«Space Optimal Self-Stabilizing Token Circulation in the Local Broadcast Model».
Gabriel Le Bouder (LaBRI)
Abstract:
One specificity of wireless networks is that any message sent by some
device is received identically by all the neighbors of the emitter. In
other words, it is impossible to send any information to one specific
neighbor and not to the other. This model is therefore more challenging
that communication models assuming identified communication channels, or
even simply port-known communication.
Token Circulation is a problem in which a unique token must circulate
indefinitely in all the nodes of the network. The passing of the token
from the current token holder to one neighbor requires that this
neighbor of the token holder receives the token, and be the only
neighbor to do so. Up to today, this problem has been essentially
tackled under the port-known state-model, in which sending a message to
a unique neighbor is trivial. In the Local Broadcast State Model, the
simple sending of a token to a neighbor is a whole challenge.
We address this problem under the paradigm of Self-Stabilization, i.e.
transient-fault-robustness. We propose an algorithm that is optimal in
terms of use of memory, i.e. Θ(log log n) bits per node.