REVIEW 2 cited by
On Distributed Computing with Beeps
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We consider networks of processes which interact with beeps. Various beeping models are used. The basic one, defined by Cornejo and Kuhn [CK10], assumes that a process can choose either to beep or to listen; if it listens it can distinguish between silence or the presence of at least one beep. The aim of this paper is the study of the resolution of paradigms such as collision detection, computation of the degree of a vertex, colouring, or 2-hop-colouring in the framework of beeping models. For each of these problems we present Las Vegas or Monte Carlo algorithms and we analyse their complexities expressed in terms of the number of slots. We present also efficient randomised emulations of more powerful beeping models on the basic one. We illustrate emulation procedures with an efficient degree computation algorithm in the basic beeping model; this algorithm was given initially in a more powerful model.
Forward citations
Cited by 2 Pith papers
-
Computing in Anonymous Dynamic Networks with One-Bit Communications
One-bit broadcast-counting in anonymous dynamic networks supports general multiset computation in O(n³ log² n) rounds, nearly matching the congested O(n³) bound, with a matching Ω(n³) lower bound for large input universes.
-
Notes on Theory of Distributed Systems
Lecture notes compiling standard topics and results in distributed systems theory from basic communication to population protocols and topological methods.
Discussion (0). Continue with ORCID to comment.