*Back to index*
#
Massively Replicating Services in Wide-Area Networks

**
Peter B. Danzig, Dante DeLucia, Katia Obraczka, USC
**
**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.

*Back to index*