Spreading by Word of Mouth — The Scholars' Coast

Where this book sits

Draws on

The Clearinghouse: A Decentralized Agent for Locating Named Objects in a Distributed EnvironmentOppen & Dalal 1981
- the name serviceThe name service whose replicas the algorithms were made to keep in step.
Grapevine: An Exercise in Distributed ComputingBirrell et al. 1982
- replication by mailA replicated registry kept up to date by mail between its servers.

This book retells

Epidemic Algorithms for Replicated Database MaintenanceDemers et al. 1987

Leads to

Eventually ConsistentVogels 2009
- eventual consistencyEventual consistency, taken as a design choice for large stores.
Conflict-Free Replicated Data TypesShapiro et al. 2011 · Changes That Never Clash
- eventual consistencyEventual consistency, reached by copies passing updates to one another.
Probabilistically Bounded Staleness for Practical Partial QuorumsBailis et al. 2012 · Probably Up to Date
- anti-entropyAnti-entropy: copies compare and exchange until all are current.

Each link is an idea one paper took from another. Point at one, or tap it, to read how.

a paper this book retells a paper retold in another book a paper outside the series

First, in machine terms

One update, many replicas

A database is copied at many sites. An update is made at one of them, and every other site should end up holding it, with no site in charge.

Direct mail is quick, but messages are lost and the sender may not know every site.
Anti-entropy: each site regularly picks another at random and the two reconcile their whole copies. It reaches everyone, slowly.
Rumor mongering (Demers et al., 1987): a site passes fresh news to random peers until it goes stale. It is quick and cheap and leaves a small fraction never told, which anti-entropy then catches.

We tell it with the libraries of a coast, scholars who talk in a colonnade, and a yearly festival.

Thirty replicas one update

One replica holds the update. Mail it to the rest, then let pairs reconcile.

The scholars' coast

Many libraries, no one in charge

The coast is a string of small libraries, each keeping its own copies of the same works. Nothing here waits for a vote, and a library answers its readers from whatever it holds.^*

The larger tally winsEvery edition carries the day and hour it was written. Of two editions of a work, a library keeps the later.

No one in chargeNobody knows what every library holds, and nobody sees that news arrives.

Old for a whileWhile news travels, some shelves hold the old edition. The aim is to bring that to an end.

What has to travel

One scrap, many shelves

Each library's copy of a work is an edition, and every edition carries a tally: the day and hour by the sun at which it was written, with the number of the library that wrote it to break a tie.

What travels is short: one learning under a title, on a scrap of papyrus. Demerios, at one library, corrects The Order of the Heavens to say that the Earth goes round the Sun. The new edition's tally is later than any other on that work.

Writing a new edition at one's own library is the one thing a scholar may do. Nothing else changes a shelf except receiving someone else's edition. Every library should in the end hold Demerios's edition, or a newer one.

What follows is the plain habits by which it gets there, how quickly each works, what each costs in walking and carrying, and what each leaves over.

A small library of weathered plaster on a base of dressed stone, with a porch of two plain columns under a pediment and a tiled roof; a reader in grey stands on the porch with a scroll open in his hands, racks of scrolls show through the open door, and the sea lies beyond the olive trees

The simplest habit

Letters to everyone

A scholar who has written a new edition can copy it onto a slip for every other library and send a courier to each. A library that receives the slip keeps whichever tally is larger.

While the coast was small that was enough. Three things go wrong with it.

What goes wrong

A courier is lost

The courier is lost or late, or the slip is dropped in a ditch, and the library never hears.

What goes wrong

A library is not on the list

A new library has opened since the writer's list was made, or one was forgotten. It gets no slip.

What goes wrong

One library does all the work

The writer copies and sends a slip for every other library, however many there are.

Nobody notices when a slip goes astray. The library that missed it does not know there was one, and the writer does not know it was missed. On a coast of hundreds, nobody could chase such misses by hand.

The habit that misses no one

The festival

Once a year the copyists of the coast come to the festival ground, where long stone tables stand in rows below the stoa.

Each copyist draws by lot the name of one library, goes to its copyist, and the two sit down opposite each other with their whole collections. Some names are drawn two or three times, some not at all.

The pair go through the scrolls work by work. Wherever they hold different editions, the one with the smaller tally takes the other's.

Three ways to sit

Giving

The copyist with the newer edition gives it to the other, and takes nothing back.

Three ways to sit

