Consensus in Sparse, Mobile Ad Hoc Networks

• Published in: IEEE transactions on parallel and distributed systems 2012-03, Vol.23 (3), p.467-474
• Main Authors: Alekeish, K., Ezhilchelvan, P.
• Format: Article
• Language: English
• Subjects: Ad hoc networks; Computer crashes; consensus; coverage assurance; crash tolerance; Manet; Mobile communication; Multicast protocols; network density; Nickel; node connectivity; quiescent multicasting; Wireless communication
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/TPDS.2011.182

Consensus is central to several applications including collaborative ones which a wireless ad hoc network can facilitate for mobile users in terrains with no infrastructure support for communication. We solve the consensus problem in a sparse network in which a node can at times have no other node in its wireless range and useful end-to-end connectivity between nodes can just be a temporary feature that emerges at arbitrary intervals of time for any given node pair. Efficient one-to-many dissemination, essential for consensus, now becomes a challenge; enough number of destinations cannot deliver a multicast unless nodes retain the multicast message for exercising opportunistic forwarding. Seeking to keep storage and bandwidth costs low, we propose two protocols. An eventually relinquishing (◇ RC) protocol that does not store messages for long is used for attempting at consensus, and an eventually quiescent (◇ QC) one that stops forwarding messages after a while is used for concluding consensus. Use of the ◇ RC protocol poses additional challenges for consensus, when the fraction, f/n, of nodes that can crash is 1/4 ≤ f/n