Brief announcement: Compact Self-Stabilizing Leader Election for General Networks - Sorbonne Université Access content directly
Conference Papers Year : 2017

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.
No file

Dates and versions

hal-01553088 , version 1 (03-07-2017)

Identifiers

  • HAL Id : hal-01553088 , version 1

Cite

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. ⟨hal-01553088⟩
354 View
0 Download

Share

Gmail Mastodon Facebook X LinkedIn More