Asking

The copyist with the older edition asks for the newer one.

Three ways to sit

Both

Each gives and each asks, so after the table both hold the newer edition, whichever had it.

One hundred libraries hold the festival, year after year

At each table

0festivals held1hold the new edition

One library holds the new edition. Every copyist draws one name by lot.

It never fails

Every copyist has some chance of being paired with every other

So a library that holds a new edition will in time sit with any library that lacks it, and the older edition gives way. The lot needs no couriers and no list: only the libraries that come. Doubling the coast adds only a fixed handful of festivals to the wait.

Proof · that anti-entropy with every pair possible reaches every site with probability 1

Let S be the set of sites. Suppose that for every pair s, s′ in S the probability that s chooses s′ as partner in a cycle is at least some q > 0. Claim. Every site comes to hold the value with the largest timestamp, with probability 1. For the number of cycles the paper quotes Pittel: about log₂ n + ln n for push, which this book takes on the paper's word.

This is the paper's argument of §3.2, set out. Let S be the set of sites, and suppose that for every pair s, s′ in S the probability that s chooses s′ as partner in a cycle is at least some q > 0.
Let s₀ be a site holding the entry with the largest timestamp t, and let s be any site holding an older value. In any cycle, the probability that s chooses s₀ is at least q.
If s chooses s₀, then whichever of push, pull or push-pull is in use, ResolveDifference leaves s with a value of timestamp at least t, since the value with the smaller timestamp is replaced by the one with the larger, and none is larger than t. (With push alone the same holds in the cycle in which s₀ chooses s.)
The probability that s has not chosen s₀ in c cycles is at most (1 − q)^c, which tends to 0 as c grows. Since there are finitely many sites, the probability that some site still holds an older value tends to 0.∎

The last few libraries

When few remain, asking beats giving

Suppose the news has already reached nearly everyone, and only a few libraries still lack it.

A library that lacks the edition and asks is told at once by any partner who has it. A library that waits to be given it gets it only if a partner happens to draw its name. So with asking, the share of libraries without the news falls as the square of itself at every festival. With giving it shrinks by about the same factor each time, a little over a third. Doing both behaves like asking.

One library in ten lacks the news worked out from the two rules, for a coast of a thousand libraries

The page works these out; it does not run a festival for them.

Proof · that pull squares the susceptible fraction and push only scales it

Let p_i be the probability that a site is still susceptible (has not received the update) after the ith cycle, n the number of sites, with partners chosen uniformly. Claim. With pull, p_i+1 = p_i²; with push, p_i+1 = p_i(1 − 1/n)^n(1−p_i).

This is the paper's deterministic model of §1.3. Let p_i be the probability that a site is still susceptible after the ith cycle, n the number of sites, and partners be chosen uniformly.
Pull. A site is susceptible after cycle i + 1 exactly when it was susceptible after cycle i and the partner it contacted was also susceptible. The partner is susceptible with probability p_i, independently, so p_i+1 = p_i².
Push. A site is susceptible after cycle i + 1 exactly when it was susceptible after cycle i and none of the infective sites chose it. There are n(1 − p_i) infective sites, each choosing it with probability 1/n, so p_i+1 = p_i(1 − 1/n)^n(1−p_i).
For large n the last factor is close to e^−(1−p_i), and for small p_i close to e⁻¹. Push therefore multiplies a small p_i by about 1/e each cycle, a geometric decrease, while pull squares it, which falls faster than any geometric decrease once p_i is small.
Push-pull makes a site informed if either holds, so it does at least as well as pull; the paper reports that it behaves essentially like pull.∎

The festival has one fault. The pair go through their whole collections, and in an ordinary year almost every work agrees. Almost all the effort is spent finding that nothing needs doing.

A cheaper table

Comparing sums first

Each library keeps, beside its catalogue scroll, a catalogue sum: a short sum worked out from the whole catalogue. Two catalogues that agree on every work and edition have the same sum, and two that differ anywhere almost certainly have different ones.

A pair can begin by comparing sums, which is a glance across the table, and sit down to the long reading only if the sums differ.

The sums alone do not settle it. A recent edition is nearly always known to some libraries and not yet to others, so two libraries drawn by lot will usually differ over something recent, and the long reading is back.

The remedy

The recent list

Each library keeps a recent list: the editions whose tallies are newer than a chosen span. The pair swap recent lists first, each taking whatever is newer, and only then compare sums. Now the sums usually agree.

