\boldhead{1. Basic Techniques} This section introduces our notion of a replicated database and presents the basic direct mail, anti-entropy and complex epidemic protocols together with their analyses. {\noindent \bf 1.1 Notation} Consider a network consisting of a set $S$ of $n$ sites, each storing a copy of a database. The database copy at site $s \in S$ is a time-varying partial function $$s.\hbox{ValueOf}: K \rightarrow (v:V\times t:T)$$ where $K$ is a set of keys (names), $V$ is a set of values, and $T$ is a set of timestamps. $V$ contains the distinguished element $\hbox{NIL}$ but is otherwise unspecified. $T$ is totally ordered by $<$. We interpret $s.\hbox{ValueOf}[k]=(\hbox{NIL},t)$ to mean that the item identified by $k$ has been deleted from the database. That is, from a database client's perspective, $s.\hbox{ValueOf}[k]=(\hbox{NIL},t)$ is the same as ``$s.\hbox{ValueOf}[k]$ is undefined.'' The exposition of the distribution techniques in Sections 1.2 and 1.3 is simplified by considering a database that stores the value and timestamp for only a single name. This is done without loss of generality since the algorithms treat each name separately. So we will say $$s.\hbox{ValueOf} \in (v:V\times t:T)$$ i.e., $s.\hbox{ValueOf}$ is just an ordered pair consisting of a value and a timestamp. As before, the first component may be $\hbox{NIL}$, meaning the item was deleted as of the time indicated by the second component. The goal of the update distribution process is to drive the system towards $$\forall s, s^\prime \in S: s.\hbox{ValueOf} = s^\prime .\hbox{ValueOf}$$ There is one operation that clients may invoke to update the database at any given site, $s$: $$\hbox{Update}[v:V] \equiv s.\hbox{ValueOf} \leftarrow (v, \hbox{Now}[])$$ where $\hbox{Now}$ is a function returning a globally unique timestamp. One hopes that the timestamps returned by $\hbox{Now}[]$ will be approximately the current Greenwich Mean Time---if not, the algorithms work formally but not practically. The interested reader is referred to the Clearinghouse[Op] and Grapevine[Bi] papers for a further description of the role of the timestamps in building a usable database. For our purposes here, it is sufficient to know that a pair with a larger timestamp will always supersede one with a smaller timestamp. Κ˜– "tex" style˜Jšœ˜˜Iblock˜©K˜Kšœ˜˜šœ€˜€Kšœ4˜4—KšœΫ˜Ϋ˜“Kšœ)˜)—Kšœά˜ά˜JKšœK˜K—˜]KšœM˜M—Kšœͺ˜ͺ———…— * Θ