Efficient Synchronization of Replicated Data in Distributed Systems

Thorsten Schütt, Florian Schintke, Alexander ReinefeldLecture Notes in Computer Science 2003 · DOI · OpenAlex

Abstract

Maintaining consistency across massive, replicated datasets in distributed environments is a significant challenge, particularly when traditional centralized or quorum-based models fail to scale. This paper introduces nsync, a tool that leverages topology-aware hierarchical gossip algorithms and block-level updates to synchronize data across thousands of autonomous nodes. By optimizing communication rounds and respecting underlying network structures, nsync achieves high performance and logarithmic scaling for data distribution.

Introduction

In large-scale scientific collaborations, such as particle physics or earth observation, researchers generate petabytes of data that must be replicated globally to ensure low-latency access. Traditional synchronization methods often rely on a "master copy" or strict consistency models requiring a quorum of nodes to agree on updates. In "Grid" environments—characterized by autonomous nodes and heterogeneous network links—these centralized approaches create massive bottlenecks and fail to scale.

The Synchronization Challenge

The core problem addressed is how to efficiently synchronize thousands of nodes without a central authority. Existing tools often treat the network as a "black box," leading to inefficient use of slow WAN links. A scalable solution must minimize redundant data transfers and adapt to the physical network topology to avoid saturating limited bandwidth.

Methodology: The nsync Approach

nsync treats synchronization as a distributed communication problem solved via gossip algorithms. Instead of an $O(n^2)$ all-to-all communication pattern, nsync organizes data exchange into discrete rounds of node-to-node (n2n) synchronization.

Hierarchical Gossip and Topology Awareness

The system utilizes a hierarchy of network descriptions (e.g., switches, hubs, rings) to prioritize high-bandwidth local links. In each round, nodes propagate not only their own updates but also those received from others in previous rounds.

Progression of synchronization rounds in a gossip-based network.

Technical Pillars

  • Block-Level Sync: Similar to the rsync algorithm, nsync identifies and transmits only modified blocks within a file, significantly reducing bandwidth requirements for large datasets.
  • Seven-Phase Execution: The process follows a structured pipeline: Configuration, Startup, Change Detection, Planning (calculating the gossip sequence), Dry Run (parallel conflict detection), Synchronization, and Finalization.

Key Insights: Meta-Nodes and Heuristics

A critical innovation in nsync is the Meta-Node Strategy. For complex topologies, clusters of nodes are treated as a single "meta-node." Data is synchronized within a cluster first, and then a designated "proxy" node handles communication across slow links to other clusters. This prevents the same data from traversing a bottleneck multiple times.

Comparison of synchronization heuristics for cross-cluster communication.

The researchers also identified a "zigzag" effect in performance graphs, where synchronization time increases slightly more when moving from an even to an odd number of nodes due to the requirement of an additional communication round.

Experimental Evaluation

The authors evaluated nsync on a 96-node PC cluster using four scenarios:

  1. all-to-all-bigfile: A 10 MB file on every node propagated to all others.
  2. all-to-all-smallfiles: 10 MB of data split into 1,024 files.
  3. bcast-bigfile: A 10 MB file broadcast from one node to all others.
  4. bcast-smallfiles: Broadcast of 1,024 small files.

Results

  • Scalability: Broadcast scenarios demonstrated $O(\log n)$ scaling, while all-to-all scenarios scaled linearly ($O(n)$).
  • Performance: The tool successfully saturated 100 Mb full-duplex links.
  • System Bottlenecks: At high node counts (45+), performance was limited by OS-level constraints (file descriptors and memory caching) rather than the algorithm itself.

Conclusion and Future Work

nsync provides a robust framework for decentralized data synchronization. While highly effective, future work is needed to address memory overhead for metadata at extreme scales, improve congestion handling for network hubs, and integrate SSL for secure data transfer. Currently, conflict resolution remains a manual process, which may require automation in high-update environments.

Summary updated

BibTeX
@inproceedings{schutt2003efficient,
  author = {Thorsten Schütt and Florian Schintke and Alexander Reinefeld},
  title = {{Efficient Synchronization of Replicated Data in Distributed Systems}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2003},
  doi = {10.1007/3-540-44860-8\_28},
}
Figure