Its price

The span must be long enough

The span has to be longer than news needs to cross the whole coast. If the coast grows past it, the sums start to fail and the work returns to something slightly worse than reading everything. The paper warns that the choice is critical.

With no span

Newest first

The pair swap editions newest first, comparing sums after each, and stop the moment the sums agree. For that a library keeps a second scroll of its catalogue in order of tally. The paper calls it peel back.

Between festivals

Word of mouth

The stoa is the long colonnade beside the festival ground, where scholars from every library pass in turn and stop to talk.

A scholar who has just written a new edition, or just heard one, carries a scrap of it and tells it each day to whoever the road puts in the way. Whom a scholar meets is a matter of chance. Nobody arranges who talks to whom, and nobody keeps a record of who has been told.

The scraps a scholar is passing on are kept on a wax tablet, the hot tablet.

The stoa from the festival ground side: a long colonnade of plain columns under a tiled roof, the stone tables on the levelled ground before it and trees beyond

With respect to one scrap

Has not heard

The scholar's library does not hold it yet.

With respect to one scrap

Still telling

The scrap is on the hot tablet, and the scholar tells it to whoever is met. Whoever hears it for the first time begins to tell it too.

With respect to one scrap

Has stopped

The scrap is on the shelf as an edition, and readers are still answered from it. The scholar no longer tells it.

Why a scholar stops

Losing interest

Telling a scrap to someone who already has it is wasted breath. So a scholar who does so may give up, with a chance of one in some chosen number: the scholar's allowance.

At first the telling grows, because most of those met have not heard. Later it dies out, because most of those met have. The paper separates two choices. An attentive scholar learns whether the hearer already knew, and loses interest only after an idle telling; a blind one does not learn it, and may give up after any telling. And a scholar gives up either on a toss, at the chance of one in the allowance, or by count, after as many tellings as the allowance and not before. An attentive scholar who counts takes only idle tellings one after another, and starts again from none after a telling that was needed.

Nothing here is a plan. A scholar does not know whether the news has reached everyone, only what the last few hearers said.

When the last teller stops

Who never hears

The telling runs until no one is still telling, and then it stops for good. Whoever has not heard by then never will, by this habit. Those libraries are the residue.

The paper measures three things, and they pull against each other: the residue; the tellings for each library, which is the traffic; and the delay, both the average days until a library hears and the days until the last one that will hear does.

A thousand libraries, one scrap choose how the scholars tell, then let it run

Allowance

Does the teller learn whether the hearer knew?

Gives up

0never heard0tellings a library0days

Pale: has not heard. Gold: still telling. Green: has stopped.

The paper's measures, on a thousand libraries

Counting, attentive

An allowance of one leaves about 18 libraries in a hundred without the news, at 1.7 tellings a library. Three leaves about 1 in a hundred at 4.5. Five leaves about 1 in a thousand at 6.7.

The paper's measures

A larger allowance, a smaller residue

With an attentive scholar who gives up on a toss, an allowance of one leaves about a fifth of a very large coast unheard, and two about a sixteenth. The residue falls steeply as the allowance grows, and no allowance makes it nothing.

The paper's measures

Delay changes little

A library hears in eleven to thirteen days on average with counting, and fourteen to nineteen with tosses. The last library to hear does so in about seventeen days with counting and over thirty with tosses.

Proof · that the fraction who never hear satisfies s = e^{−(k+1)(1−s)}

Let s, i, r be the fractions of the population susceptible (have not heard), infective (still telling) and removed (have stopped), with s + i + r = 1, and let an infective site lose interest with probability 1/k each time it calls a site that is not susceptible. Claim. When the epidemic ends, s = e^{−(k+1)(1−s)}.

This is the paper's model of §1.4. Let s, i, r be the fractions of the population susceptible, infective and removed, so that s + i + r = 1. A susceptible site becomes infective in proportion to si; an infective site becomes removed at rate (1/k)(1 − s) per unit of i, since it loses interest with probability 1/k when it calls a site that is not susceptible, which happens with probability 1 − s. Hence
ds/dt = −si, di/dt = si − (1/k)(1 − s)i.
Dividing the second by the first removes t: di/ds = −1 + (1 − s)/(ks) = −(k + 1)/k + 1/(ks).
Integrating, i(s) = −((k + 1)/k)s + (1/k) ln s + c.
At the start one site in n is infective, so i(1 − ε) = ε with ε = 1/n. For large n, ε → 0, so i(1) = 0 and c = (k + 1)/k. Hence i(s) = ((k + 1)/k)(1 − s) + (1/k) ln s.
The epidemic ends when i = 0, that is when ln s = −(k + 1)(1 − s), so the residue satisfies s = e^{−(k+1)(1−s)}. For k = 1 the solution is about 0.20 and for k = 2 about 0.06, as the paper states.∎

