PAN

Jun Luo, Jean‐Pierre Hubaux, Patrick Eugster2003 · DOI

TL;DR

This paper introduces PAN, a novel system for reliable data storage in mobile ad hoc networks (MANETs) that leverages probabilistic quorum systems and a gossip-based diffusion mechanism. PAN aims to provide high data availability in dynamic network environments with reduced overhead compared to traditional approaches, offering a tunable trade-off between reliability and efficiency.

What Problem Does This Paper Address?

In mobile ad hoc networks (MANETs), maintaining reliable data storage is a significant challenge due to the constantly changing and unpredictable network topology. Traditional distributed systems often rely on strict consistency models and synchronized replicas, which are too costly and complex to implement in dynamic MANETs. While probabilistic approaches offer promise, directly applying existing quorum systems to MANETs is difficult due to their reliance on stable network structures and often symmetric quorum designs. This paper addresses the need for a robust, efficient, and adaptable data storage solution specifically tailored for the unique characteristics of MANETs, focusing on making small data objects highly available at a reasonable cost.

Methods

The core of PAN is a probabilistic quorum system designed for MANETs. Key methodological innovations include:

  • Gossip-Based Diffusion: Instead of relying on explicit multicast or unicast to all members of a quorum, PAN uses a gossip-based diffusion mechanism for update dissemination. This makes the system more resilient to individual link failures and node mobility, as information spreads probabilistically.
  • Asymmetric Quorum Construction: Unlike traditional quorum systems that often use symmetric quorums (same size for read and write), PAN employs an asymmetric approach. This allows for fine-tuning the sizes of read and write quorums to match application-specific needs, such as higher query rates than update rates, leading to better efficiency.
  • Topology-Awareness: PAN incorporates heuristics to make its protocols aware of network topology. For instance, when diffusing updates, servers can prioritize "nearer" nodes based on routing path lengths, reducing overall network load.
  • Probabilistic Quorum System Design: The paper adapts the principles of probabilistic quorum systems, where quorum intersections are governed by probabilities rather than strict rules, making them more suitable for dynamic environments.

Datasets

Not discussed in the paper. The evaluation relies on simulations using the ns-2 simulator.

Key Insights and Ideas

  • Gossip is Key for MANET Reliability: The paper demonstrates that a gossip-based approach is a natural fit for achieving reliable data dissemination in MANETs, where direct communication paths are unreliable and constantly changing.
  • Asymmetry is Essential for Efficiency: The ability to use different quorum sizes for reads and writes is crucial for optimizing performance in applications with varying access patterns, a common scenario in MANETs.
  • Tunability is Paramount: PAN's design allows for flexible parameter tuning (e.g., quorum sizes, fanout) to achieve a desired balance between reliability and network load, making it adaptable to diverse application requirements.
  • Predictability is Achievable: Despite the inherent dynamism of MANETs, the paper shows that the performance of PAN (reliability and network load) can be analytically predicted, which is vital for system design and management.

Key Results

  • High Reliability: PAN achieves high data reliability, even in dynamic network conditions with frequent topology changes. The "optimistic" reliability metric, which considers a query successful if it retrieves a recent, though not necessarily the absolute latest, update, is consistently high.
  • Reduced Network Load: The gossip-based diffusion and topology-aware optimizations significantly reduce network overhead (measured in message-hops per second) compared to non-optimized versions. The optimized PAN shows up to a 20% reduction in network load.
  • Analytical Model Validation: The paper presents an analytical model for predicting PAN's performance. Simulation results largely validate the model's predictions for reliability, while network load predictions are noted as being rougher but still indicative of trends.
  • Adaptability: Simulations show that PAN can be tuned to adapt to different application environments, such as those with higher update rates or varying server availability. For instance, adjusting quorum parameters can reduce network load with minimal impact on reliability.

Limitations and Future Work

  • Analytical Model for Network Load: The analytical model for network load is acknowledged as being "rough" due to factors like packet drops and stale routing information. Future work aims to improve this model.
  • Server Unavailability Impact: While the paper investigates server unavailability, it notes that the impact is more pronounced at higher node speeds.
  • Future Work: The authors suggest further research into improving the analytical model, exploring random graph theory for analysis, and investigating PAN's performance under different access rates. They also propose exploring how PAN can adapt to changes in access rates and investigating the potential of using server "silence" (not replying even if alive) to reduce collisions and improve reliability.

Summary updated

Abstract

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 probabilistic 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.
BibTeX
@misc{luo2003pan,
  author = {Jun Luo and Jean‐Pierre Hubaux and Patrick Eugster},
  title = {{PAN}},
  year = {2003},
  doi = {10.1145/778416.778417},
}
Figure