Election in the Qualitative World

  • Jérémie Chalopin
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)


In [3], 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.

Unable to display preview. Download preview PDF.


  1. 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
  2. 2.
    Awerbuch, B., Betke, M., Rivest, R., Singh, M.: Piecemeal graph exploration by a mobile robot (extended abstract). In: Proc. of the 8th annual conference on Computational Learning Theory, COLT 1995, pp. 321–328. ACM Press, New York (1995)CrossRefGoogle Scholar
  3. 3.
    Barrière, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Can we elect if we cannot compare? In: Proc. of the 15th annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2003, pp. 324–332. ACM Press, New York (2003)CrossRefGoogle Scholar
  4. 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. 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. 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
  7. 7.
    Boldi, P., Vigna, S.: Fibrations of graphs. Discrete Math. 243, 21–66 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Bougé, L.: On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes. Acta Informatica 25(2), 179–201 (1988)zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    Chalopin, J., Métivier, Y.: A bridge between the asynchronous message passing model and local computations in graphs. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 212–223. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  10. 10.
    Das, S., Flocchini, P., Nayak, A., Santoro, N.: Distributed exploration of an unknown graph. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 99–114. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  11. 11.
    Dessmark, A., Fraigniaud, P., Pelc, A.: Deterministic rendezvous in graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 184–195. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  12. 12.
    Palamidessi, C.: Comparing the expressive power of the synchronous and the asynchronous π-calculus. Mathematical Structures in Computer Science 13(5), 685–719 (2003)CrossRefMathSciNetGoogle Scholar
  13. 13.
    Yamashita, M., Kameda, T.: Computing on anonymous networks: Part i - characterizing the solvable cases. IEEE Transactions on parallel and distributed systems 7(1), 69–89 (1996)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Jérémie Chalopin
    • 1
  1. 1.LaBRIUniversité Bordeaux 1TalenceFrance

Personalised recommendations