The Wakeup Problem in Synchronous Broadcast Systems SIAM Journal on Discrete Mathematics Volume 14, Number 2 pp. The Wakeup Problem in Synchronous Broadcast Systems Leszek Gasieniec, Andrzej Pelc, David Peleg Abstract. 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 n processors of a completely connected broadcast system.
Some processors wake up spontaneously, while others have to be woken up.
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.