Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms
Given a boolean predicate $\Pi$ on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for $\Pi$ is a distributed algorithm that can start from any initial configuration of the network (i.e., every node has an arbitrary value assigned to each of its variable...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/9335/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850278361115394048 |
|---|---|
| author | Lélia Blin Laurent Feuilloley Gabriel Le Bouder |
| author_facet | Lélia Blin Laurent Feuilloley Gabriel Le Bouder |
| author_sort | Lélia Blin |
| collection | DOAJ |
| description | Given a boolean predicate $\Pi$ on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for $\Pi$ is a distributed algorithm that can start from any initial configuration of the network (i.e., every node has an arbitrary value assigned to each of its variables), and eventually converge to a configuration satisfying $\Pi$. It is known that leader election does not have a deterministic self-stabilizing algorithm using a constant-size register at each node, i.e., for some networks, some of their nodes must have registers whose sizes grow with the size $n$ of the networks. On the other hand, it is also known that leader election can be solved by a deterministic self-stabilizing algorithm using registers of $O(\log \log n)$ bits per node in any $n$-node bounded-degree network. We show that this latter space complexity is optimal. Specifically, we prove that every deterministic self-stabilizing algorithm solving leader election must use $\Omega(\log \log n)$-bit per node registers in some $n$-node networks. In addition, we show that our lower bounds go beyond leader election, and apply to all problems that cannot be solved by anonymous algorithms. |
| format | Article |
| id | doaj-art-ec12cbc7062b44dda93f5c36d9d8a673 |
| institution | OA Journals |
| issn | 1365-8050 |
| language | English |
| publishDate | 2023-03-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-ec12cbc7062b44dda93f5c36d9d8a6732025-08-20T01:49:32ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-03-01vol. 25:1Distributed Computing and...10.46298/dmtcs.93359335Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election AlgorithmsLélia BlinLaurent FeuilloleyGabriel Le BouderGiven a boolean predicate $\Pi$ on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for $\Pi$ is a distributed algorithm that can start from any initial configuration of the network (i.e., every node has an arbitrary value assigned to each of its variables), and eventually converge to a configuration satisfying $\Pi$. It is known that leader election does not have a deterministic self-stabilizing algorithm using a constant-size register at each node, i.e., for some networks, some of their nodes must have registers whose sizes grow with the size $n$ of the networks. On the other hand, it is also known that leader election can be solved by a deterministic self-stabilizing algorithm using registers of $O(\log \log n)$ bits per node in any $n$-node bounded-degree network. We show that this latter space complexity is optimal. Specifically, we prove that every deterministic self-stabilizing algorithm solving leader election must use $\Omega(\log \log n)$-bit per node registers in some $n$-node networks. In addition, we show that our lower bounds go beyond leader election, and apply to all problems that cannot be solved by anonymous algorithms.http://dmtcs.episciences.org/9335/pdfcomputer science - distributed, parallel, and cluster computingcomputer science - data structures and algorithms |
| spellingShingle | Lélia Blin Laurent Feuilloley Gabriel Le Bouder Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms Discrete Mathematics & Theoretical Computer Science computer science - distributed, parallel, and cluster computing computer science - data structures and algorithms |
| title | Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms |
| title_full | Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms |
| title_fullStr | Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms |
| title_full_unstemmed | Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms |
| title_short | Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms |
| title_sort | optimal space lower bound for deterministic self stabilizing leader election algorithms |
| topic | computer science - distributed, parallel, and cluster computing computer science - data structures and algorithms |
| url | http://dmtcs.episciences.org/9335/pdf |
| work_keys_str_mv | AT leliablin optimalspacelowerboundfordeterministicselfstabilizingleaderelectionalgorithms AT laurentfeuilloley optimalspacelowerboundfordeterministicselfstabilizingleaderelectionalgorithms AT gabriellebouder optimalspacelowerboundfordeterministicselfstabilizingleaderelectionalgorithms |