One price in every version

The residue is about one over the exponential of the tellings for each library

1.7 tellings leave about a fifth, 3.3 about a twenty-seventh, 6.7 about a thousandth. A scrap is told to a library about as often as chance picks it, and a library is missed only if chance never picks it in all the tellings there are. So a smaller residue is bought with tellings, at the same price however the scholars tell. Only the delay tells the versions apart.

Argument · that s = e^−m in every version of rumour mongering

Let n be the number of sites, s the residue, and m the average number of updates sent from a site, so that the epidemic sends nm updates in all, each to a site chosen uniformly. Claim. s = e^−m. The paper says the argument is not fully proved.

The paper gives this argument in §1.4 and says it is not fully proved. Let m be the average number of updates sent from a site, so the epidemic sends nm updates in all.
Each update is addressed to a site chosen uniformly, so a given site is not chosen by any one with probability 1 − 1/n.
If the updates were independent, the probability that a given site is chosen by none of them is (1 − 1/n)^nm, which tends to e^−m as n grows. This probability is the residue s.
The step that is not proved is that m may be treated as a constant: it varies from site to site, and the relation holds only if its spread about the mean goes to zero as n → ∞. The authors observe this empirically and have not proved it.
Table 1 agrees with the relation: m = 1.7 gives e^−1.7 ≈ 0.18 and m = 3.3 gives ≈ 0.037.∎

Two ways to meet

Telling, asking and crowded days

A scholar who is telling goes to whoever is met and hands over the scraps. A scholar who is asking goes to whoever is met and says what is new? Either way a scrap changes hands.

Asking does better here too, and by a good deal. With an attentive scholar who counts, the paper's trials leave about 3 libraries in a hundred without the news at an allowance of one, at 2.7 tellings a library; about 6 in ten thousand at two; about 4 in a million at three.

The same thousand libraries telling against asking, attentive and counting

Each day

Allowance

0never heard0tellings a library0days

With asking, every library asks one other each day, and a scholar who still has the scrap on the hot tablet hands it over. A scholar asked by several in a day counts the day as wasted only if none of them needed the scrap, and starts the count afresh if any did.

Why telling is used at all

A quiet coast

When nothing is new, a telling scholar says nothing, which costs no breath. An asking scholar goes on asking, and every day's asking is wasted. Asking suits a busy coast and telling a quiet one.

Doing both

Only the lower count is charged

Two scholars who both tell and ask may find that both knew the scrap. Then only the one who has told it fewer times counts a wasted telling, and both do if they are level. That gives the smallest residue the paper reports, and costs carrying the count with the scrap.

Crowded days

Turned away, and hunting

If a scholar can be spoken to by only so many in a day, some are turned away. Telling gets better: the turned-away telling would have been a wasted one. Asking gets worse: a library refused day after day can miss the news. A scholar turned away can hunt for another listener, which is cheap and helps in every case.

With a limit of one speaker a day and hunting without end, every scholar ends up paired with one other, as at the festival. Telling and asking then become the same, and the residue is very small.

Two habits, each covering the other

The festival behind the gossip

The telling is quick and cheap and may leave a few libraries. The festival is slow and dear and leaves none. So the coast does both.

The telling can fail outright: the last teller can stop while some libraries have not heard, and the scrap is then held by some and not by others for good, unless something else carries it. The festival is that something else. Held rarely, it makes certain that every edition reaches every library or is replaced by a newer one.

When two copyists at the festival find that one holds a scrap the other lacks, they put it right. They may also do something more, and there are three replies to choose from.

The cautious reply

Nothing more

The festival will in time carry the scrap to everyone.

The bolder reply, by letters

Tell everyone again, by courier

This can cost a great deal. If the news has reached about half the coast, every one of those libraries writes to every library at the next festival.

The bolder reply, by word of mouth

Treat it as news again

