Dr Peter Davies-Peck peter.w.davies@durham.ac.uk
Assistant Professor
Beeping models are models for networks of weak devices, such as sensor networks or biological networks. In these networks, nodes are allowed to communicate only via emitting beeps: unary pulses of energy. Listening nodes have only the capability of carrier sensing: they can only distinguish between the presence or absence of a beep, but receive no other information. The noisy beeping model further assumes listening nodes may be disrupted by random noise. Despite this extremely restrictive communication model, it transpires that complex distributed tasks can still be performed by such networks. In this paper we provide an optimal procedure for simulating general message passing in the beeping and noisy beeping models. We show that a round of Broadcast CONGEST can be simulated in O(∆ log n) rounds of the noisy (or noiseless) beeping model, and a round of CONGEST can be simulated in O(∆ 2 log n) rounds (where ∆ is the maximum degree of the network). We also prove lower bounds demonstrating that no simulation can use asymptotically fewer rounds. This allows a host of graph algorithms to be efficiently implemented in beeping models. We present several example applications, including an O(log n)-round Broadcast CONGEST algorithm for maximal matching, which, when simulated using our method, immediately implies a near-optimal O(∆ log 2 n)-round maximal matching algorithm in the noisy beeping model. A preliminary version of this paper appeared in the proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC) [14].
Davies-Peck, P. (online). Optimal Message-Passing with Noisy Beeps. Distributed Computing,
Journal Article Type | Article |
---|---|
Acceptance Date | May 27, 2025 |
Online Publication Date | Jun 10, 2025 |
Deposit Date | Jun 5, 2025 |
Publicly Available Date | Jun 17, 2025 |
Journal | Distributed Computing |
Print ISSN | 0178-2770 |
Electronic ISSN | 1432-0452 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Keywords | Message Passing; Beeping Model; Superimposed Codes |
Public URL | https://durham-repository.worktribe.com/output/4089497 |
Published Journal Article (Advance Online Version)
(435 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Component stability in low-space massively parallel computation
(2024)
Journal Article
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
(2021)
Journal Article
Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
(2021)
Journal Article
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
(2021)
Journal Article
On the Locality of the Lovász Local Lemma
(2025)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search