The Wakeup Problem in Synchronous Broadcast Systems
Leszek Gasieniec, Andrzej Pelc and David Peleg
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
This paper studies the differences between two levels of synchronization
in a distributed broadcast system (or a multiple access channel). In the
globally synchronous model, all processors have access to a global clock.
In the locally synchronous model, processors have local clocks ticking
at the same rate, but each clock starts individually, when the processor
wakes up. We consider the fundamental problem of waking up all of n processors
of a completely connected broadcast system. Some processors wake up spontaneously,
while others have to be woken up. Only wake processors can send messages;
a sleeping processor is woken up upon hearing a message. The processors
hear a message in a given round if and only if exactly one processor sends
a message in that round. Our goal is to wake up all processors as fast
as possible in the worst case, assuming an adversary controls which processors
wake up and when. We analyze the problem in both the globally synchronous
and locally synchronous models, with or without the assumption that n is
known to the processors. We propose randomized and deterministic algorithms
for the problem, as well as lower bounds in some of the cases. These bounds
establish a gap between the globally synchronous and locally synchronous
models.