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.ingupdates 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.iollsystem, 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\ratiirc, 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.