Toggle Main Menu Toggle Search

Open Access padlockePrints

Design and Performance-Study of Crash-Tolerant Protocols for Broadcasting and Reaching Consensus in MANETs

Lookup NU author(s): Einar Vollset, Dr Paul Ezhilchelvan

Downloads


Abstract

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, beginning with formulating a MANET liveness property and deriving 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 one with the smallest overhead is used to support a known, randomized consensus protocol. The consensus overhead and the latency remain surprisingly small even as the number of nodes with distinct initial opinions increases.


Publication metadata

Author(s): Vollset E, Ezhilchelvan PD

Publication type: Report

Publication status: Published

Series Title: School of Computing Science Technical Report Series

Year: 2005

Pages: 25

Print publication date: 01/08/2005

Source Publication Date: August 2005

Report Number: 925

Institution: School of Computing Science, University of Newcastle upon Tyne

Place Published: Newcastle upon Tyne

URL: http://www.cs.ncl.ac.uk/publications/trs/papers/925.pdf


Share