A Simple Lower Bound for Set Agreement in Dynamic Networks
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917891193962496 |
|---|---|
| author | Fraigniaud, Pierre Nguyen, Minh Hang Paz, Ami |
| author_facet | Fraigniaud, Pierre Nguyen, Minh Hang Paz, Ami |
| contents | Given a positive integer $k$, $k$-set agreement is the distributed task in which each process $i\in [n]$ in a group of $n$ processing nodes starts with an input value $x_i$ in the set $\{0,\dots,k\}$, and must output a value $y_i$ such that (1) for every $i \in [n]$, $y_i$ is the input value of some process, and (2)$|\{y_i : i\in [n]\}|\leq k$. That is, at most $k$ different values in total must be outputted by the processes. The case $k=1$ correspond to (binary) consensus, arguably the most studied problem in distributed computing. While lower bounds for consensus have been obtained for most of the standard distributed computing models, the design of lower bounds for $k$-set agreement with $k>1$ is notoriously known to be much more difficult, and remains open for many models. The main techniques for designing lower bounds for k-set agreement with $k>1$ use tools from algebraic topology.
The algebraic topology tools are difficult to manipulate, and require a lot of care for avoiding mistakes. This difficulty increases when the communications are mediated by a network of arbitrary structure. Recently, the KNOWALL model has been specifically designed as a first attempt to understand the LOCAL model through the lens of algebraic topology, and Castañeda et al.(2021) have designed lower bounds for $k$-set agreement in the KNOWALL model, with applications to dynamic networks.
In this work, we re-prove the same lower bound for $k$-set agreement in the KNOWALL model. This new proof stands out in its simplicity, which makes it accessible to a broader audience, and increases confidence in the result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07036 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Simple Lower Bound for Set Agreement in Dynamic Networks Fraigniaud, Pierre Nguyen, Minh Hang Paz, Ami Distributed, Parallel, and Cluster Computing Given a positive integer $k$, $k$-set agreement is the distributed task in which each process $i\in [n]$ in a group of $n$ processing nodes starts with an input value $x_i$ in the set $\{0,\dots,k\}$, and must output a value $y_i$ such that (1) for every $i \in [n]$, $y_i$ is the input value of some process, and (2)$|\{y_i : i\in [n]\}|\leq k$. That is, at most $k$ different values in total must be outputted by the processes. The case $k=1$ correspond to (binary) consensus, arguably the most studied problem in distributed computing. While lower bounds for consensus have been obtained for most of the standard distributed computing models, the design of lower bounds for $k$-set agreement with $k>1$ is notoriously known to be much more difficult, and remains open for many models. The main techniques for designing lower bounds for k-set agreement with $k>1$ use tools from algebraic topology. The algebraic topology tools are difficult to manipulate, and require a lot of care for avoiding mistakes. This difficulty increases when the communications are mediated by a network of arbitrary structure. Recently, the KNOWALL model has been specifically designed as a first attempt to understand the LOCAL model through the lens of algebraic topology, and Castañeda et al.(2021) have designed lower bounds for $k$-set agreement in the KNOWALL model, with applications to dynamic networks. In this work, we re-prove the same lower bound for $k$-set agreement in the KNOWALL model. This new proof stands out in its simplicity, which makes it accessible to a broader audience, and increases confidence in the result. |
| title | A Simple Lower Bound for Set Agreement in Dynamic Networks |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2501.07036 |