This costs little. A scrap nearly everyone knows is soon dropped by whoever tells it. And when half the coast knows it, many scholars start telling at once, which costs less than starting from one.

A combination that cannot fail

Swap from the head of the list until the sums agree

Each library keeps its recent scraps in order of how lately each proved useful. A scrap that is new to the hearer moves to the head, and one that proves old slips down. A pair swap scraps from the heads of their lists, a few at a time, until their catalogue sums agree. Since they go on until the sums agree, no library is left out, and a coast cut in two for a while and joined again is put right the same way.

Spreading an absence

Withdrawing a work

Suppose Demerios judges a work wrong and withdraws it at Demerios's own library. Taking it off the shelf is not enough.

At the next meeting the pair compare. One library holds nothing of the work, and the other holds an edition. A library with nothing takes the other's edition, so the meeting gives the work back. Every habit so far spreads what is present. None spreads an absence.

The remedy is to make the absence something that can be carried. In place of the struck work the library writes a notice of withdrawal: a slip that names the work and carries a tally, like an edition. It spreads by the same habits, and wherever an older edition meets it, the edition is struck and the notice stays.

Two libraries meet at the festival choose what Library 1 did

Library 2 still holds the old edition, written on day 3.

What notices cost

They pile up

A library cannot keep every notice for good. It could throw one away once every library has it, but nobody on the coast knows that: it asks for everyone to be heard from, and some library is nearly always closed or cut off.

The plain answer

A fixed span

Throw a notice away after a fixed span, a month say. Then an old edition that turns up after the notice is gone is let back in. A longer span lessens the risk and uses more shelf.

A far longer span

Dormant notices

A notice names a few wardens, libraries drawn by lot. After a first span most libraries throw it away, and the wardens keep a copy asleep, carried to no one. After a second span they discard it too. If an old edition turns up at a warden, the notice wakes and is spread afresh.

What a woken notice carries

Two tallies

A woken notice must not carry a fresh tally in place of its own. Somewhere on the coast there may be a later edition, written after the notice to bring the work back, and a fresh tally would strike that too.

So a notice carries two tallies. The first never changes: it says when the work was withdrawn, and an edition is struck only if its tally is lower than this. The second is the waking tally: it says when the notice was last awake, and it alone decides whether the notice sleeps and whether it is carried.

A sleeping notice wakes the work was withdrawn on day 5, and brought back by a new edition on day 8

An old edition from day 3 turns up at a warden on day 10. Wake the notice.

Proof · that reactivating by the activation timestamp cancels no later update

A death certificate carries an ordinary timestamp t and an activation timestamp a, equal when it is created. It is dormant once a is older than the threshold τ₁, and deleted once a is older than τ₁ + τ₂. Claim. Reactivation, which sets a to the current time, cancels no item whose timestamp u exceeds t.

This is the argument of §2.2, set out. A death certificate carries an ordinary timestamp t and an activation timestamp a, equal when created.
The rule of cancellation uses only t: a certificate cancels an item with timestamp u exactly when t > u. The rule of propagation uses only a: the certificate is dormant, and so not propagated by anti-entropy, once a is older than τ₁, and is deleted once a is older than τ₁ + τ₂.
Suppose a site has a legitimate item with timestamp u > t, an update that reinstated the item after its deletion. The certificate has t < u, so it does not cancel it.
Reactivating a certificate sets a to the current time and leaves t unchanged. The cancellation test is unchanged, so the reactivated certificate still fails to cancel any item with u > t, while the new a lets it propagate.
By contrast, had reactivation set t to the current time, a certificate with t′ > u would cancel the reinstating update, which is incorrect.∎

Sleeping notices buy a great deal: for the same shelf, the history a coast can keep grows with the number of its libraries, from a month to years. The paper likens a waking to an immune reaction. The scheme does not scale for ever. While the first span is longer than a notice needs to cross the coast, wakings are rare. If the coast outgrows the span, wakings become common, each adds traffic that slows the next notice, and the habit breaks down. So the first span, and the shelf each library gives to notices, must grow slowly with the size of the coast.

A coast is not an even plain

Near partners and the ferry

Most libraries lie along the coast road within a walk of their neighbours. An inlet cuts a few of them off from the rest, and the only crossing is a ferry.

The few libraries across the ferry draw nearly all their partners from the other side, and each of the many on this side has a small chance of drawing one of them. Added up, the ferry carries far more meetings than any road.

