Massively Replicating Services in Wide-Area Networks

One-line summary: Peer-peer anti-entropy using a logical topology of replicas for services overlaid on the physical topology. Intra-cluster "broadcast", inter-cluster communication between "representatives".

Overview/Main Points

• Organize a wide area network into replication clusters for a service, by overlaying a logical topology onto the nodes.
• Simulated annealing is used to find a minimum-cost (weighted sume of diameter and edges) k-connected undirected graph. (Optimal algorithm is NP-complete.) The redundancy constraint is expressed as a lower bound on the redundancy between any pair of nodes.
• Authors extend Steiglitz's algorithm for finding a low-cost k-connected graph with lower-bounded redundancy: they impose an upper bound on node degree as well as a lower bound, in order to distribute work fairly among nodes and limit the amount of update duplicates.
• Peer-to-peer anti-entropy is used to exchange updates. Within replication clusters, updates are "flooded" (logical multicast; can exploit reliable physical multicast if available, but doesn't rely on it). Between replication clusters, representative individual replicas exchange updates.