PAN: Providing Reliable Storage in Mobile Ad Hoc Networks with Probabilistic Quorum Systems

摘要

Reliable storage of data with concurrent read/write accesses (or query/update) is an ever recurring issue in distributed settings. In mobile ad hoc networks, the problem becomes even more challenging due to highly dynamic and unpredictable topology changes. It is precisely this unpredictability that makes probabilistic protocols very appealing for such environments. Inspired by the principles of probabilistie quorum systems, we present a Probabilistic quorum system for Ad hoc Networks (PAN), a collection of protocols for the reliable storage of data in mobile ad hoc networks. Our system behaves in a predictable way due to the gossip-based diffusion mechanism applied for quorum accesses, and the protocol overhead is reduced by adopting an asymmetric quorum construction. We present an analysis of our PAN system, in terms of both reliability and overhead, which can be used to fine tune protocol parameters to obtain the desired tradeoff between efficiency and fault tolerance. We confirm the predictability and tunability of PAN through simulations with ns-2.