Leader Election in Sparse Dynamic Networks with Churn

REFERENCES

• H. H. Abu-Amara. “Fault-Tolerant Distributed Algorithm for Election in Complete Networks.” IEEE Trans. Comput. 37:4 (1988), 449–453.
   Web of Science ®Google Scholar
• Y. Afek and A. Bremler. “Self-Stabilizing Unidirectional Network Algorithms by Power-Supply.” In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, (SODA ’97), pp. 111–120. New York, NY: ACM, 1997.
   Google Scholar
• J. Augustine, T. Kulkarni, P. Nakhe, and P. Robinson. “Robust Leader Election in a Fast-Changing World.” In Proceedings Ninth International Workshop on Foundations of Mobile Computing, (FOMC’13), Israel, 2013.
   Google Scholar
• J. Augustine, A. R. Molla, E. Morsy, G. Pandurangan, P. Robinson, and E. Upfal. “Storage and Search in Dynamic Peer-to-Peer Networks.” In Proceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’13), pp. 53–62. New York, NY: ACM, 2013.
   Google Scholar
• J. Augustine, G. Pandurangan, and P. Robinson. “Fast Byzantine Agreement in Dynamic Networks.” In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC’13), pp. 74–83. New York, NY: ACM, 2013.
   Google Scholar
• J. Augustine, G. Pandurangan, P. Robinson, and E. Upfal. “Towards Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks.” In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA’12). New York, NY: ACM, 2012.
   Google Scholar
• A. Boukerche and K. Abrougui. “An Efficient Leader Election Protocol for Mobile Networks.” In Proceedings of the 2006 International Conference on Wireless Communications and Mobile Computing (IWCMC ’06), pp. 1129–1134. Vancouver, British Columbia, Canada: ACM, 2006.
   Google Scholar
• H. C. Chung, P. Robinson, and J. L. Welch. “Regional Consecutive Leader Election in Mobile Ad-hoc Networks.” In Proceedings of the 6th International Workshop on Foundations of Mobile Computing (DIALM-POMC ’10), pp. 81–90. New York, NY, USA: ACM, 2010.
   Google Scholar
• H. C. Chung, P. Robinson, and J. 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), pp. 52–61. New York, NY: ACM, 2011.
   Google Scholar
• A. K. Datta, L. L. Larmore, and H. Piniganti. “Self-Stabilizing Leader Election in Dynamic Networks.” In Proceedings of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems of (SSS’10), pp. 35–49. New York, NY: Springer, 2010.
   Google Scholar
• E. W. Dijkstra. “Self-Stabilizing Systems in Spite of Distributed Control.” Commun. ACM 17:11 (1974), 643–644.
   Web of Science ®Google Scholar
• S. Dolev. Self-Stabilization. Cambridge, MA: MIT Press, 2000.
   Google Scholar
• C. Dwork, D. Peleg, N. Pippenger, and E. Upfal. “Fault Tolerance in Networks of Bounded Degree.” SIAM J. Comput. 17:5 (1988), 975–988.
   Web of Science ®Google Scholar
• H. Garcia-Molina. “Elections in a Distributed Computing System.” IEEE Trans. Comput. 31:1 (1982), 48–59.
   Web of Science ®Google Scholar
• K. Hatzis, G. Pentaris, P. Spirakis, V. Tampakis, and R. Tan. “Fundamental control algorithms in mobile networks.” In Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’09), pp. 251–260. New York, NY: ACM, 1999.
   Google Scholar
• R. Ingram, P. Shields, J. Walter, and J. L. Welch. “An Asynchronous Leader Election Algorithm for Dynamic Networks.” In Proceedings of 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS’09), pp. 1–12. IEEE, 2009.
   Google Scholar
• A. Itai, S. Kutten, Y. Wolfstahl, and S. Zaks. “Optimal Distributed t-Resilient Election in Complete Networks.” Software Engineering, IEEE Transactions on 16:4 (1990), 415–420.
   Web of Science ®Google Scholar
• B. M. Kapron, D. Kempe, V. King, J. Saia, and V. Sanwalani. “Fast Asynchronous Byzantine Agreement and Leader Election with Full Information.” ACM Transactions on Algorithms 6:4 (2010).
   Web of Science ®Google Scholar
• V. King and J. Saia. “Breaking the O(n2) Bit Barrier: Scalable Byzantine Agreement with an Adaptive Adversary.” J. ACM 58:18 (2011), 1–24.
   Web of Science ®Google Scholar
• V. King, J. Saia, V. Sanwalani, and E. Vee. “Towards Secure and Scalable Computation in Peer-to-Peer Networks.” In Procceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 87–98. IEEE, 2006.
   Google Scholar
• F. Kuhn and R. Oshman. “Dynamic Networks: Models and Algorithms.” SIGACT News 42:1 (2011), 82–96.
   Google Scholar
• F. Kuhn, N. Lynch, and R. Oshman. “Distributed Computation in Dynamic Networks.” In Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC’10), pp. 513–522. New York, NY: ACM, 2010.
   Google Scholar
• L. Lamport, R. Shostak, and M. Pease. “The Byzantine Generals Problem.” ACM Trans. Program. Lang. Syst. 4:3 (1982), 382–401.
   Web of Science ®Google Scholar
• N. Malpani, J. L. Welch, and N. Vaidya. “Leader Election Algorithms for Mobile Ad Hoc Networks.” In Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM’00), pp. 96–104. Boston, MA: ACM, 2000.
   Google Scholar
• S. Masum, A. Ali, and M. Bhuiyan. “Fundamental Control Algorithms in Mobile Networks.” In Procceedings of the 20th International Conference on Advanced Information Networking and Applications AINA’06, pp. 29–34. Vienna, Austria: IEEE Computer Society, 2006.
   Google Scholar
• P. Parvathipuram, V. Kumar, and G.-C. Yang. “An Efficient Leader Election Algorithm for Mobile Ad Hoc Networks.” In Proceedings of the 1st International Conference on Distributed Computing and Internet Technology, (ICDCIT’04), pp. 32–41. Bhubaneswar, India: Springer, 2004.
   Google Scholar
• M. Pease, R. Shostak, and L. Lamport. “Reaching Agreement in the Presence of Faults.” J. ACM 27:2 (1980), 228–234.
   Web of Science ®Google Scholar
• D. Peleg. “Time-Optimal Leader Election in General Networks.” J. Parallel Distrib. Comput. 8:1 (1990), 96–99.
   Web of Science ®Google Scholar
• D. Stutzbach and R. Rejaie. “Understanding Churn in Peer-to-Peer networks.” In Proceedings of the 6th ACM SIGCOMM Conference on Internet Measurement, IMC ’06, pp. 189–202. New York, NY: ACM, 2006.
   Google Scholar
• E. Upfal. “Tolerating a Linear Number of Faults in Networks of Bounded Degree.” Inf. Comput. 115:2 (1994), 312–320.
   Web of Science ®Google Scholar
• S. Vasudevan, J. Kurose, and D. Towsley. “Design and Analysis of a Leader Election Algorithm for Mobile Ad Hoc Networks.” In Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP’04), pp. 350–360. IEEE, 2004.
   Google Scholar