Design and performance-study of crash-tolerant protocols for broadcasting and reaching consensus in MANETs

The mobile ad-hoc networking (MANET) technology offers an ideal medium for hosting self-organized collaborative applications in terrains with no infrastructure support for untethered communication. Collaboration involves users with potentially different initial opinions deciding identically, i.e., reaching consensus. Efficient consensus solutions require efficient broadcast support. This paper presents four crash-tolerant broadcast protocols which are designed (i) to provide the maximum broadcast coverage that can ever be guaranteed, and (ii) to suit a wide range of MANET types: from a connected MANET (no partitions) to intermittently disconnected one (partitions occurring rarely and healing swiftly) to an intermittently connected one (partitions taking longer to heal and re-appearing swiftly). The resulting design challenges are addressed systematically, presenting two foundational results that would guide the protocol design. The protocols´ performance is then studied through simulations for a range of node speeds and network densities. The best-performing one is used to host a consensus protocol as its ´application´. The overhead and the latency for reaching consensus are measured; surprisingly, they are hardly affected as the number of nodes with distinct initial opinions increases beyond one.