Universal Election Algorithm

• Autorzy: Wróblewski D.

Warianty tytułu

PL

Uniwersalny algorytm elekcji

• Języki publikacji: EN

Abstrakty

EN

We consider undirected connected graphs as natural model for computer networks. For this model, the distributed election algorithm is presented, its correctness is proved and its complexity is discussed.

PL

W pracy rozpatrujemy nieskierowane grafy spójne, będące modelem sieci komputerowych. W tym modelu prezentujemy rozproszony algorytm elekcji, dowodzimy jego poprawności i dyskutujemy jego złożoność.

Słowa kluczowe

EN

distributed computing; elections; enumeration; ambiguous graphs

PL

programowanie rozproszone; elekcja; numeracja; grafy lokalnie niejednoznaczne

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2003
• Tom: Nr 967
• Strony: 1--16

Twórcy

autor

Wróblewski D.

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

Bibliografia

• [1 ] C. Berge, The Theory of Graphs and its Applications, Methuen and Co. Ltd., London 1962
• [2] 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
• [3] A. Mazurkiewicz, Distributed Disassembly of Mosaics, Information Processing Letters 46 (1993) 173-178
• [4] A. Mazurkiewicz, Distributed Enumeration, Information Processing Letters 61 (1997) 233-239
• [5] A. Mazurkiewicz, Locally Computable Enumerations, (to appear in FCT’97 proceedings)
• [6] M. Moczurad, Contractible Graphs are not Retractable, (draft)
• [7] E. M. Reingold, J. Nievergelt, N. Deo, Algorytmy kombinatoryczne, PWN, Warszawa 1985