Atum

Rachid Guerraoui, Anne-Marie Kermarrec, Matej Pavlovič, Dragos-Adrian Seredinschi

TL;DR

Atum is a new group communication middleware designed for large, dynamic, and potentially hostile distributed systems. It introduces "volatile groups" (vgroups) that are small, dynamic, and robust clusters of nodes, allowing for efficient Byzantine fault tolerance within groups and scalable gossip-based communication between them. This approach enables systems to handle significant churn and a notable percentage of Byzantine faults while maintaining high performance.

What Problem Does This Paper Address?

Building reliable distributed systems is challenging, especially when dealing with large-scale environments where nodes frequently join and leave (churn) and some nodes may exhibit arbitrary, malicious behavior (Byzantine faults). Traditional approaches to group communication often struggle to balance the need for robustness (e.g., through state machine replication) with the flexibility required for dynamic systems. State machine replication (SMR) typically requires groups to be stable and small for efficiency, while handling churn often involves dynamic group memberships. This paper aims to bridge this gap by providing a group communication service that is scalable, robust against Byzantine faults, and highly flexible in the face of constant churn.

Methods

Atum's core innovation is the concept of volatile groups (vgroups). These are small, dynamic clusters of nodes that execute a Byzantine Fault Tolerant (BFT) State Machine Replication (SMR) protocol. This confines individual node failures within a vgroup, masking them from the rest of the system.

To manage these vgroups and the overall system, Atum employs several key techniques:

  • Logarithmic Grouping: Vgroups are maintained at a size logarithmic to the total system size. This balances the efficiency of smaller groups with the robustness of larger ones.
  • Random Walk Shuffling: When nodes join or leave, Atum uses random walks across an overlay network to ensure that faulty nodes are evenly distributed among vgroups. This prevents the concentration of faults within a single group.
  • H-graph Overlay: Vgroups are interconnected in an H-graph overlay, which is a sparse, well-connected structure with a logarithmic diameter. This facilitates efficient communication between vgroups.
  • Gossip Protocol: Messages are disseminated between vgroups using a gossip protocol over the H-graph overlay. This ensures scalability and resilience.
  • Two Implementations: Atum is implemented in two versions: one using a synchronous SMR algorithm (SYNC) and another using an asynchronous (eventually synchronous) SMR algorithm (ASYNC). This allows for evaluation across different network assumptions.

Datasets

Not discussed in the paper. The evaluation uses simulated and real-world deployments on Amazon EC2 and Grid 5000.

Key Insights and Ideas

  • Volatile Groups as a Sweet Spot: The paper argues that by combining small, dynamic groups (vgroups) with robust protocols (SMR) and flexible overlay mechanisms (gossip, random walks), Atum achieves a desirable balance between robustness and flexibility, which is difficult to attain with traditional approaches.
  • Decoupling Intra- and Inter-Group Communication: Atum effectively separates the problem of fault tolerance within a group (handled by SMR) from the problem of scalable communication between groups (handled by gossip). This modularity simplifies design and analysis.
  • Randomness is Key for Scalability and Robustness: The use of random walks for shuffling and the H-graph overlay are crucial for distributing faults and enabling efficient message dissemination in large, dynamic systems.
  • Asynchronous vs. Synchronous Trade-offs: The evaluation highlights that while synchronous implementations offer more predictable behavior and simpler reasoning, asynchronous implementations are generally more performant, especially in wide-area network (WAN) settings where synchrony is less guaranteed.
  • Practicality of Byzantine Fault Tolerance at Scale: The results demonstrate that achieving Byzantine fault tolerance in systems with thousands of nodes and significant churn is feasible with the right architectural choices.

Key Results

  • Scalability: Atum can scale exponentially beyond 1000 nodes, disseminating messages in polylogarithmic time.
  • Churn Tolerance: The system smoothly handles up to 18% of nodes churning every minute.
  • Byzantine Fault Tolerance: Atum is impervious to arbitrary faults, tolerating 5.8% Byzantine nodes in a system of 850 nodes without performance degradation.
  • Performance:
    • Group communication latency in SYNC is comparable to classic gossip protocols, with a slight overhead due to BFT.
  • AShare (file sharing) achieves read performance comparable to NFS4, and even outperforms it for larger files when using parallel retrieval.
  • AStream (data streaming) demonstrates low latency for metadata dissemination, with the overall stream latency dependent on the underlying multicast mechanism.

Limitations and Future Work

  • Join Operation Trust: The join operation requires trusting a single contact node for initial information, which is a common prerequisite in intrusion-proof systems but could be a point of failure or trust.
  • Complexity of Interplay: The paper acknowledges the significant complexity arising from the interplay between SMR reconfiguration, overlay management, and vgroup operations like splitting and merging.
  • Future Work: The authors suggest exploring more sophisticated Byzantine fault tolerance mechanisms for specific applications and further investigating the trade-offs between different SMR protocols and overlay structures. They also mention the availability of the Atum library and applications for further research.

Summary updated

Abstract

This paper presents Atum, a group communication middleware for a large, dynamic, and hostile environment. At the heart of Atum lies the novel concept of volatile groups: small, dynamic groups of nodes, each executing a state machine replication protocol, organized in a flexible overlay. Using volatile groups, Atum scatters faulty nodes evenly among groups, and then masks each individual fault inside its group. To broadcast messages among volatile groups, Atum runs a gossip protocol across the overlay.
BibTeX
@inproceedings{guerraoui2016atum,
  author = {Rachid Guerraoui and Anne-Marie Kermarrec and Matej Pavlovič and Dragos-Adrian Seredinschi},
  title = {{Atum}},
  booktitle = {Middleware},
  year = {2016},
  url = {https://openreview.net/forum?id=8PsDTlyRtT},
}
Figure