LIPIcs.DISC.2017.43.pdf
- Filesize: 325 kB
- 3 pages
Document
Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs
Authors
-
Part of:
Volume:
31st International Symposium on Distributed Computing (DISC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-10-12
Cite As Get 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).
Subject Classification
Keywords
- Leader Election
- Self-stabilization
- Memory Complexity
- Arbitrary Graphs
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
B. Awerbuch and R. Ostrovsky. Memory-efficient and self-stabilizing network reset. In PODC, pages 254-263. ACM, 1994.
-
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.
-
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.
- 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.
-
S. Dolev. Self-stabilization. MIT Press, March 2000.
-
S. Dolev, M. G. Gouda, and M. Schneider. Memory requirements for silent stabilization. Acta Inf., 36(6):447-462, 1999.
- 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.
- 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.
-
T. Herman and S. V. Pemmaraju. Error-detecting codes and fault-containing self-stabilization. Inf. Process. Lett., 73(1-2):41-46, 2000.
-
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.
-
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.