Universal Election Algorithm using forward links

• Autorzy: Wróblewski D.

Warianty tytułu

PL

Uniwersalny algorytm elekcji z użyciem połączeń przekierowujących

• Języki publikacji: EN

Abstrakty

EN

We consider finite connected undirected graphs as a model for anonymous computer networks. In this framework we show a general purpose distributed election protocol, which uses forward links over the standard communication channels between processors. The forward links are represented in the form of structured labels, so the algorithm is a graph relabelling system, however its transformations are not local in the classical sense. For this particular algorithm we define a new notion of extended locality and claim that it still conforms to the intuitive meaning of the locality term.

PL

Rozpatrujemy skończone grafy spójne, będące modelem anonimowych sieci komputerowych. W modelu tym definiujemy uniwersalny algorytm elekcji, który w trakcie działania używa połączeń przekierowujących rozpiętych wzdłuż krawędzi grafu. Przekierowania są reprezentowane za pomocą strukturalnych etykiet, zatem algorytm jest wyrażalny w formalizmie systemów reetykietujących grafy. Jednak kroki algorytmu nie są transformacjami lokalnymi w klasycznym znaczeniu tego słowa. Dlatego też definiujemy dopasowane do tego algorytmu pojęcie lokalności rozszerzonej oraz uzasadnionym że jest ono zgodne z intuicyjnym rozumieniem terminu "lokalność".

Słowa kluczowe

EN

distributed computing; elections; enumeration; coverings; ambiguous graphs; anonymous networks

PL

programowanie rozproszone; elekcja; numeracja; pokrycia; grafy lokalnie niejednoznaczne; grafy anonimowe

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2003
• Tom: Nr 970
• Strony: 1--32
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Wróblewski D.

• Institute of Computers Science, Ordona 21, 01-237 Warsaw, Poland,

Bibliografia

• [Ang80] D. Angluin. Local and Global Properties in Networks of Processors, Proceedings of the 12th Symposium on Theory of Computing (1980) 82-93
• [Bar96] V. C. Barbosa, An Introduction to Distributed Algorithms, The MIT Press, 1996
• [Dem98] P. Dembiński, Randomized Enumeration, ICS PAS Reports 848 (1998)
• [GM02] E. Godard, Y. Metivier. A characterization of families of graphs in which election is possible (ext. abstract). In Proc. Of Foundations oj Software Science and Computation Structures. FOSSACS'02 (2002), M. Nielsen and U. Engberg, Eds., no. 2303 in LNCS, Springer-Verlag, pp. 159-171
• [LMZ93] I. Litovsky, Y. Metivier, W. Zielonka, The Power and Limitations of Local Computations in Graphs and Networks, Lecture Notes in Computer Science 657 (1993) 333-345
• [Maz93] A. Mazurkiewicz. Distributed Disassembly of Mosaics. Information Processing Letters 46 (1993) 173-178
• [Maz97] A. Mazurkiewicz, Distributed Enumeration. Information Processing Letters 61 (1997) 233-239
• [Maz97.1] A. Mazurkiewicz, Locally Computable Enumerations, (to appear in FCT97 proceedings)
• [Tel94] G. Tel, Introduction to Distributed Algorithms, Cambridge University Press, 1994
• [Wro03] D. Wróblewski, Universal election protocol. Prace IPI PAN, nr 967. 2003
• [Wro03.1] D. Wróblewski, Universal Election Algorithm using an auxiliary graph. Prace IPI PAN. nr 968. 2003