Efficient Reconciliation and Flow Control
for Anti-Entropy Protocols
Robbert van Renesse
∗
Dan Dumitriu
†
Valient Gough Chris Thomas
Amazon.com, Seattle
ABSTRACT
The paper shows that anti-entropy protocols can process
only a limited rate of updates, and proposes and evaluates a
new state reconciliation mechanism as well as a flow control
scheme for anti-entropy protocols.
Categories and Subject Descriptors: C.2.1 [Computer-Com-
munication Networks]: Network Architecture and Design
– network communications; C.2.4 [Computer-Communic-
ation Networks]: Distributed Systems – distributed appli-
cations; D.1.3 [Programming Techniques]: Concurrent
Programming – distributed programming; D.4.4 [Operating
Systems]: Communications Management – network com-
munication; D.4.5 [Operating Systems]: Reliability – fault
tolerance;
General Terms: Algorithms, Reliability.
Additional Key Words and Phrases: Epidemics, Anti-Entropy,
Gossip, Flow Control
1. INTRODUCTION
Anti-entropy, or gossip, is an attractive way of replicating
state that does not have strong consistency requirements [3].
With few limitations, updates spread in expected time that
grows logarithmic in the number of participating hosts, even
in the face of host failures and message loss. The behavior
of update propagation is easily modeled with well-known
epidemic analysis techniques. As a result, many distributed
applications use gossip to contain various inconsistencies.
In spite of its popularity, little study has been done into
how gossip protocols behave under high update load. Gos-
sip protocols purport to deliver messages within a certain
configurable number of rounds with high probability, and
thus provide synchronous guarantees. Like any other syn-
∗
Contact author. Current address: Dept. of Comp. Sc.,
Cornell University. Email: rvr@cs.cornell.edu
†
Current address: Ballista Securities, New York.
chronous communication channel, gossip has capacity that is
limited by available bandwidth for transporting gossip data
and CPU cycles for generating and processing the gossip
messages. Under high update load, a gossip protocol may
not be able to send all updates required to reconcile differ-
ences between peers. Updates would take arbitrary time to
propagate as the gossip channel gets backed up.
Gossip protocols are designed to be non-invasive and have
predictable performance, and for this a designer has to fix
not only the gossip rate per participant but also the max-
imum size of gossip messages (e.g., maximum UDP packet
size). While this avoids network and CPU overload, it also
limits the capacity of the gossip channel.
This paper makes two contributions. First, it presents a
new state reconciliation mechanism that is designed both for
minimal CPU overhead and for situations in which only lim-
ited bandwidth is available (Section 3). Second, it proposes
and analyzes a flow control scheme for gossip (Section 4).
Related work is discussed in Section 5.
2. GOSSIP BASICS
There are two classes of gossip: anti-entropy and rumor-
mongering protocols. Anti-entropy protocols gossip infor-
mation until it is made obsolete by newer information, and
are useful for reliably sharing information among a group of
participants. Rumor-mongering has participants gossip in-
formation for some amount of time chosen sufficiently high
so that with high likelihood all participants receive the in-
formation. In this paper, we shall focus on anti-entropy—
reconciliation and flow control for rumor-mongering have re-
ceived considerably attention already (see Section 5).
Let P = {p, q, ...} be a set of participants. Each participant
maintains state, which we model as a mapping σ ∈ S = K →
(V ×N ). Here K is a set of keys, V a set of values, and N an
infinite ordered set of version numbers. σ(k) = (v, n) means
that key k is mapped to value v and version n. A more
recent mapping for the same key contains a larger version
number. Both value and version number spaces contain a ⊥
element, and in case of N , ⊥ is the lowest element. Initially
all keys on all participants are mapped to (⊥, ⊥).
A participant’s state is mutable and is replicated onto all
participants. We model this as a mutable mapping µ
p
: P →
S maintained by each participant p. A participant p is only
