System design: Efficient Reconciliation and Flow Control for Anti-Entropy Protocols

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-Communication Networks]: Network Architecture and Design – network communications; C.2.4 [Computer-Communication Networks]: Distributed Systems – distributed applications; D.1.3 [Programming Techniques]: Concurrent Programming – distributed programming; D.4.4 [Operating Systems]: Communications Management – network communication; 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. Gossip protocols purport to deliver messages within a certain configurable number of rounds with high probability, and thus provide synchronous guarantees. Like any other synchronous 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 differences 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 maximum 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 limited 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 rumormongering protocols. Anti-entropy protocols gossip information 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 information for some amount of time chosen sufficiently high so that with high likelihood all participants receive the information. In this paper, we shall focus on anti-entropy— reconciliation and flow control for rumor-mongering have received 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 (⊥, ⊥).