Abstrakt. Distribuerad köning är ett grundläggande samordningsproblem som uppstår i en mängd olika tillämpningar, inklusive distribuerade kataloger, helt beställda multicast och distribuerad ömsesidig uteslutning. Pilprotokollet är en lösning för distribuerad köning som baseras på omkastning av sökvägen på ett förvalt spanning träd i nätverket. Vi presenterar en ny och omfattande konkurrensanalys av pilprotokollet. Vi anser att den totala kostnaden för att hantera ett begränsat antal köande förfrågningar, som kan eller inte kan utfärdas samtidigt, och visar att pilprotokollet är O(s · log D)-konkurrenskraftigt till optimal köning protokoll, där s och D är sträck och diametern, respektive spanning träd. Dessutom visar vi att vår analys är nästan tight genom att bevisa att för varje spännträd som väljs för utförande, pilprotokollet är (s · logg (D/s) / logg (D/s))-konkurrenskraftigt till optimal köning protokoll. Vår analys avslöjar en spännande koppling mellan pil protokoll och närmaste granne resande säljare turné på en lämpligt definierad graf.
I REF, Det visas att i detta fall, den totala kostnaden för Arrow är inom en faktor O (log D) av den optimala kostnaden på trädet T.
Dynamic Analysis of the Arrow Distributed Protocol
{'venue': 'Theory of Computing Systems', 'journal': 'Theory of Computing Systems', 'mag_field_of_study': ['Computer Science']}