Beeping a Deterministic Time-Optimal Leader Election

Report, Other literature type English OPEN
Dufoulon, Fabien; Burman, Janna; Beauquier, Joffroy;
  • Publisher: HAL CCSD
  • Identifiers: doi: 10.4230/lipics.disc.2018.20
  • Subject: leader election | ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.4: Distributed Systems | beeping model | Computer Science | distributed algorithms | time complexity | ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems | wireless networks | [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] | deterministic algorithms | [ INFO.INFO-DC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]

The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we solve the leader election problem with an asymptotically optimal round complexity of O(D + log n), for a network of unknown size n and unkn... View more
  • References (21)
    21 references, page 1 of 3

    Y. Afek, N. Alon, Z. Bar-Joseph, A. Cornejo, B. Haeupler, and F. Kuhn. Beeping a maximal independent set. Distributed Computing, 26(4):195-208, Aug 2013.

    D. Alistarh, A. Cornejo, M. Ghaffari, and N. Lynch. Firefly synchronization with asynchronous wake-up. In Workshop on Biological Distributed Algorithms, 2014.

    J. Beauquier, J. Burman, F. Dufoulon, and S. Kutten. Fast Beeping Protocols for Deterministic MIS and (Δ+1)-Coloring in Sparse Graphs (Extended Version). Technical report.


    J. Beauquier, J. Burman, F. Dufoulon, and S. Kutten. Fast Beeping Protocols for Deterministic MIS and (Δ+1)-Coloring in Sparse Graphs. In IEEE INFOCOM, 2018, to appear.

    A. Casteigts, Y. Métivier, J. M. Robson, and A. Zemmari. Design Patterns in Beeping Algorithms. In OPODIS, pages 15:1-15:16, 2016.

    A. Casteigts, Y. Métivier, J.M. Robson, and A. Zemmari. Deterministic leader election in O(D + log n) time with messages of size O(1). In DISC, pages 16-28, 2016.

    I. Chlamtac and S. Kutten. On broadcasting in radio networks - problem analysis and protocol design. IEEE Transactions on Communications, 33(12):1240-1246, December 1985. doi:10.1109/TCOM.1985.1096245.

    A. Cornejo and F. Kuhn. Deploying wireless networks with beeps. In DISC, pages 148-162, 2010.

    A. Czumaj and P. Davies. Optimal leader election in multi-hop radio networks. ArXiv e-prints, May 2015. arXiv:1505.06149.

  • Similar Research Results (1)
  • Related Organizations (1)
  • Metrics
Share - Bookmark