Epidemic algorithms for replicated database maintenance

Whru a dilt~lhSC is replicated at, many sites2 maintaining mutual consistrnry among t, he sites iu the fac: e of updat, es is a signitirant problem. This paper descrikrs several randomized algorit, hms for dist, rihut. ing updates and driving t, he replicas toward consist, c>nc, y. The algorit Inns are very simple and require few guarant, ees from the underlying conllllunicat. ioll system, yc+ they rnsutc t. hat. the off (~c~t, of ('very update is evcnt, uwlly rf+irt-ted in a11 rq1ica. s. The cost, and parformancc of t, hr algorithms arc tuned I>? c%oosing appropriat, c dist, rilMions in t, hc randoinizat, ioii step. TIN> idgoritlmls ilr (' c*los~*ly analogoIls t, o epidemics, and t, he epi-dcWliolog) -litc, ilitlh iii Illld~~rsti4lldill~ tlicir bc*liavior. One of tlW i, oritlims 11&S brc>n implrmcWrd in the Clraringhousr sprv (brs of thr Xerox C'orporat~c~ Iiitcrnc4, solviiig long-standing prol>lf~lns of high traffic and tlatirl>ilsr inconsistcllcp.