Article ID Journal Published Year Pages File Type
438426 Theoretical Computer Science 2008 17 Pages PDF
Abstract

In “Can we elect if we cannot compare” (SPAA’03), Barrière, Flocchini, Fraigniaud and Santoro consider a qualitative model of distributed computing, where the labels of the entities are distinct but mutually incomparable. They study the leader election problem in a distributed mobile environment and they wonder whether there exists an algorithm such that for each distributed mobile environment, it either states that the problem cannot be solved in this environment, or it successfully elects a leader. In this paper, we give a positive answer to this question. We also give a characterization of the distributed mobile environments where election and rendezvous can be solved.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics