Brief announcement: Compact Self-Stabilizing Leader Election for General Networks

Abstract : We present a self-stabilizing leader election algorithm for general networks, with space-complexity $O(\max\{\log \Delta, \log \log n\})$ bits per node in $n$-node networks with maximum degree~$\Delta$. This space complexity is sub-logarithmic in $n$ as long as $\Delta = n^{o(1)}$. The best space-complexity known so far for general networks was $O(\log n)$ bits per node, and algorithms with sub-logarithmic space-complexities were known for the ring only. To our knowledge, our algorithm is the first algorithm for self-stabilizing leader election to break the $\Omega(\log n)$ bound for silent algorithms in general networks. Breaking this bound was obtained via the design of a (non-silent) self-stabilizing algorithm using sophisticated tools such as solving the distance-2 coloring problem in a silent self-stabilizing manner, with space-complexity $O(\max\{\log \Delta, \log \log n\})$ bits per node. Solving this latter coloring problem allows us to implement a sub-logarithmic encoding of spanning trees --- storing the IDs of the neighbors requires $\Omega(\log n)$ bits per node, while we encode spanning trees using $O(\max\{\log \Delta, \log \log n\})$ bits per node. Moreover, we show how to construct such compactly encoded spanning trees without relying on variables encoding distances or number of nodes, as these two types of variables would also require $\Omega(\log n)$ bits per node.
Type de document :
Communication dans un congrès
31st International Symposium on Distributed Computing (DISC 2017), Oct 2017, Vienna, Austria. Proceedings of DISC 2017, 2017, 〈http://www.disc-conference.org/wp/disc2017/〉
Liste complète des métadonnées

https://hal.sorbonne-universite.fr/hal-01553088
Contributeur : Sébastien Tixeuil <>
Soumis le : lundi 3 juillet 2017 - 14:14:13
Dernière modification le : lundi 30 avril 2018 - 15:24:03

Identifiants

  • HAL Id : hal-01553088, version 1

Collections

Citation

Lélia Blin, Sébastien Tixeuil. Brief announcement: Compact Self-Stabilizing Leader Election for General Networks. 31st International Symposium on Distributed Computing (DISC 2017), Oct 2017, Vienna, Austria. Proceedings of DISC 2017, 2017, 〈http://www.disc-conference.org/wp/disc2017/〉. 〈hal-01553088〉

Partager

Métriques

Consultations de la notice

309