Subject: Computer Science - Distributed, Parallel, and Cluster Computing
We study the multi-message broadcast problem using abstract MAC layer models of wireless networks. These models capture the key guarantees of existing MAC layers while abstracting away low-level details such as signal propagation and contention. We begin by studying upp... View more
 N. Alon, A. Bar-Noy, N. Linial, and D. Peleg. A Lower Bound for Radio Broadcast. Journal of Computer and System Sciences, 43(2):290-298, 1991.
 R. Bar-Yehuda, O. Goldreich, and A. Itai. On the Time Complexity of Broadcast in Radio Networks: an Exponential Gap Between Determinism and Randomization. In Proceedings of the International Symposium on Principles of Distributed Computing, 1987.
 Reuven Bar-Yehuda, Oded Goldreich, and Alon Itai. On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. J. Comput. Syst. Sci., 45(1):104-126, 1992.
 K. Censor-Hillel, Seth Gilbert, N. Lynch, and Calvin Newport. Structuring Unreliable Radio Networks. In Proceedings of the International Symposium on Principles of Distributed Computing, 2011.
 I. Chlamtac and S. Kutten. On broadcasting in radio networks: Problem analysis and protocol design. IEEE Transactions on Communications, 33(12):1240-1246, 1985.
 Hyun Chul Chung, Peter Robinson, and Jennifer L. Welch. Regional consecutive leader election in mobile ad-hoc networks. In Proceedings of the 6th International Workshop on Foundations of Mobile Computing, pages 81-90, 2010.
 Hyun Chul Chung, Peter Robinson, and Jennifer L. Welch. Optimal regional consecutive leader election in mobile ad-hoc networks. In Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, FOMC '11, pages 52-61, 2011.
 A. E. F. Clementi, A. Monti, and R. Silvestri. Round Robin is Optimal for Fault-Tolerant Broadcasting on Wireless Networks. Journal of Parallel and Distributed Computing, 64(1):89- 96, 2004.
 Alejandro Cornejo, Nancy Lynch, Saira Viqar, and Jennifer L Welch. Neighbor Discovery in Mobile Ad Hoc Networks Using an Abstract MAC Layer. In Annual Allerton Conference on Communication, Control, and Computing, 2009.
 E. Kushilevitz and Y. Mansour. An O(Dlog(N/D)) lower bound for broadcast in radio networks. In Proceedings of the International Symposium on Principles of Distributed Computing, pages 65-74, 1993.