Document Open Access Logo

Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs

Authors Lélia Blin, Sébastien Tixeuil

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.43.pdf
  • Filesize: 325 kB
  • 3 pages

Document Identifiers

Author Details

Lélia Blin
Sébastien Tixeuil

Cite AsGet BibTex

Lélia Blin and Sébastien Tixeuil. Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.43

Abstract

We present the first self-stabilizing algorithm for leader election in arbitrary topologies whose space complexity is O(max{log Delta, log log n}) bits per node, where n is the network size and Delta its degree. This complexity is sub-logarithmic in n when Delta = n^o(1).
Keywords
  • Leader Election
  • Self-stabilization
  • Memory Complexity
  • Arbitrary Graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. B. Awerbuch and R. Ostrovsky. Memory-efficient and self-stabilizing network reset. In PODC, pages 254-263. ACM, 1994. Google Scholar
  2. L. Blin and S. Tixeuil. Compact deterministic self-stabilizing leader election: The exponential advantage of being talkative. In Proceedings of the 27th International Conference on Distributed Computing (DISC 2013), Lecture Notes in Computer Science (LNCS), pages 76-90. Springer Berlin / Heidelberg, 2013. Google Scholar
  3. L. Blin and S. Tixeuil. Compact deterministic self-stabilizing leader election on a ring: The exponential advantage of being talkative. Distributed Computing, page to appear, 2017. Google Scholar
  4. S. Delaët, B. Ducourthial, and S. Tixeuil. Self-stabilization with r-operators revisited. Journal of Aerospace Computing, Information, and Communication (JACIC), 3(10):498-514, 2006. URL: http://dx.doi.org/10.2514/1.19848.
  5. S. Dolev. Self-stabilization. MIT Press, March 2000. Google Scholar
  6. S. Dolev, M. G. Gouda, and M. Schneider. Memory requirements for silent stabilization. Acta Inf., 36(6):447-462, 1999. Google Scholar
  7. B. Ducourthial and S. Tixeuil. Self-stabilization with path algebra. Theoretical Computer Science (TCS), 293(1):219-236, February 2003. URL: http://dx.doi.org/10.1016/S0304-3975(02)00238-4.
  8. M. Gradinariu and C. Johnen. Self-stabilizing neighborhood unique naming under unfair scheduler. In Euro-Par 2001: Parallel Processing, 7th International Euro-Par Conference Manchester, UK August 28-31, 2001, Proceedings, pages 458-465, 2001. URL: http://dx.doi.org/10.1007/3-540-44681-8_67.
  9. T. Herman and S. V. Pemmaraju. Error-detecting codes and fault-containing self-stabilization. Inf. Process. Lett., 73(1-2):41-46, 2000. Google Scholar
  10. T. Herman and S. Tixeuil. A distributed tdma slot assignment algorithm for wireless sensor networks. In Proceedings of the First Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensors'2004), number 3121 in Lecture Notes in Computer Science, pages 45-58, Turku, Finland, July 2004. Springer-Verlag. Google Scholar
  11. J.Beauquier, M. Gradinariu, C. Johnen, and J. O. Durand-Lose. Token-based self-stabilizing uniform algorithms. J. Parallel Distrib. Comput., 62(5):899-921, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact