<p>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 <i>carrier sensing</i>: 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 <Emphasis FontCategory="SansSerif">Broadcast CONGEST</Emphasis> can be simulated in <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2025_488_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">$O(\Delta \log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi mathvariant="normal">Δ</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> rounds of the noisy (or noiseless) beeping model, and a round of <Emphasis FontCategory="SansSerif">CONGEST</Emphasis> can be simulated in <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2025_488_Article_IEq2.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="83" /> </InlineMediaObject> <EquationSource Format="TEX">$O(\Delta ^2\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi mathvariant="normal">Δ</mi> <mn>2</mn> </msup> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> rounds (where <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2025_488_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\Delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2025_488_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="61" /> </InlineMediaObject> <EquationSource Format="TEX">$O(\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-round <Emphasis FontCategory="SansSerif">Broadcast CONGEST</Emphasis> algorithm for maximal matching, which, when simulated using our method, immediately implies a near-optimal <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2025_488_Article_IEq5.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="83" /> </InlineMediaObject> <EquationSource Format="TEX">$O(\Delta \log ^2 n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi mathvariant="normal">Δ</mi> <msup> <mo>log</mo> <mn>2</mn> </msup> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-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) [<CitationRef CitationID="CR14">14</CitationRef>].</p>

Optimal message-passing with noisy beeps

期刊论文
出版模式：

开放获取
发表日期：

2025年6月10日

查看全文

Peter Davies-Peck

摘要

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(\Delta \log n)$ $O (Δ log n)$ rounds of the noisy (or noiseless) beeping model, and a round of CONGEST can be simulated in $O(\Delta ^2\log n)$ $O (Δ^{2} log n)$ 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. We present several example applications, including an $O(\log n)$ $O (log n)$ -round Broadcast CONGEST algorithm for maximal matching, which, when simulated using our method, immediately implies a near-optimal $O(\Delta \log ^2 n)$ $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].