The wakeup problem in synchronous broadcast systems (extended abstract)

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.

REFERENCES

• 1: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.98-108, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41849]
• 4: I. Chlamtac and S. Kutten, On Broadcasting in Radio Networks- Problem Analysis and Protocol Design, IEEE Trans. on Comm un. 33, (1985).
• 5: I. Chlamtac , S. Kutten, Tree-based broadcasting in multihop radio networks, IEEE Transactions on Computers, v.36 n.10, p.1209-1223, Oct. 1987 [doi>10.1109/TC.1987.1676861]
• 6: I. Chlamtac and S. Kutten, A Spatial Reuse TDMA/FDMA for Mobile Multi-hop Radio Networks, Proc. IEEE INFOCOM, 1985, Washington DC, pp. 389-394.
• 7: I. Chlamtac and O. Weinstein, The Wave Expansion Approach to Broadcasting in Multihop Radio Networks, Proc. INFOCOM, 1987.
• 8: Bogdan S. Chlebus , Leszek Gąsieniec , Alan Gibbons , Andrzej Pelc , Wojciech Rytter, Deterministic broadcasting in unknown radio networks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.861-870, January 09-11, 2000, San Francisco, California, United States
• 9: Krzysztof Diks , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, The Impact of Knowledge on Broadcasting Time in Radio Networks, Proceedings of the 7th Annual European Symposium on Algorithms, p.41-52, July 16-18, 1999
• 10: S. Even and S. Rajsbaum, Unison, canon, and sluggish clocks in networks controlled by a synchronizer, Mathematical Systems Theory 28, (1995), 421-435.
• 11: Faith E. Fich , Russell Impagliazzo , Bruce Kapron , Valerie King , Mirosław Kutyłowski, Limits on the power of parallel random access machines with weak forms of write conflict resolution, Journal of Computer and System Sciences, v.53 n.1, p.104-111, Aug. 1996 [doi>10.1006/jcss.1996.0052 ]
• 12: Michael J. Fischer , Shlomo Moran , Steven Rudich , Gadi Taubenfeld, The Wakeup Problem, SIAM Journal on Computing, v.25 n.6, p.1332-1357, Dec. 1996 [doi>10.1137/S0097539793254959]
• 13: J. Hastad , T. Leighton , B. Rogoff, Analysis of backoff protocols for multiple access channels, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.241-253, January 1987, New York, New York, United States [doi>10.1145/28395.28422]
• 14: Albert G. Greenberg , Philippe Flajolet , Richard E. Ladner, Estimating the multiplicities of conflicts to speed their resolution in multiple access channels, Journal of the ACM (JACM), v.34 n.2, p.289-325, April 1987 [doi>10.1145/23005.23006]
• 15: J Goodman , A G Greenberg , N Madras , P March, On the stability of the Ethernet, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.379-387, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22187]
• 16: I. Gitman, R. M. Van Slyke and H. Frank, Routing in Packet-Switching Broadcast Radio Networks, IEEE Trans. on Commun., (1976), 926-930.
• 17: R. E. Kahn, S. A. Gronemeyer, J. Burchfiel and R. C. Kunzelman, Advances in Packet Radio Technology, Proc. IEEE 66, (1978).
• 18: R. C. Kunzelman, Overview of the ARPA Packet Radio Experimental Network, Proc. COMPCON, 1978, pp. 157-160.
• 19: Eyal Kushilevitz , Yishay Mansour, Computation in noisy radio networks, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.236-243, January 25-27, 1998, San Francisco, California, United States
• 20: Jacques Mazoyer, On optimal solutions to the firing squad synchronization problem, Theoretical Computer Science, v.168 n.2, p.367-404, Nov. 20, 1996 [doi>10.1016/S0304-3975(96)00084-9 ]
• 21: N. Shacham and E. J. Craighill, Dynamic Routing for Real-Time Transport in Packet Radio Networks, Proc. INFOCOM, 1982.
• 22: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Theory, Verification