Election in the Qualitative World
- 392 Downloads
In , Barrière et al. 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 the election problem can be solved.
Unable to display preview. Download preview PDF.
- 1.Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th Symposium on Theory of Computing, STOC 1980, pp. 82–93 (1980)Google Scholar
- 4.Barrière, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Rendezvous and election of mobile agents: Impact of sense of direction. In: Theory of Computing Systems (to appear)Google Scholar
- 5.Bender, M., Slonim, D.: The power of team exploration: Two robots can learn unlabeled directed graphs. In: Proc. of the 35th annual Symposium on Foundations of Computer Science, FOCS 1994, pp. 75–85 (1994)Google Scholar
- 6.Boldi, P., Codenotti, B., Gemmell, P., Shammah, S., Simon, J., Vigna, S.: Symmetry breaking in anonymous networks: Characterizations. In: Proc. 4th Israeli Symposium on Theory of Computing and Systems, pp. 16–26. IEEE Press, Los Alamitos (1996)Google Scholar