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.
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.