\input Paper.tex \null\vskip .1in \centerline{ Epidemic Algorithms for Replicated Database Maintenance} \centerline{ PODC '87} \centerline{ ERRATA} \vskip .1in \item{$\bullet$} The title of Table 1 should be: ``Performance of an epidemic on 1000 sites using feedback and counters.'' \item{$\bullet$} The title of Table 2 should be: ``Performance of an epidemic on 1000 sites using blind and coin.'' The heading of the first column in Table 2 should be ``1/Probability''. \item{$\bullet$} The title of Table 3 should be: ``Performance of a pull epidemic on 1000 sites using feedback and counters''. \item{$\bullet$} Last complete sentence of the 6th page, first column and the next sentence should be: ``Simulations indicate that the counter variations are closest to this behavior (counter with feedback being the most effective). The coin variations do not fit the above assuptions, since they do not have most of their traffic occurring when nearly all sites are infective.'' \item{$\bullet$} The equation for T(n) in section 3.0 should be $$ T(n) = \cases{O(n), & $a<1$;\cr O(n/\log n), & $a=1$;\cr O(n^{2-a}), & $1 < a < 2$;\cr O(\log n), & $a = 2$; \cr O(1), &$a > 2$\cr}$$ \item{$\bullet$} The equation preceding equation 3.1.1 should be: $$ p(d) = { \sum_{i=Q(d-1)+1}^{Q(d)} f(i) \over Q(d) - Q(d-1) } $$ \item{$\bullet$} The numbers in the two columns of Table 6 under the heading ``Compare Traffic'' were computed incorrectly. The rightmost six columns of Table 6 should be essentially identical to those of Table 4. \item{$\bullet$} In section 3.2, observations 1 and 2 should refer to Tables 4 and 5 instead of Tables 2 and 3. Furthermore, while observations 1 through 5 remain valid with Table 6 corrected as above, the situation is more accurately and succinctly summarized as follows: $k$ has been chosen for each value of $a$ so that complete spreading occurs. Under these circumstances, the fact that rumor mongering achieves the same raw results as anti-entropy is not surprising. However, the cost of an anti-entropy cycle is a function of the database size, while the cost of a rumor mongering cycle is a function of the number of active rumors in the system. Similarly, the compare traffic figures in Table 4 and Table 6 have different meanings. In general rumor mongering comparisons should be cheaper than anti-entropy comparisons, since they need to examine only the list of hot rumors. We conclude that a nonuniform spatial distribution can produce a worthwhile improvement in the performance of {\it push-pull} rumor mongering, particularly the traffic on critical network links. \end ʤ˜J˜Jšœ˜JšÏb7œ˜9Jšœ ˜ Jšœ˜ Jšœ ˜ Jšœ˜J˜Jšœ ˜ J˜Iblock˜{K˜½K˜~J˜K˜ýJ˜K˜?K˜ÌK˜K˜AK˜K˜BK˜K˜ØK˜K˜»K˜K˜J˜J˜J˜—…— ” >