Consider a group of nodes connected through multiple-access channels and the
only observable feedback on the channel is a binary value: either one or more
nodes have transmitted (busy), or no node has transmitted (idle). The channel
model thus described is called *Beeping Model *and captures computation in
hardware using a group of sequential circuit modules connected by a logic-OR
gate. It has also been used to study chemical signaling mechanisms between
biological cells and carrier-sensing based wireless communication.

In
this paper, we study the distributed complexity of two fundamental problems in
the Beeping Model. In both problems, there is a set of nodes each with a unique
identifier *i* in *N={1,2,... ,n}*. A subset of the nodes
*A* is called *active nodes*. In the *Membership Problem*,
every node needs to find out the identifiers of all active nodes. In the
*Conflict Resolution *problem, the goal is to let every active node use
the channel alone (without collision) at least once.

We derive two results
that characterize the distributed complexity of these problems. First, we prove
that in the Beeping Model the two above problems are equally hard. This is in
stark contrast to traditional channel models with ternary feedback in which the
membership problem is strictly harder than conflict resolution. The equivalence
result also leads to a randomized lower bound for conflict resolution, which
shows a relative powerlessness of *randomization *in the beeping model. On
the other hand, we observe that *parallelization *could be particularly
powerful in Beeping Model, and our second result is to propose a novel
deterministic parallel algorithm that takes significantly less time than previous
solutions using a reasonable number of parallel channels.

In shorter version of this paper is published in the International Symposium on Distributed Computing (DISC) 2013.

}, author = {Bojun Huang and Thomas Moscibroda}, booktitle = {International Symposium on Distributed Computing (DISC) 2013}, month = {October}, title = {Conflict Resolution and Membership Problem in Beeping Model}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=200256}, year = {2013}, }