Noisy Beeps

Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We study the effect of noise on the n-party beeping model. In this model, in every round, each party may decide to either 'beep' or not. All parties hear a beep if and only if at least one party beeps. The beeping model is becoming increasingly popular, as it offers a very simple abstraction of wireless networks and is very well suited for studying biological phenomena. Still, the noise resilience of the beeping model is yet to be understood. Our main result is a lower bound, showing that making protocols in the beeping model resilient to noise may have a large performance overhead. Specifically, we give a protocol that works over the (noiseless) beeping model, and prove that any scheme that simulates this protocol over the beeping model with correlated stochastic noise will blow up the number of rounds by an Ω(log n) multiplicative factor. We complement this result by a matching upper bound, constructing a noise-resilient simulation scheme with O(log n) overhead for any noiseless beeping protocol.

Original languageEnglish (US)
Title of host publicationPODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages418-427
Number of pages10
ISBN (Electronic)9781450375825
DOIs
StatePublished - Jul 31 2020
Event39th Symposium on Principles of Distributed Computing, PODC 2020 - Virtual, Online, Italy
Duration: Aug 3 2020Aug 7 2020

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference39th Symposium on Principles of Distributed Computing, PODC 2020
Country/TerritoryItaly
CityVirtual, Online
Period8/3/208/7/20

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • beeping models
  • communication complexity
  • distributed systems
  • error-correcting codes
  • interactive coding
  • lower bounds

Fingerprint

Dive into the research topics of 'Noisy Beeps'. Together they form a unique fingerprint.

Cite this