Asynchronous leader election and MIS using abstract MAC layer

ABSTRACT

We study leader election (LE) and computation of a maximal independent set (MIS) in wireless ad-hoc networks. We use the abstract MAC layer proposed in [14] to divorce the algorithmic complexity of solving these problems from the low-level issues of contention and collisions. We demonstrate the advantages of such a MAC layer by presenting simple asynchronous deterministic algorithms to solve LE and MIS and proving their correctness. First, we present an LE algorithm for static single-hop networks in which each process sends no more than three messages to its neighbors in the system. Next, we present an algorithm to compute an MIS in a static multi-hop network in which each process sends a constant number of messages to each of its neighbors in the communication graph.

References

1. H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. John Wiley and Sons, Inc., 2004.
2. R. Bar-Yehuda, O. Goldreich, and A. Itai. On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization. In Proc. of the 6th Annual ACM Symposium on Principles of Distributed Computing, pages 98--108, 1987.
3. J. L. Bordim, Y. Ito, and K. Nakano. Randomized leader election protocols in noisy radio networks with a single transceiver. In Proc. of the 4th International Symposium on Parallel and Distributed Processing and Applications, pages 246--256, 2006.
4. J. I. Capetanakis. Tree algorithms for packet broadcast channels. IEEE Trans. on Information Theory, 25(5):505--515, 1979.
5. A. Cornejo, N. Lynch, S. Viqar, and J. L. Jennifer L. Welch. Neighbor discovery in mobile ad hoc networks using an abstract MAC layer. In Proc. of the 47th Annual Allerton Conference on Communication, Control, and Computing, pages 1460--1467, 2009.
6. M. Ghaffari, N. Lynch, and S. Sastry. Leader election using loneliness detection. In Proc. of the 25th International Symposium on Distributed Computing, pages 268--282, 2011.
7. S. Gollakota and D. Katabi. Zigzag decoding: combating hidden terminals in wireless networks. In Proc. of the ACM SIGCOMM 2008 Conference on Data Communication, pages 159--170, 2008.
8. R. Ingram, P. Shields, J. Walter, and J. L. Welch. An asynchronous leader election algorithm for dynamic networks. In Proc. of the 23rd IEEE International Parallel and Distributed Processing Symposium, 2009.
9. T. Jurdziński, M. Kutylowski, and J. Zatopiański. Efficient algorithms for leader election in radio networks. In Proc. of the 21st Annual Symposium on Principles of Distributed Computing, pages 51--57, 2002.
10. M. Khabbazian, F. Kuhn, D. R. Kowalski, and N. Lynch. Decomposing broadcast algorithms using abstract MAC layers. In Proc. of the 6th International Workshop on Foundations of Mobile Computing, pages 13--22, 2010.
11. M. Khabbazian, F. Kuhn, N. Lynch, M. Medard, and A. P. Gheibi. MAC design for analog network coding. In Proc. of the 7th ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, pages 42--51, 2011.
12. D. Kowalski and A. Pelc. Broadcasting in undirected ad hoc radio networks. Distributed Computing, 18(1), 2005.
13. D. Kowalski and A. Pelc. Leader election in ad hoc radio networks: A keen ear helps. In Proc. of the 36th International Colloquium on Automata, Languages and Programming, pages 521--533, 2009.
14. F. Kuhn, N. Lynch, and C. Newport. The abstract MAC layer. In Proc. of the 23rd International Conference on Distributed Computing, pages 48--62, 2009.
15. F. Kuhn, N. Lynch, and C. Newport. The abstract MAC layer. Technical Report MIT-CSAIL-TR-2010-040, CSAIL, MIT, 2010.
16. F. Kuhn, N. Lynch, and C. Newport. The abstract MAC layer. Distributed Computing, 24(3):187--296, 2011.
17. F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In Proc. of the 19th International Symposium on Distributed Computing, pages 273--287, 2005.
18. N. A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.
19. T. Moscibroda and R. Wattenhofer. Maximal independent sets in radio networks. In Proc. of the 24th Annual ACM Symposium on Principles of Distributed Computing, pages 148--157, 2005.
20. K. Nakano and S. Olariu. Randomized leader election protocols in radio networks with no collision detection. In Proc. of the 11th International Conference on Algorithms and Computation, pages 362--373, 2000.
21. K. Nakano and S. Olariu. Leader election protocols for radio networks. In Handbook of wireless networks and mobile computing, pages 219--242. John Wiley & Sons, Inc., 2002.
22. K. Nakano and S. Olariu. A survey of leader election protocols for radio networks. In Proc. of the International Symposium on Parallel Architectures, Algorithms and Networks, pages 63--68, 2002.
23. K. Nakano and S. Olariu. Uniform leader election protocols for radio networks. IEEE Trans. on Parallel and Distributed Systems, 13(5), 2002.
24. J. Schneider and R. Wattenhofer. A log-star distributed maximal independent set algorithm for growth-bounded graphs. In Proc. of the 27th Symposium on the Principles of Distributed Computing, pages 35--44, 2008.
25. J. Schneider and R. Wattenhofer. What is the use of collision detection (in wireless networks)? In Proc. of the 24th International Symposium on Distributed Computing, pages 133--147, 2010.
26. J. E. Walter, J. L. Welch, and N. H. Vaidya. A mutual exclusion algorithm for ad hoc mobile networks. Wireless Networks, 7:585--600, 2001.
27. D. E. Willard. Log-logarithmic selection resolution protocols in a multiple access channel. SIAM Journal of Computing, 15:468--477, 1986.

• Software and its engineering

  • Software organization and properties

    • Software system structures