Abstract

Self-organized collaborative applications in terrains with no infrastructure support for untethered communication are long known to be feasible only with the mobile ad-hoc networking (MANET) technology. Supporting collaboration however requires a solution to the consensus problem, using which collaborating users with different initial opinions can decide identically. 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, beginning with formulating a MANET liveness property and deriving two foundational results that would guide the protocol design. The protocol performance is then studied through simulations for a range of node speeds and network densities. The one with the least overhead among them is used to host a known, randomized consensus protocol as a broadcast application. The consensus overhead and the latency are found to be surprisingly small even when each node has distinct initial opinion. The underlying reason is attributed to the specific characteristics of MANETs and the features of the broadcast protocol.

Keywords

Crash-tolerance, Ad-hoc networking, Partitions and Connectedness, Broadcasting, Consensus.