The paper's answer is to prefer nearer partners. Each library lists the others in order of distance and draws partners from the list, with a chance that falls with the square of a library's place in the list. Where the coast is thickly settled the near ones get most of the chance, and where it is thin the chance spreads further.

The coast seen from above: libraries scattered among olive groves and joined by footpaths, with the stoa and its festival ground beside the water

Partners by lot, or nearer first the paper's trials, on a coast with one such crossing

These are the paper's measures. The page does not work them out.

How much nearer

Along one road

If every scholar picks only the nearest neighbour, the roads carry little, and news creeps along one library at a time. If anyone is picked by lot, news is quick and every stretch of road is crowded. A chance that falls with the square of the distance keeps both in hand.

Safe for the festival

Every pair still has some chance

So long as any two libraries may be paired, every library will in time meet every other, and the festival still misses no one.

Not safe for the telling

Telling the neighbour again

Two libraries that lie close together, far from all the others, may keep choosing each other. If they do so as many times as the allowance, the scrap is dropped before it leaves the pair. A lone library beyond a long stretch may never be picked while a scrap is still warm.

The remedy is to raise the allowance as the preference for the near grows. That works well for telling and asking together. Telling alone is far more sensitive: the paper's trial of it needed an allowance of thirty-six. The plain safeguard is the festival behind the gossip. The authors had the improved habit put to use in the system they studied, and the load and the disagreement between copies both fell.

The limits

What it does not say

The coast's habits bring every library the news in the end. Five things they do not promise.

Does news arrive within a number of days?

No. Every choice is by lot, so nothing can be said such as the news will arrive in so many days. If no one writes any more, the chance that it has still not reached everyone falls away fast as time passes. The authors take this as a fair price for habits that are simple to carry out correctly.

Does telling alone reach everyone?

No. It leaves a residue that can be made small and never empty, and there are small coasts where it fails badly. Only the festival behind it brings every library the edition or a newer one, and it promises that in the end, not by a day.

Does the coast ever agree completely?

Only when no one writes any more. While scholars keep writing, some libraries are behind, and a reader may be handed an out-of-date edition. How likely, and how far behind, is a question of its own.^*

What if two scholars write different editions of one work?

The coast keeps the one with the larger tally and throws the other away. It does not combine them. A tally is a reading of the sun, so it is only as good as the library's reading: if tallies stray, the coast still agrees in the end, but a newer edition may lose to an older one.

What is left unsolved?

Awkward shapes of the coast, which can ruin the gossip and which the authors say they do not yet understand; whether a fixed span for notices can be avoided; and whether some libraries should be set above others to carry news across the long distances.

Back to machines

The coast was a replicated database

Every library is a replica, and a scrap is an update. Hover or tap to see who is who.

On the coast

In the machine room

Reconciling at random reaches every replica in the end; passing fresh news on at random is quick and cheap, and leaves a small fraction for the reconciling to catch.

Deletions have to be spread as certificates, or an old copy brings the item back.

The scholars' coast, in detail All the papers

Setting The Scholars' Coast

The paper behind this book

Alan Demers, Mark Gealy, Dan Greene, Carl Hauser, Wes Irish, John Larson, Sue Manning, Scott Shenker, Howard Sturgis, Dan Swinehart, Doug Terry and Don Woods, Epidemic Algorithms for Replicated Database Maintenance. Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC), Vancouver, August 1987, 1–12; the version used here is Xerox PARC CSL-89-1, January 1989. — Direct mail, anti-entropy with checksums and peel back, rumor mongering, death certificates and spatial distributions, from the Clearinghouse servers of the Xerox Corporate Internet.

The ideas, plainly.

Demers and co-authors keep a database copied at many sites and ask how an update made at one site can reach all the others with very little help from the network and no one in charge. Each entry carries a timestamp and the larger timestamp wins, so any two sites that meet can settle which entry is newer. Mailing the update to everyone is quick but unreliable, and the sender may not know every site. Anti-entropy, in which each site regularly picks another at random and the two reconcile, always reaches every site, but slowly and at the cost of comparing whole databases; checksums and lists of recent updates make it cheap.

Rumor mongering passes an update on while it is still news: a site that has it tells others and loses interest after meeting enough who already knew. That is quick and cheap, but it can leave a fraction of sites who never hear, a fraction that shrinks exponentially with the patience allowed and is tied to the traffic by one relation in every version. Pull does much better than push when few sites are left. Anti-entropy run rarely behind it makes certain that nothing is missed.

