The computational power of beeps
From MaRDI portal
Publication:1664124
DOI10.1007/978-3-662-48653-5_3zbMATH Open1394.68014arXiv1508.03859OpenAlexW2220195453MaRDI QIDQ1664124FDOQ1664124
Authors: Calvin Newport, Seth Gilbert 
Publication date: 24 August 2018
Abstract: In this paper, we study the quantity of computational resources (state machine states and/or probabilistic transition precision) needed to solve specific problems in a single hop network where nodes communicate using only beeps. We begin by focusing on randomized leader election. We prove a lower bound on the states required to solve this problem with a given error bound, probability precision, and (when relevant) network size lower bound. We then show the bound tight with a matching upper bound. Noting that our optimal upper bound is slow, we describe two faster algorithms that trade some state optimality to gain efficiency. We then turn our attention to more general classes of problems by proving that once you have enough states to solve leader election with a given error bound, you have (within constant factors) enough states to simulate correctly, with this same error bound, a logspace TM with a constant number of unary input tapes: allowing you to solve a large and expressive set of problems. These results identify a key simplicity threshold beyond which useful distributed computation is possible in the beeping model.
Full work available at URL: https://arxiv.org/abs/1508.03859
Recommendations
Cited In (6)
- Beeping a deterministic time-optimal leader election
- Contention resolution with constant throughput and log-logstar channel accesses
- Design patterns in beeping algorithms: examples, emulation, and analysis
- Design patterns in beeping algorithms
- Counting in one-hop beeping networks
- Asynchronous broadcasting with bivalent beeps
This page was built for publication: The computational power of beeps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1664124)
