Universal Election Algorithm using an auxiliary graph

• Autorzy: Wróblewski D.

Warianty tytułu

PL

Uniwersalny algorytm elekcji z użyciem grafu pomocniczego

• Języki publikacji: EN

Abstrakty

EN

We consider finite connected undirected graphs as a model for computer networks. In this framework we show a general-purpose distributed election algorithm, which uses a locally built auxiliary graph.

PL

W pracy rozpatrujemy nieskierowane grafy spójne, jako model sieci komputerowych. W modelu prezentujemy rozproszony algorytm elekcji, który podczas swego działania używa budowanego lokalnie grafu pomocniczego.

Słowa kluczowe

EN

distributed computing; elections; enumeration; coverings; ambiguous graphs

PL

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

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

Twórcy

autor

Wróblewski D.

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

Bibliografia

• [1] D. Angluin, Local and Global Properties in Networks of Processors, Proceedings of the 12,h Symposium on Theory of Computing (1980) 82-93
• [2] A. Mazurkiewicz. Distributed Disassembly of Mosaics, Information Processing Letters 46 (1993) 173-178
• [3] A. Mazurkiewicz, Distributed Enumeration, Information Processing Letters 61 (1997) 233-239
• [4] A. Mazurkiewicz, Locally Computable Enumerations, (to appear in FCT’97 proceedings)
• [5] 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
• [6] E. Godard, Y. Metivier, A characterization of families of graphs in which election is possible (ext. abstract). In Proc. Of Foundations of Software Science and Computation Structures, FOSSACS'02 (2002), M. Nielsen and U. Engberg, Eds., no. 2303 in LNCS, Springer-Verlag, pp. 159-171.
• [7] D. Wróblewski, Universal Election Algorithm, ICS PAS reports, nr 967, 2003;