Compact self-stabilizing leader election for general networks

DOI10.1007/978-3-319-77404-6_13MaRDI QIDQ2294688zbMATH OpenOpenAlexFDO

Authors Lélia Blin, Sébastien Tixeuil

Publication date 12 February 2020

Full work available at URL https://arxiv.org/abs/1702.07605

Mathematics Subject Classification ID

Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Analysis of algorithms (68W40)

Abstract: We present a self-stabilizing leader election algorithm for arbitrary networks, with space-complexity $O(maxlogDelta,loglogn)$ 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 arbitrary networks was $O(logn)$ 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(logn)$ bound for silent algorithms in arbitrary 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(maxlogDelta,loglogn)$ 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(logn)$ bits per node, while we encode spanning trees using $O(maxlogDelta,loglogn)$ 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(logn)$ bits per node.

Recommendations

• Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative
• Self-stabilizing leader election in optimal space under an arbitrary scheduler
• Self-stabilizing weak leader election in anonymous trees using constant memory per edge
• Self-stabilizing leader election in polynomial steps
• The space complexity of leader election in anonymous networks

Cited in

(10)

• A self-stabilizing algorithm for b-matching
• Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative
• The space complexity of leader election in anonymous networks
• scientific article; zbMATH DE number 88976 (Why is no real title available?)
• Self-stabilizing weak leader election in anonymous trees using constant memory per edge
• Communication-efficient leader election and consensus with limited link synchrony
• Communication efficient self-stabilizing leader election
• Resource efficient stabilization for local tasks despite unknown capacity links
• Self-stabilizing leader election in optimal space under an arbitrary scheduler
• Self-stabilizing leader election in dynamic networks

This page was built for publication: Compact self-stabilizing leader election for general networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294688)