Vi anser att problemet med att utforma en distribuerad algoritm som, med tanke på en godtycklig ansluten graf G noder med unika etiketter, omvandlar G till en sorterad lista av noder. Denna algoritm bör vara så enkel som möjligt och, för skalbarhet, bör garantera en polylogaritmisk körtid samt som mest en polylogaritmisk ökning av graden av varje nod under dess utförande. Dessutom bör det vara självstabiliserande, det vill säga, det bör så småningom kunna konstruera en sorterad lista från varje tillstånd i vilket grafen är ansluten. Det visar sig att det inte är lätt att tillfredsställa alla dessa krav samtidigt. Vår grundläggande strategi mot detta mål är den så kallade linearization tekniken: varje nod v upprepade gånger gör följande med sina grannar: • för dess vänster (dvs mindre) grannar u1,. .., u k i ordning efter minskande etiketter, v ersätter {v, u1},. ...,.................................................................................... ..,,,........................................................................................................ .., w i ordningen för att öka etiketter, v ersätter {v, w1},. ...,............................................................. ..,............................................................. Som visas i detta papper, omvandlar denna teknik någon ansluten graf till en sorterad lista, men det finns grafer som detta kan ta lång tid. Därför föreslår vi flera förlängningar av linjäriseringstekniken och experimentellt utvärdera deras prestanda. Våra resultat visar att några av dessa har en polylogaritmisk prestanda, så det finns hopp om att det finns distribuerade algoritmer som kan uppnå alla våra mål ovan.
I REF presenteras en lokal kontrollstrategi som kallas linearisering för att omvandla en godtyckligt ansluten graf till en sorterad lista.
Linearization: Locally self-stabilizing sorting in graphs
{'venue': 'University of Madrid', 'journal': None, 'mag_field_of_study': ['Computer Science']}