Multi-message broadcast with abstract MAC layers and unreliable links

Preprint, Article English OPEN
Ghaffari, Mohsen; Kantor, Erez; Lynch, Nancy; Newport, Calvin;
(2014)
  • Publisher: Association for Computing Machinery (ACM)
  • Related identifiers: doi: 10.1145/2611462.2611492
  • 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
  • References (13)
    13 references, page 1 of 2

    [1] 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.

    [2] 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.

    [3] 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.

    [4] 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.

    [5] I. Chlamtac and S. Kutten. On broadcasting in radio networks: Problem analysis and protocol design. IEEE Transactions on Communications, 33(12):1240-1246, 1985.

    [6] 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.

    [7] 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.

    [8] 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.

    [9] 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.

    [31] 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.

  • Related Organizations (6)
  • Bioentities (1)
    1the Protein Data Bank
  • Metrics