Fast and Robust Information Spreading in the Noisy PULL Model
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912110637744128 |
|---|---|
| author | D'Archivio, Niccolò Korman, Amos Natale, Emanuele Vacus, Robin |
| author_facet | D'Archivio, Niccolò Korman, Amos Natale, Emanuele Vacus, Robin |
| contents | Understanding how information can efficiently spread in distributed systems under noisy communications is a fundamental question in both biological research and artificial system design. When agents are able to control whom they interact with, noise can often be mitigated through redundancy or other coding techniques, but it may have fundamentally different consequences on well-mixed systems. Specifically, Boczkowski et al. (2018) considered the noisy $\mathcal{PULL}(h)$ model, where each message can be viewed as any other message with probability $δ$. The authors proved that in this model, the basic task of propagating a bit value from a single source to the whole population requires $Ω(\frac{nδ}{h(1-δ|Σ|)^2})$ (parallel) rounds.
The current work shows that the aforementioned lower bound is almost tight. In particular, when each agent observes all other agents in each round, which relates to scenarios where each agent senses the system's average tendency, information spreading can reliably be achieved in $\mathcal{O}(\log n)$ time, assuming constant noise. We present two simple and highly efficient protocols, thus suggesting their applicability to real-life scenarios. Notably, they also work in the presence of multiple conflicting sources and efficiently converge to their plurality opinion. The first protocol we present uses 1-bit messages but relies on a simultaneous wake-up assumption. By increasing the message size to 2 bits and removing the speedup in the information spreading time that may result from having multiple sources, we also present a simple and highly efficient self-stabilizing protocol that avoids the simultaneous wake-up requirement.
Overall, our results demonstrate how, under stochastic communication, increasing the sample size can compensate for the lack of communication structure by linearly accelerating information spreading time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02560 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast and Robust Information Spreading in the Noisy PULL Model D'Archivio, Niccolò Korman, Amos Natale, Emanuele Vacus, Robin Distributed, Parallel, and Cluster Computing Understanding how information can efficiently spread in distributed systems under noisy communications is a fundamental question in both biological research and artificial system design. When agents are able to control whom they interact with, noise can often be mitigated through redundancy or other coding techniques, but it may have fundamentally different consequences on well-mixed systems. Specifically, Boczkowski et al. (2018) considered the noisy $\mathcal{PULL}(h)$ model, where each message can be viewed as any other message with probability $δ$. The authors proved that in this model, the basic task of propagating a bit value from a single source to the whole population requires $Ω(\frac{nδ}{h(1-δ|Σ|)^2})$ (parallel) rounds. The current work shows that the aforementioned lower bound is almost tight. In particular, when each agent observes all other agents in each round, which relates to scenarios where each agent senses the system's average tendency, information spreading can reliably be achieved in $\mathcal{O}(\log n)$ time, assuming constant noise. We present two simple and highly efficient protocols, thus suggesting their applicability to real-life scenarios. Notably, they also work in the presence of multiple conflicting sources and efficiently converge to their plurality opinion. The first protocol we present uses 1-bit messages but relies on a simultaneous wake-up assumption. By increasing the message size to 2 bits and removing the speedup in the information spreading time that may result from having multiple sources, we also present a simple and highly efficient self-stabilizing protocol that avoids the simultaneous wake-up requirement. Overall, our results demonstrate how, under stochastic communication, increasing the sample size can compensate for the lack of communication structure by linearly accelerating information spreading time. |
| title | Fast and Robust Information Spreading in the Noisy PULL Model |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2411.02560 |