Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am reading the paper "Efficient Reconciliation and Flow Control for Anti-Entropy Protocols"! , I couldn't clearly understand Section 3.2 "Scuttlebutt Reconciliation". Here I extract out some sentences from the paper, which especially confuse me.

  1. If gossip messages were unlimited in size, then the sets contains the exact differences,just like with precise reconciliation.

  2. Scuttlebutt requires that if a certain delta (r; k; v; n) is omitted, then all the deltas with higher version numbers for the same r should be omitted as well.

  3. Scuttlebutt satises the global invariant C(p;q) for any two processes p and q:

share|improve this question
So what is the question? – Andrew Nov 8 '12 at 16:32

There's not really a question here, but I happen to have read that paper just now. I'll try to provide my interpretation.

  1. This sentence states that Scuttlebut reconciliation will not differ from precise reconciliation if there was no maximum to the size of network messages. Obviously, there is; this is the whole point of coming up with a clever reconciliation mechanism.
  2. This sentence states that there can be no gaps in the sequence of changes (deltas) that are part of a single Scuttlebut message. If a particular change is not transmitted in some message, then it is not allowed to include any change that is more recent that the omitted message. So in short: a message always contains a set of changes that are the oldest among changes not known to the peer that will receive the message.
  3. The invariant ensures that for each key k in the set of state variables, participant q either has the current value of k present at participant p, or the version number (or timestamp) of the current value at p is higher than the maximum version number of all values at p that q knows about. All in all, this has to do with the absence of gaps again.

Writing this up has made things more clearer for myself, hope it helps you :) (feel free to comment when things are still too fuzzy)

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.