Optimal Message-Passing with Noisy Beeps

DOI10.1145/3583668.3594594MaRDI QIDQ6202266zbMATH OpenOpenAlexFDO

Authors P. Davies

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

beeping modelmessage passingsuperimposed codes

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: 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 only the capability of {it 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 extsf{Broadcast CONGEST} can be simulated in $O(Deltalogn)$ round of the noisy (or noiseless) beeping model, and a round of extsf{CONGEST} can be simulated in $O(Delt{a}^{2}logn)$ rounds (where $Delta$ 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. As an example, we present an $O(logn)$-round extsf{Broadcast CONGEST} algorithm for maximal matching, which, when simulated using our method, immediately implies a near-optimal $O(Deltalo{g}^{2}n)$-round maximal matching algorithm in the noisy beeping model.

Cites work

• A biological solution to a fundamental distributed computing problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Almost cover-free codes and designs
• An Improved Distributed Algorithm for Maximal Independent Set
• Beeping a deterministic time-optimal leader election
• Can Uncoordinated Beeps tell Stories?
• Construction and impromptu repair of an MST in a distributed network with o(m) communication
• Deploying wireless networks with beeps
• Distributed approximate maximum matching in the CONGEST model
• Efficient randomized distributed coloring in CONGEST
• Fundamentals of Error-Correcting Codes
• scientific article; zbMATH DE number 3801449 (Why is no real title available?)
• Leader election in multi-hop radio networks
• Near optimal leader election in multi-hop radio networks
• Nonrandom binary superimposed codes
• On r-cover-free families
• On the upper bound of the size of the \(r\)-cover-free families
• Optimal multi-broadcast with beeps using group testing
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Some simple distributed algorithms for sparse networks
• The locality of distributed symmetry breaking

Cited in

(5)

• Optimal message-passing with noisy beeps
• Brief announcement: Content-oblivious leader election on rings
• Content-oblivious leader election on rings
• Beeping deterministic congest algorithms in graphs
• Deterministic local problems in radio networks: on the impact of local domination and a bit of advice

This page was built for publication: Optimal Message-Passing with Noisy Beeps

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