Can Uncoordinated Beeps tell Stories?

The beeping model is an extremely restrictive communication model. Nodes communicate in discrete rounds using beeps---simple bursts of energy---and carrier sensing. Simultaneous beeps produce (nondestructive) collisions, resulting in information loss. Such communication differs greatly from the traditional communication mechanisms in distributed systems, like message-passing or shared memory. Indeed, a beep is a unary signal that communicates no information (e.g., no message content, nor sender information) beyond its own presence. As a result, in a round of beeping communication, hearing a beep means only that some (unknown) neighboring node is communicating in this very round, whereas silence (i.e., hearing no beeps) means only that no neighboring node is communicating.

Most previous works assume that nodes all start (wake up) at the same time. In this (synchronous starts) setting nodes have synchronized local clocks and thus synchronized round numbers. Via these round numbers, information can be extrinsically conveyed in a round of beeping communication. For example, the parity of the round number allows to convey letters in {0, 1}. In contrast, we consider here that nodes start in an uncoordinated manner. Thus two nodes may have arbitrarily different round numbers and no information can be extrinsically conveyed in a single round. In the present paper, we show how non-trivial information---e.g., letters from a binary alphabet---can be conveyed through several rounds instead. Applying tools from coding theory and additive number theory, we propose communication schemes---binary words of length l specifying how a node communicates during l consecutive rounds---allowing nodes to convey letters from an alphabet of size h, for any constant h ≥ 2 (known by all nodes). Direct application of such schemes allows to implement a message-passing primitive with an exponential (in the number of message bits) multiplicative overhead. Here, in contrast, we design an exponentially more efficient message-passing primitive.

First, we use these communication schemes to implement a 2-hop beep communication primitive, simulating beeping communication on the square of the communication graph. Building upon this primitive, we present the first solution to the 2-hop desynchronization problem in the beeping model with uncoordinated starts. This is a fundamental interference control problem, in which nodes must compute (periodic) infinite communication schemes, disjoint from those chosen by the nodes at distance one and two on the communication graph (thus, the schemes are said to be 2-hop desynchronized). That way, nodes may communicate while avoiding collisions and information loss. Finally, we show how nodes can use these 2-hop desynchronized schemes to simulate a convenient, general (i.e., not limited to any predefined alphabet size h) and efficient (i.e., with an overhead linear in the number of bits of the message) message-passing abstraction layer.