Leader election for anonymous asynchronous agents in arbitrary networks

Dariusz Dereniowski; Andrzej Pelc

doi:10.1007/s00446-013-0196-x

Leader election for anonymous asynchronous agents in arbitrary networks

Abstrakt

We consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph and share it with other agents to accomplish leader election. This can be done using meetings of agents, which is difficult because of their asynchronous nature: an adversary has total control over the speed of agents. When can a leader be elected in this adversarial scenario and how to do it? We give a complete answer to this question by characterizing all initial configurations for which leader election is possible and by constructing an algorithm that accomplishes leader election for all configurations for which this can be done.

Cytowania

1 7

CrossRef
0

Web of Science
1 9

Scopus

Autorzy (2)

Dariusz Dereniowski prof. dr hab. inż.
Andrzej Pelc
- Université du Québec en Outaouais Département d’informatique

Cytuj jako

Pełna treść

pobierz publikację

pobrano 14 razy

Wersja publikacji: Accepted albo Published Version
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00446-013-0196-x
Licencja: otwiera się w nowej karcie

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:: DISTRIBUTED COMPUTING nr 27, wydanie 1, strony 21 - 38,
ISSN: 0178-2770
Język:: angielski
Rok wydania:: 2014
Opis bibliograficzny:: Dereniowski D., Pelc A.: Leader election for anonymous asynchronous agents in arbitrary networks// DISTRIBUTED COMPUTING. -Vol. 27, iss. 1 (2014), s.21-38
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00446-013-0196-x
Weryfikacja:: Politechnika Gdańska