Deletions have to be spread too, or an old copy brings the item back, so a deletion is a certificate with a timestamp; certificates cannot be kept for ever, so a few sites keep them asleep and wake them if an old copy turns up, with a second timestamp so that waking does not cancel newer updates. Choosing partners nearer first, with a chance that falls with the number of closer sites, spares the few critical links, at a small cost in delay; but it can defeat rumor mongering in awkward networks, which is another reason for the anti-entropy behind it.

Demerios stands for Alan Demers, the first author. The paper names twelve authors, Alan Demers, Mark Gealy, Dan Greene, Carl Hauser, Wes Irish, John Larson, Sue Manning, Scott Shenker, Howard Sturgis, Dan Swinehart, Doug Terry and Don Woods, and all are credited here. Only Demerios is named; the scholars of the stoa and the copyists of the festival are not told apart, since no one is in charge of either.

In the paper, term by term

the libraries along the coast, each holding copies	Sites, each storing a replica of the database. §1.1.
a work in the common scroll of learnings	A key of the database. §1.1.
an edition; its tally, the day and hour by the sun with the library's number; the larger tally wins	A value with a timestamp; the larger timestamp supersedes. §1.1.
writing a new edition at one's own library	Update[v]: the one client operation, at one site. §1.1.
a scrap of papyrus with a learning	An update. §0.
letters to every library	Direct mail: n messages per update, unreliable, and the sender may not know every site. §1.2.
the festival: pairs by lot compare whole collections	Anti-entropy: a simple epidemic that reaches every site with probability 1. §1.3, §3.2.
giving, asking, or both	Push, pull, push-pull. §1.3.
asking squares the share still without it; giving scales it	Pull: p_i+1 = p_i²; push: p_i(1 − 1/n)^n(1−p_i). §1.3.
the catalogue sum	A checksum of the database, updated incrementally. §1.3.
the recent list; a span longer than the news needs	The recent update list and the window T. §1.3.
newest first until the sums agree	Peel back, with an index by timestamp. §1.3.
drawing a name by lot	Choosing a partner uniformly at random. §1.3.
the scholars in the stoa; a day's meeting	Rumor mongering, a complex epidemic, in cycles. §1.4.
the hot tablet	The infective list of updates a site is sharing. §1.4.
has not heard; still telling; has stopped	Susceptible, infective, removed. §1.4.
the allowance; losing interest	The parameter k: loss of interest with probability 1/k, or after k unnecessary contacts. §1.4.
attentive or blind; toss or count	Feedback or blind; coin or counter. §1.4.
those who never hear	The residue s. §1.4.
tellings per library; days to hear	Traffic m; delay t_ave and t_last. §1.4.
the residue is one over the exponential of the tellings	s = e^−m, shared by the variations; not fully proved. §1.4.
telling and asking, on busy and quiet coasts	Push versus pull in rumor mongering; pull has s = e^−Θ(m³). §1.4.
both sides' counts, only the lower one added	Minimization. §1.4.
a limit on speakers per day; hunting for another	Connection limit and hunting; the chance of a site being contacted by j others in a cycle is about e⁻¹/j!. §1.4.
the festival behind the gossip; telling a found difference afresh	Backing up a complex epidemic with anti-entropy; redistribution, by mail O(n²) messages in the worst case. §1.5.
the list kept in order of use; swapping batches until the sums agree	Peel back combined with rumor mongering by a doubly-linked list. §1.5.
a notice of withdrawal	A death certificate. §2.
a fixed span; asking whether everyone has the notice	A fixed threshold; Sarin and Lynch's snapshot-based discarding. §2.
the wardens named by lot; a sleeping notice; the first and second spans	Dormant death certificates; retention sites; thresholds τ₁ and τ₂; the history kept grows by a factor of O(n), and τ₁ must grow as O(log n). §2.1.
the two tallies of a notice; waking	Ordinary and activation timestamps; reactivation. §2.2, §2.3.
preferring near partners; the ferry	Spatial distributions; critical links. On a line, a d⁻² distribution gives traffic per link of O(log n). §3, §3.1.
chance falling with a place in the list	A distribution parameterised by Q_s(d), the number of sites within distance d. §3.
the two small coasts where telling fails	Figures 1 and 2: spatial distributions can defeat rumor mongering. §3.2.