<figure><img src="image_1.png" /></figure>

HAL
open science

# Analysis of update synchronization for multiple copy data bases

Erol Gelenbe, Kenneth C. Sevcik

<figure><img src="image_2.png" /></figure>

## To cite this version:

Erol Gelenbe, Kenneth C. Sevcik. Analysis of update synchronization for multiple copy data bases. [Research Report] IRIA-RR-322, IRIA. 1978, pp.25. hal-04716510

HAL Id: hal-04716510

https://inria.hal.science/hal-04716510v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Dw-04432 RR 322

RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

ANALYSIS OF
UPDATE SYNCHRONIZATION
FOR MULTIPLE
COPY DATA-BASES

Erol GELENBE
Ken SEVCIK

Rapport de Recherche N° 322

Septembre 1978
ANALYSIS OF UPDATE SYNCHRONIZATION
FOR MULTIPLE COPY DATA-BASES

E. Gelenbe,* K. Sevcik **

Résumé :

Dans cet article une définition précise de la cohérence et de la promptitude d'un système d'information réparti (base de données répartie, système d'exploitation réparti, etc...) est donnée. Cette définition nous permet de mesurer et de calculer la cohérence, et d'évaluer l'efficacité d'algorithmes dont le rôle est de préserver la cohérence. Un algorithme de préservation de la cohérence est ensuite introduit et son effet sur un système réparti est calculé.

Abstract :

A formal model allowing a precise definition of coherence and promptness in a multiple copy information system is presented and used to analyze a class of update synchronization techniques.

* Laboratoire de Recherche en Informatique - Université Paris-Sud - 91405 Orsay, France.

**IRIA/LABORIA - B.P. 105 - 78150 Le Chesnay, France.
# I - INTRODUCTION

There are an increasing number of computer applications in which many people at different locations use a communication network to access and update a single data-base. In such systems, there are several motivations for storing copies of the same information at more than one center in the network. First, responses to queries can be made more quickly if the information requested is stored at the center where the query is received. Second, the breakdown of certain centers or communication links will not cause everyone to lose access to the information if copies are stored at several centers.

If updates to a multiple copy data base originate at various centers, several major problems arise. Each center becomes aware of update requests originating at other centers only after some unpredictable delay. Thus, a person may make an update request based on information currently available at his center when actually the information has already been modified by someone at another center. If not controlled, such situations can cause the internal consistency constraints of the data base to be violated even if each update maintains consistency when applied alone. In single copy data bases, mutual exclusion can be provided by mechanisms such as locks, but in the multiple copy context, the volume and duration of the communication required to set global locks is often prohibitive. An alternative is to check that all variables read by the update remain unchanged when the update is ready to write new values in the data-base. The update must be rejected if the value of some variable it read has changed. A second problem is that the order in which updates are applied affects, in general, the contents of a data base copy. Thus all centers must somehow agree both on which updates are to be rejected in order to maintain internal consistency and on the order in which the accepted updates are to be applied.

Finally, each center must decide when to apply an update request it has received to its copy of the data base. The most conservative strategy is to wait until later communication with all other centers has guaranteed that the update need not be rejected and that all previous updates have already been applied in the agreed upon order at the center. Alternatively, a center may choose to apply the update sooner on the
assumptions that it will not eventually be rejected and that other updates not yet applied at the center but earlier in the agreed upon order will neither access nor modify any of the information that it accesses or modifies. If the update is applied and this assumption is later discovered to have been false, then the data base copy must be backed up and the updates reapplied in the proper order.

A variety of techniques for controlling concurrent updates in multiple copy data bases have been proposed recently. The simplest of these rely on a "central" node [AD,B]. All update requests are passed from the center where they originate to the central node where they are either rejected or else receive a sequence number. The updates are then sent to all centers, where they are applied in the order of the sequence numbers. In a refinement of this scheme, the central node assigns batches of sequence numbers periodically to each center [GB]. In this way, updates receive their sequence number at the center where they originate, and then are sent directly to all other centers. Another possibility is to allow updates to originate from only one center at a time, with centers explicitly passing the right to admit updates from one to the next [LE].

Other update control techniques are based on a time-stamp by a local clock assigned to each update when it is created. The time-stamps can be made globally unique if at most one update can be created in any tick of the clock and if the center identification number is appended to the low order end of the time stamp. Such globally unique time stamps can be used directly to define the order of updates [JT], or they can play a supporting role in a more complex scheme. Thomas has proposed an update control method based on "majority consensus" [Th]. Each update request is passed from center to center, and each center may "reject" or "approve" the update based on what decisions it has made on updates seen earlier. An update is accepted when it has been approved by a majority of the centers. Accepted updates are applied in the order of their time stamps. This technique is robust in the presence of failures of centers and communication links. As long as more than a half of the centers are active and able to communicate, updates from these centers can be applied to the data base.

Another approach involving time-stamps has been developed for use in the SDD-1 distributed data base system [BSRG]. Updates are classified according to the data-base variables they access and modify. A given station is assigned the responsibility of sequencing a given class. Potential interference between updates of different classes is resolved by a "conflict graph". Pre-analysis of the conflict graph reveals the (hopefully few) situations in which careful coordination of updates of different classes is necessary.

The primary responsibility of an update control scheme is to guarantee that all centers reject the same requests, and apply the accepted updates in the same order (at least as far as can be detected from the data base state). There are, however, several secondary goals that should be considered in selecting an update control technique for a specific data base environment. These include (i) reducing delays in applying updates, (ii) avoiding favoring updates from some centers, (iii) giving similar responses to identical queries submitted simultaneously at different
rent nodes, (iv) minimizing the need to undo updates, and (v) insuring
that the order in which updates are applied conforms with their actual
order of submission. Because these goals are not all mutually compati-
ble, the selection of an update control policy requires that trade-
offs be made.

Our goal in this paper is to identify and illustrate the use of
some quantitative performance measures for studying the trade-offs among
the goals indicated in the previous paragraph. We introduce a general
metric for measuring the difference between two copies of the data-
base, then we point out instances of the metric that are useful in mea-
suring the extent to which particular update control techniques satisfy
the various goals.

In section 2, we define a formal model for studying the control of
concurrent updates to a multiple copy base. Section 3 presents the ana-
lysis of an example of such a system (a simple inventory control system).
Section 4 examines two parameterized families of update control policies.
In section 5, we discuss the possibility of extending our approach to
more general models. Finally, in section 6, we survey some additional
uses of the performance measures we have identified.

2. THE FORMAL MODEL

Consider a distributed data base system composed of N centers.
Each center maintains a copy of a set of data and replies to queries
which it receives locally concerning the information contained in this
data. Each center must also modify the data as a function of updates it
receives. These updates may originate locally, or can be sent to a cen-
ter by some other center. A transmission delay Tij is incurred by an up-
date as it travels from center i to center j.

The copy of the set of data at center i is completely characteri-
zed by its state $V_i(t)$, $t \ge 0$. This state is modified by the introduction
of updates via the update function $f$ which is common to all of the cen-
ters and which is time-invariant.

An update is defined as a vector (j,k,τ,x) where j is the number
of the center at which it originates, k indicates that is the k-th up-
date originating there, τ is the instant at which center j recognizes
the arrival of the update (but does not necessarily introduce it into
its copy of the data), and x is its information content. Part of the in-
formation content is the specification of three sets of data base varia-
bles : the readset includes variables read by the update at its center of
origination ; the reference set includes variables read at each center as
the update is applied there ; the write set includes all variables assi-
gned new values by the update. In order to preserve internal consistency,
an update must be rejected if, between the time of its origination and
the time it is applied at accenter, any of its readset variables are chan-
ged by another update.

An update control technique consists of two policies. The ordering
policy specifies the order in which the updates are to be applied (in
effect) at each center. The release policy specifies when an update recei-
ved at a center should be applied to the local data base copy.
The time $\tau$ is the time-stamp which center j assigns to the update $(j,k,\tau,x)$. At that instant, center j also initiates its transmission to all the other centers. Notice that each update originates at exactly one center; k is the sequence number assigned to it there. Note that, independent of the granularity of the clocks, time stamps can be made globally unique (and thus fully ordered) by using j and k.

The update function operates on the state of a center as follows. Suppose center i receives an update $(j,k,\tau,x)$ at some time $\tau+T_{ji}$. This update will wait in queue at center i for some duration $\omega$ (determined by the update control technique) before being processed. At time $\tau+T_{ji}+\omega$ its processing will begin and will end at $\tau+T_{ji}+\omega+S_i$. $S_i$ is the processing time (or service time) of the update at center i. At the end of the processing of the update, the state of the center is modified; that is

$$V_i(t^+) = f(V_i(t),x), \quad t = \tau + T_{ji} + \omega + S_i$$

We assume that only one update can be applied at a time at a given center; this implies that at center i in the interval

$$(\tau + T_{ji} + \omega, \tau + T_{ji} + \omega + S_i]$$

only the update $(j,k,\tau,x)$ will be processed. This excludes the possibility of having multiple state transitions at the same time.

Initially, at $t=0$, the state of all of the centers is the same :

$$V_i(0) = e_o, \quad \text{for all } 1 \le i \le N.$$

Thus the system is started with identical copies of the data at each center.

Let $\Sigma$ be the state-space of a copy of the data, and $\Gamma$ the space of all updates. Thus

$$f: \Sigma \times \Gamma \rightarrow \Sigma.$$

A record of what updates have been applied to the data copy is retained as part of $\Sigma$.

In general, for $e \in \Sigma, x, y \in \Gamma$

$$f(f(e,x)y) \neq f(f(e,y)x) \quad \text{for } x \neq y.$$

Thus the order in which updates are performed will be of importance.

We define a reference copy $V(t)$ as follows. $V(t)$ represents an ideal system in which all updates are made at the instant of their time-stamp. Thus

$$V(0) = e_o$$

and for each $t \ge 0$,

$$V(t) = f(f(\dots f(e_o, x_1)x_2) \dots x_{n-1})x_n$$
where $(i_1, k_1, t_1, x_1)$, $(i_2, k_2, t_2, x_2)$, ..., $(i_n, k_n, t_n, x_n)$ are the updates
which have arrived to the "real" (N copy) system prior to t, and

$$o \le t_1 < t_2 < \dots < t_n \le t.$$

In order to measure the information gap existing between different
copies of the data, or states of the system, we will introduce a *metric*
or norm $d(e,e')$. This metric will allow us to formulate some concepts
related to the physically intuitive notion of coherence of the distribu-
tion information system and which will be our main criteria for evalua-
ting the "quality" of the system.

For examples $d(e,e')$ may be the number of records of different ty-
pes in which e and e' differ, or the difference in the number of upda-
tes included in e and e'. More complex definitions of this metric which
include the specific information content of the states may also be con-
sidered.

We shall introduce two performance criteria for the distributed
information system. The *promptness* of a center *i* is defined as its dis-
tance from the reference copy. Let $\pi_i(t)$ denote the promptness of center
*i* at time *t*; then

$$\pi_i(t) = d(V_i(t), V(t)).$$

The *promptness* of the system at time *t*, $\pi(t)$, is the average promp-
tness of the centers :

$$\pi(t) = \frac{1}{N} \sum_{i=1}^{N} \pi_i(t).$$

Thus $\pi_i(t)$ tells us how up-to-date center *i* is at a given instant of
time. We shall often deal with the steady-state distribution of prompt-
ness defined as

$$P[\pi_i \le X] = \lim_{t \to \infty} P[\pi_i(t) \le X]$$

or with its average (or expected) value $E\pi_i$.

Another measure of interest for which we shall give a precise defi-
nition is the *coherence* at time *t*. This quantity will provide a measure
of the "dispersion" of the information states at each center. Thus a
highly coherent system is one on which all centers have exactly the sa-
me information stored in the copies of the data. Notice that the system
may be coherent, but not up-to-date (i.e. not prompt).

We define the *coherence of two copies* *i* and *j* at time *t* :

$$C_{ij}(t) = d(V_i(t), V_j(t)).$$

The *coherence of the system* is

$$C(t) = \frac{1}{N^2} \sum_{i,j} d(V_i(t), V_j(t)).$$
The stationary distribution

$$P[C_{ij} \le X] = \lim_{t \to \infty} P[C_{ij}(t) \le X]$$

$$P[C \le X] = \lim_{t \to \infty} P[C(t) \le X]$$

and the expected values in stationary state EC, EC will be of interest.

The system is coherent at time t if $C(t^j) = 0$ (with probability one)

and copies i and j are coherent if $C_{ij}(t) = 0$.

We will say that the system is *convergent* if stopping all updates after time t guarantees that

$$\lim_{X \to \infty} C(t+X) = 0 \quad (\text{with probability one}).$$

(i.e. all copies eventually become identical if all updates are stopped).

A *system checkpoint* is a time interval $[t, t+\Delta]$ during which the system is mutually coherent. We shall say that the system is *stable* if there exists an infinite sequence of non-overlapping checkpoint intervals

$$[t_1, t_1+\Delta_1], [t_2, t_2+\Delta_2], \dots, [t_n, t_n+\Delta_n], \dots$$

such that the expected length of each intercheckpoint interval is finite :

$$E[t_n - (t_{n-1} + \Delta_{n-1})] < \infty \quad \text{for all } n \ge 1.$$

The model we have presented in this section is quite general. For our purposes in the next two sections, we specialize the model as follows :

(i) Each center keeps a copy of the whole data base.

(ii) The clocks at each center are synchronized and are of sufficiently high resolution that two updates cannot originate at the same center with the same time stamp.

(iii) An update is sent from the center of origination by an individual message to each other center.

(iv) Every message sent is eventually received (although the transit delay may include times for re-sending lost messages).

(v) The ordering policy is to apply updates in the order of their time stamps (with ties broken by center number).

(vi) The release policy is either "release at arrival", or "release at $\tau+R$" where R is a fixed delay, or "release only when it is guaranteed that all earlier updates have already been received and released".
Because some of these assumptions are sometimes unrealistic (e.g. (ii)) or restrictive (e.g. (i), (iv), (v), (vi) we will discuss how they can be relaxed in section 5.

In the remainder of this section we relate the formal model to our intuitive notion of how updates are achieved in a multiple copy data base. Updates are assumed to take the following form. The values of variables in the readset are acquired through data base queries and some computation is done to determine the desired update. Next, the update is requested and sent to each other center. At each center it is eventually released. Its application involves the current values of variables in the reference set, doing a limited amount of computation, and writing new values for variables in the write set. The amount of computation done involving the reference variables is limited both because extensive computation should not be replicated at each center and because each center must guarantee mutual exclusion in applying the updates.

Several types of updates have special properties. If all updates in a system have null readsets and null reference sets (i.e. pure assignments), then it is never necessary to reject updates or to undo updates. The value of a variable at a center is simply that value assigned by the update with the latest time stamp among those received. If all updates have null readsets and only increment or decrement variables in the reference set (as in an inventory system), then convergence of the system is guaranteed even if the updates are applied in different orders at different centers. Again, updates never need be rejected or undone. Some updates may require extensive computation involving the readset variables either because the computation is complex or because the readset is very large. Without some additional mechanism, such updates would be likely to encounter perpetual rejection due to the high probability that, during its computation, some other update would change one of its readset variables. One way to allow such updates to proceed would be to provide global locks in addition to another update control technique. Only updates risking perpetual rejection would incur the expense of setting, and releasing the global locks.

If the release policy chosen requires that updates be applied only when it is known that all earlier updates have between received and applied, then it is desirable that centers inform one another not only of updates that originate at the center, but also of time intervals in which no updates originate. This can be done by having each center periodically send a special message to each other center. The special message would consist of the identity of the center of origination, a time stamp, and the time stamp of the most recent update to have originated at the center. Another center, receiving such a message, could then determine from the sequence numbers of updates whether or not it has received all updates origination, at the other node with time stamps earlier than the one of the special message.

Updates must be rejected if, during their computation, any of their readset variables are changed by another update. The mechanism for detecting such a change is not simple. In principle, it requires that for each data base variable, not only its current value but also the time stamp of the update that gave it that value be retained. In practice, it is
necessary in most environments to group variables and let a single time stamp indicate the most recent change to any variable in the group. This increases the frequency with which updates must ne rejected, but it avoids having to retain a time stamp for each variable.

In general, the ordering policy will not necessarily preserve the actual order in which the update requests are made. Clearly, in many applications, the order of application of two updates originating at different nodes at nearly the same time is of little consequence. In fact, the problem of synchronizing clocks at the nodes makes it impos- sible to determine the exact order in which requests are made [C,Lam]. Nonetheless, there are potential applications for distributed data-bases in which the order of applying the updates may be of great significance (e.g. inventory control systems, funds transfer systems, and stock exchan- ge systems). In these cases, it is highly desirable to minimize the ex- tent to which the order of updates determined by the ordering policy differs from the true order in which the requests were made. For simi- lar reasons, the frequency of having to reject update requests should also be minimized in such systems.

<figure><img src="image_4.png" /><figcaption>Figure 1. Center i of the distributed inventory control system</figcaption></figure>
### 3. COHERENCE AND PROMPTNESS IN A DISTRIBUTED INVENTORY CONTROL SYSTEM

One of the typical applications of distributed information processing systems is in the area of inventory control. Several examples come to mind: distributed banking applications, reservation systems, inventory control systems in geographically distributed industrial plants, and so on. That is why we shall examine in this section an idealized instance of such a system. This example will serve to illustrate the concepts developed in section 2.

Again we have N locations. At each location i an image of the level of the inventory $L_i(t)$ at time t (i.e. the number of items in stock) is maintained. Let us stress that $L_i(t)$ refers to the same inventory of the same item. We exclude multiple item inventories (the case where $L_i(t)$ is a vector) in order to preserve the simplicity and clarity of the discussion.

Each center also keeps the variables $U_i(t)$ and $Q_i(t)$:

- $U_i(t)$ is the audit trail or time-ordered set of all updates which have been used to modify the inventory $L_i(t)$ in the time interval $(0,t)$ at center i,

- $Q_i(t)$ is the set of updates which have been received at center i but not yet used to modify the inventory level.

Updates have the form $u = (j,k,\tau,x)$ defined in section 2; $x$ will take values in the set $\{+, -\}$ implying that the result of an update is to increase or decrease the level of the inventory by one item. The updates arrive to center i both locally, and from any other center j after a random delay $T_{ij}$, and the time $S_i$ necessary for introducing the update after it is released is zero. Thus in all respects we are dealing with a special instance of the general model described in the previous section, and the state is represented by:

$$V_i(t) = (L_i(t), Q_i(t), U_i(t), t)$$

The behaviour of the i-th center with its update control policy is represented on Figure 1. The policy we consider here consists of holding any update arriving from center j to center i at time $t^*$ up to time $t^*+R$ before it is released in order to modify the level $L_i$, where R is fixed as a function of system parameters. The role of the holding time R becomes clear when one examines Figure 1: this delay is used to reduce the disparity between the order induced by the time-stamp and the order in which updates are introduced into the data base (representing the level of the inventory), as well as the difference between the set of updates which have been applied at each center.

Consider the following set of updates, which we call the *differen-**ce set** associated with centers i and j:

$$D_{ij}(t) = \{u: [u \in U_i(t) \text{ and } u \notin U_j(t)] \text{ or } [u \notin U_i(t) \text{ and } u \in U_j(t)]\}$$

Our distance function will be the number of updates in the difference
set :

$$d(V_i(t), V_j(t)) = |D_{ij}(t)|$$

Using this definition of the distance function we shall proceed to compute the promptness and coherence measures related to the system.

We shall make the following assumptions concerning the behaviour of the system :

- updates arriving locally to center i constitute a Poisson stream of rate $\lambda_i$, $1 \le i \le N$. These N Poisson streams are mutually independent.

- the transmission delay $T_{ij}$ from center i to center j, for any $i \neq j$, is exponentially distributed of parameter $\mu_{ij}$ :

$$P[T_{ij} < X] = 1 - \exp(-\mu_{ij} X)$$

With these assumption we can obtain the following results. Their derivation is not given here because it calls upon some simple analysis.

Concerning the promptness $\pi_i(t)$ we have :

**Result 1 :** The average promptness of center i at time t is given by
(for $t > R$)

$$E\pi_i(t) = \sum_{\substack{j=1 \\ j \neq i}}^{N} \lambda_j [R + \frac{1 - \exp(-\mu_{ji}(t-R))}{\mu_{ji}}] + \lambda_i R$$

and asymptotically, as $t \to \infty$, we have

$$E\pi_i = \sum_{\substack{j=1 \\ j \neq i}}^{N} \lambda_j [R + \mu_{ji}] + \lambda_i R$$

**Result 2 :** For $t > R$, the average mutual coherence of centers i and j is:

$$EC_{ij}(t) = \sum_{\substack{k=1 \\ k \neq i, j}}^{N} \lambda_k \frac{\mu_{ki} + \mu_{kj}}{\mu_{ki} \mu_{kj}} (1 - \exp(-\mu_{ki}(t-R)))$$

$$ \cdot (1 - \exp(-\mu_{kj}(t-R))) + \lambda_i \frac{1 - \exp(-\mu_{ij}(t-R))}{\mu_{ij}} + \lambda_j \frac{1 - \exp(-\mu_{ij}(t-R))}{\mu_{ij}} $$
and asymptotically, as $t \to \infty$,

$$EC_{ij} = \lambda_i / \mu_{ij} + \lambda_j / \mu_{ji} + \sum_{\substack{k=n \\ k \neq i, j}}^{n} \lambda_k \frac{\mu_{ki} + \mu_{kj}}{\mu_{ki} \mu_{kj}}$$

**Result 3 :** For any fixed $t$, the promptness of the system increases linearly with $R$, while the coherence tends to zero as $R$ approaches $t$.

This last result presents clearly the role of the fixed delay update control technique : we see that this update control technique will be particularly valuable in conjunction with another technique which makes the system stable.

**Result 4 :** The system being analyzed is convergent.

This last result is easy to establish since all updates are guaranteed to arrive and because the update control method considered simply delays updates for some finite time.
## 4. ANALYSIS OF TWO UPDATE CONTROL TECHNIQUES

In this section, we analyze the coherence and promptness of a multiple copy data base system under two parameterized families of update control techniques. We define $d(V_i(t), V_j(t))$ to measure the difference in the sets of updates applied at centers i and j by time t. As was shown in the inventory system example, sets of updates may often be commutative. In this section, we examine coherence and promptness assuming that this is not the case.

Taking time stamp order as the ordering policy and assuming that the clocks at the nodes are synchronized, we will predict the extent to which one update is applied at some node before an earlier update is applied at another node. Let $U_i(t)$ denote the set of updates applied at i by time t. In this section $V_i(t)=U_i(t)$ and the distance function will be

$$d(V_i(t), V_j(t)) = \sum_i \sum_j (\tau v_i - \tau u_j)^+ \\ u \in U(t) \quad u \notin U(t) \\ v \in U(t) \quad v \notin U(t)$$

for $i \neq j$, where u and v denote the time-stamps of updates u and v and $X^+ = X$ if X is positive and zero otherwise.

The first parameterized family of release policies we analyze is based on postponing the release of each update for a fixed time with the intention of waiting notice of any nearly simultaneous updates. Update u is released at center i only after the time on the local clock is at least $\tau u + R$. In the extreme case when R is zero, each update is applied at a center as soon as it is received. The smaller R is, the more frequently it is necessary to "undo" updates in order to assure convergence. The second family of release policies avoids undoing updates entirely by releasing an update only when it is known to be the oldest update not yet applied at the center. Each center uses update messages and any special status messages it receives to keep track of how much earlier some update, not yet received, could have originated somewhere in the network. A parameter S is the time between broadcasts of status messages from each center. The smaller S is, the better the centers can keep track of one another's status.

Intuitively, among the fixed postponment release policies, we expect that as S grows, both incoherence and the frequency of having to undo updates are reduced, but promptness is also diminished. Among the full knowledge policies, as S decreases, the traffic of status messages is increased but promptness is improved substantially and incoherence is reduced somewhat.

We will derive the expected values of both promptness and coherence at an arbitrary point in time under each of the families of release policies. To do this, we implicitly consider all possible patterns of updates originating at the nodes.
A)- Fixed postponement analysis

We wish to determine $C_{ij}^R(t) = d^R(V_j(t), V_i(t))$, the contribution to incoherence caused by the application of updates at node j prior to the application of older updates at node i if each update is released no sooner than R time units after its time stamp. For two other nodes, a and b, consider the execution of updates originating from a at node i and originating from b at node j. For two specific updates, u from a and v from b, assume that $\tau u < \tau v$. If v is applied at j but u is not applied at i by time t, then $C_{ij}^R(t)$ is increased by $\tau v - \tau u$. Because updates ori-

Denote $W_{k\ell}(x) = P[T_{k\ell} > x]$, and assume that updates arriving to the i-th center constitute N independent Poisson streams of rates $\lambda_1, \dots, \lambda_N$. The following results are shown in Appendix I.

Result 5 : For $i \neq j$ and $t > R$ :

$$EC_{ij}^R(t) = \sum_b \sum_a \lambda_a \lambda_b \int_R^t W_{ai}(x) dx \int_{y=x}^{t-R} (y-x) (1 - W_{bj}(t-y)) dy$$

Result 6 : For exponentially distributed transmission delays, with $t \to \infty$, $i \neq j$,

$$EC_{ij}^R = \sum_b \sum_a \lambda_a \lambda_b \left[ \frac{e^{-\mu_{ai} R} (\mu_{bj} + \mu_{ai} (1 - e^{-\mu_{bj} R}))}{\mu_{ai}^3 (\mu_{ai} + \mu_{bj})} \right]$$

Result 7 : The average promptness of the system is for $t > R$ :

$$E\Pi_i^R(t) = \sum_a \sum_b \lambda_a \lambda_b \left[ \frac{R^3}{6} + \int_R^t dx \frac{x^2}{2} W_{ai}(x) \right]$$

Result 8 : For exponentially distributed delays, with $t \to \infty$,

$$E\Pi_i^R = \sum_{ab} \sum_{ai} \lambda_a \lambda_b \left[ \frac{R^3}{6} + e^{-\mu_{ai} R} \left( \frac{R^2}{2\mu_{ai}} + \frac{R}{\mu_{ai}^2} + \frac{1}{\mu_{ai}^3} \right) \right]$$

In the above results we take $T_{kk} = 0$, i.e. $W_{kk}(x) = 0$ for all $x \ge 0$, hence $\mu_{kk} = \infty$.

B)- Full knowledge analysis

Under the full knowledge release strategies, at each center at any time, there is some time stamp value such that the set of updates applied so far includes all updates with time stamps earlier than the value, and none with time time stamps later. Thus $C_{ij}^R(t) = 0$ for all $i$, and we concentrate on determining $C_{ij}^S(t)$ where $i \neq j$. At node i, the latest upda-
te applied by time t is the one which satisfies the following criteria :

(i) all previous updates from the same source node have arrived and been applied at i,

(ii) the next update from the same source node has not yet arrived at i,

(iii) the newest status message or update from the same source node indicating no further updates is the oldest among all the updates that satisfy (i) and (ii).

Note that (i) and (ii) determine a unique candidate among the updates originating at a given node, while (iii) selects among these candidates. When no status messages are issued (i.e. S→∞), (iii) picks the candidate update with the earliest time stamp.

We will call the time stamp of the update selected according to (i), (ii) and (iii) the release point of node i at time t. The significance of the release point is that it is the most recent time such that communications with other nodes has guaranteed that center i knows of all updates that originated anywhere in the network before that time. Under the full knowledge release policies, at center i at time t all updates with time stamps at or before the release point have been applied to the data base copy while no updates with time stamps after the release point have been applied.

Once again, consider the application at centers i and j of updates originating at centers a and b respectively. Let $r_i(t)$ denote the difference between t and node i's release point at t. Updates u and v with time time stamps $\tau u$ and $\tau v$ such that $\tau u < \tau v$ contribute $\tau v - \tau u$ to $C_{ji}^s(t)$. Considering all pairs of source nodes and all pairs of time stamps yield:

$$E[C_{ji}^s] = \sum_a \sum_b [\lambda_a \lambda_b \int_{X=0}^{\infty} p_j^b(X) \int_{Y=X}^{\infty} (Y-X) [1 - p_i^a(Y)] dydx]$$

and

$p_i^a(Y) = \Pr[r_i(\tau+t) \le Y \mid \tau \text{ update from center a with time stamp } \tau].$

$p_i^a(Y)$ is the probability that, by time $\tau+t$ node i has received the appropriate update messages or status report messages to be able to apply an update originating at node a with time stamp $\tau$. The value of $p_i^a(Y)$ is given by:

$$p_i^a(Y) = W_{ai}(Y) \left[ \prod_{k \neq i} Z_{ki}(Y) \right] \left[ \prod_{k \neq i, a} Q_{ki}(Y) \right]$$
where

$$
Z_{ki}(Y) = \exp [-\lambda_k \int_{h=0}^{\infty} [1 - W_{ki}(Y+h)]dh]
$$

$$
\text{and } Q_{ki}(Y) = 1 - \exp [-\lambda_k Y - \frac{1}{S} \int_{h=0}^{Y} W_{ki}(h)dh] \\
\qquad - \int_{g=0}^{Y} \lambda_k e^{-\lambda_k(y-g)} (1 - W_{ki}(g)) \exp [-\frac{1}{S} \int_{h=g}^{Y} W_{ki}(h)dh]dg.
$$

Intuitively, $W_{ki}(Y)$ is the probability that the update from center $i$ with time stamp $\tau$ has itself been received at node $i$ by time $\tau+Y$, $Z_{ki}(Y)$ is the probability that all updates with time stamps before $\tau$ originating at center $k$ have arrived at node $i$ by time $\tau+Y$ and $Q_{ki}(Y)$ is the probability that center $i$ known by time $\tau+Y$ all updates with time stamps before $\tau+Y$ originating at node $k$. The derivations of the expressions for $Z_{ki}(Y)$ and $Q_{ki}(Y)$ are given in the appendix.

The distance to the reference copy is simply the special case of
$C_{ji}^S(t)$ where $p_j^b(X) = 1$, to signify the instantaneous effect of upda-
tes on the reference copy :

$$
E_{\pi_i} = \sum_b \sum_a \lambda_a \lambda_b \int_{X=0}^{\infty} \int_{Y=X}^{\infty} (Y-X) [1 - p_i^a(Y)] dy dx
$$

where $p_i^a(Y)$ is defined as before.

After some manipulations,

$$
E_{\pi_i} = \lambda \sum_{\mathbf{a}} \frac{\lambda_a}{2} \int_{Y=0}^{\infty} Y^2 [1 - p_i^a(Y)] dy
$$

where $\lambda = \sum_b \lambda_b$.

The formulae for promptness and coherence derived above for the
two families of release policies are complex. An intuition for their
behavior can be developed only by assuming a particular distributional
form for the transit delay time distributions and evaluating the formu-
lae in various example networks. We have done this for deterministic and
exponential transit delay distributions. In most networks the transit
delay distributions are "between" deterministic and exponential in that
their coefficient of variation is between zero and one.

Under the fixed postponement release policies, as the parameter R
increases, the coherence measure generally decreases exponentially, while
the promptness measure increases in proportion to R; once R is larger
than most transit delays. Promptness is relatively insensitive to R when
R is less than most transit delays. Under the full information policies,
both promptness and coherence decrease very rapidly as S is reduced
from approximately the mean time between updates to approximately the
mean transit delay time. In the former case, the value of R is chosen
to reflect the relative importance of promptness and coherence in a
particular application, while in the latter case, the choice of S ba-
lances good promptness and coherence against avoiding excessive status
message traffic.

In symmetric systems, where all centers have the same rate of up-
date origination and all pairs of centers have the same transit delay
distributions, promptness and coherence depend on the network parameters
as follows. As the number of centers increases (while maintaining the
same total rate of updates), both promptness and coherence increase ap-
proximately linearly. The increase can be attributed to the fact that a
lower and lower proportion of the updates applied at a center originate
there. As the mean transit delay increases, both promptness and coheren-
ce tend to increase in proportion to approximately the cube of the mean
transit delay. Finally, as the rate of update origination at each node
increases, both promptness and coherence increase very rapidly.

Because the variety of non-symmetric network configurations is
vast, their behavior with respect to promptness and coherence cannot be
characterized in general. We mention only a few specific cases. Consi-
der first two networks that differ only in that, in one, the update ori-
gination rate is the same at each center, while in the other, all upda-
tes originate at one center. Both promptness and coherence are margi-
nally worse (i.e. larger) in the latter case. Next, consider isolating
one center more and more by increasing its mean transit delay to each
of the other centers. Both coherence and promptness increase rapidly as
the mean transit delays for the one center are increased. A similar
effect occurs when any number of centers, as a cluster, are moved fur-
ther and further from the rest of the network with respect to mean tran-
sit delay.

While individual applications and different network configurations
are important, our numerical studies have indicated some general gui-
delines for choosing values of R or S in using the release policies ana-
lyzed earlier. In the case of the fixed postponement release policies,
the best value of R will generally lie between one and four times the
mean transit delay. For the full knowledge release policies, the avera-
ge time between status message broadcasts should be closer to the mean
transit delay than to the mean time between update originations at a
center.
# 5. EXTENSIONS TO OTHER CASES

The analyses of sections 3 and 4 were based on the assumptions made in section 2. Here, we discuss the extent to which our analytic approach can be extended when some of these assumptions are relaxed.

## A) - Non-complete data base copies

Rather than having a copy of every part of the data base reside at every center, we might require only that each part reside at any (non-empty) subset of the centers. In this case, update message traffic could be reduced if each center could determine the subset of other centers affected by a particular update. Each center would have to treat each other center individually with respect to update sequence numbering. The application of an update involves only those centers storing the variables that are changed (or variables related by consistency constraints to those changed), so analysis of update control techniques proceeds as before, except that only a subset of nodes are involved with each update.

## B) - Imperfect synchronization of clocks

While careful dynamic control can assure that the clocks at the nodes will be nearly synchronized, perfect synchronization is impossible [Lam]. This fact could be included in our model by introducing the quantity $\delta_i(t)$ which is defined to be the difference between the clock at center i and t when the "true" time (according to an ideal constant rate clock) is t. When all clocks run at the same constant rate (i.e. $\delta_i(t)$ does not depend on t), our analytic approach remains applicable. When $\delta_i(t)$ depends on t, the form of the dependence would determine the approach to analyzing update control techniques.

## C) - Non-broadcast protocols for update requests

In some types of networks (store and forward packet-switching, for example), the total load on the network due to updates can be reduced by passing a single update request message from center to center rather than sending a separate message to each other center. In this case, the quantitative analysis of the performance of update control techniques is complicated by the fact that the taken by a particular update request to reach various centers are not independent. A similar dependence among the transit times of messages arises if the message passing protocol of the network is "send and wait", or something similar [Gel]. It seems that the benefits of non-broadcast protocols can be acquired only by sacrificing some promptness and some coherence.
### D)- Other reference copy definitions

Our belief that it is good to retain the "true" order of updates as much as possible led us to define a reference copy in which updates are applied at the instant they originate. As a result, those update control techniques that are based on time stamp order tend to do best with respect to promptness. With a different definition of the reference copy, however, promptness could measure the performance of update control techniques with respect to a different idea of the "ideal" system.

### E)- Significant update computation times

Most computer networks pass messages with sufficient speed that the queueing and processing times for applying updates at a center are significant. We have assumed these times to be negligible for the sake of clarity, but the same analytic approach could be used without this assumption. Some parts of the generalized analysis might best be treated using approximations.

### F)- Failures of centers or network links

The fact that messages are occasionally lost and must be re-sent can be represented in the model we have analyzed simply by adjusting the transit delay distributions. Failures of centers or communication links, however, can only be reflected in a more detailed model. These problems motivate the use of a "majority consensus" control scheme [Th] in order to allow the majority of centers to proceed despite the failure of some centers or links. A model in which all messages originating at given center or traversing a given network path in a time period are lost is needed in order to quantify the advantage of using Thomas' control algorithm over another.

### G)- Discussion and conclusions

A number of other useful quantitative performance measures can be derived by analyses similar to those that we have presented here. Two examples are the "rejection rate" and the "inversion rate". The rejection rate is the frequency with which requests must be rejected. It depends more on the network parameters (transit delays and update rate) than on the update control technique chosen. The inversion rate is the frequency with which the ordering policy interchanges the order of two updates with respect to the true order of origination. Note that whenever the inversion rate is non-zero, promptness with respect to the reference copy as defined in section 2 grows without bound. Hence, if the ordering policy may have a non-zero inversion rate, promptness is only meaningful with respect to a reference copy in which updates follow the same ordering policy as for the centers.
Just as promptness and coherence represent a trade-off in choosing an update control policy, other performance measures reflect a trade-off in determining how to balance the priorities between updates and queries at a center. Two such measures are "query response time" (as traditionally defined) and "precision", which quantifies the extent to which a query response incorporates all updates with time stamps earlier than that of the query. Good precision requires that good response be sacrificed in order to await the application of all earlier updates before responding to the query.

In the presence of a release policy that allows the provisional application of updates before it is known for certain whether they might have to be rejected or undone, the responses to queries may also need to be "undone". Since responses once sent to a terminal or printer can only be retracted, not entirely undone, it is desirable to accompany each query response with an indication of the likelihood that the response will have to be retracted later. This indication can take the form of the recency of communication with other centers (perhaps the time stamps of the oldest possible unapplied update and the latest applied update), or an estimate of how many updates with time stamps earlier than the query have not yet been applied to the data-base copy. If a user chooses to do an update based on information in a query response that may have to be retracted, then he should incorporate the conditions that motivate him to do the update into a conditional clause on the update. Only in this way will this update be automatically undone if the query response is later retracted in such a way that the update is no longer appropriate. The alternative is for the user to monitor retractions and explicitly remove the effect of earlier updates when necessary.

We have concentrated on the use of promptness and coherence in choosing among update control techniques by calculating equilibrium expected values. There is, however, another way of using promptness and coherence. Each center can maintain a dynamic estimate of its promptness and coherence with other centers based on those messages that it has received as well as those that it infers are currently in transit. Appending these estimates to query responses (when requested) would help the users to assess the recency and soundness of the responses they receive.

We believe that quantitative tools can be helpful in identifying and resolving various trade-offs that arise in the design of update protocols in multiple copy distributed data bases. In this paper, we have established a formal model, proposed two particular performance measures and demonstrated the kind of analytic approach that can be taken. Deeper examinations of promptness and coherence and the search for other useful performance measures remain as work for the future.
APPENDIX 1 : Derivation of the results for fixed postponement analysis.

We shall only establish Result 5 and 7 since 6 and 8 are obtained by direct substitution and some straightforward computations.

Consider the updates u originating from the a-th stream, and v from the b-th stream where $y = \tau v > x = \tau u$. v will be applied at j by time t, before u is applied at i, if $\tau v \le t-R$ (and hence $\tau u < t-R$) with $\tau u + T_{ai} > t$ and $\tau v + T_{bj} \le t$. Since the updates streams are Poisson, x and y are uniformly distributed in (0,t-R) and independent. First consider a≠b. We then have that the contribution to $EC_{ij}^R(t)$ due to u and v is:

$$X_{ab} = \int_{0}^{t-R} \frac{dx}{t-R} W_{ai}(t-x) \int_{y=x}^{t-R} (y-x) (1 - W_{bj}(t-y)) \frac{dy}{t-R}$$

There are an average number $\lambda_a(t-R)$, $\lambda_b(t-R)$ updates originating at a and b, which yields Results 5.ª If a=b, $\tau u$ and $\tau v$ are again independent and uniformly distributed in (0,t-R), but now there must be at least two arrivals from stream a in the interval (0,t-R) for there to be a positive contribution to $X_{ab}$. Also, for each u we have (n-1) possible updates v, if the total number of updates arriving from stream a is fixed to n. Therefore the total average contribution to $EC_{ij}^R(t)$ from the case a=b becomes:

$$\sum_{n=2}^{\infty} n(n-1) \frac{[\lambda_a(t-R)]^n}{n!} e^{-\lambda_a(t-R)} = [\lambda_a(t-R)]^2$$

The sum of this with the terms for a≠b yields Result 5.

Let us now turn to the proof of Result 7, and consider the updates u,v such that $\tau v > \tau u$ and u originates at a and v at b. Consider the case $t-R \le \tau u \le t$; for all u of this form we will have a contribution to $E\Pi_1^R(t)$ equal to:

$$\sum_{a \ b} \sum_{a \ b} (\lambda_a R)(\lambda_b R) \int_{t-R}^{t} \frac{dx}{P} \int_{x}^{t} (y-x) \frac{dy}{R} = \sum_{a \ b} \sum_{a \ b} \lambda_a \lambda_b \frac{R^3}{6}$$

For $0 \le \tau u < t-R$ the contribution will be:

$$\sum_{a \ b} \sum_{a \ b} \lambda_a(t-R) \lambda_b t \int_{0}^{t-R} \frac{dx}{t-R} W_{ai}(t-x) \int_{x}^{t} (y-x) \frac{dy}{t} = \sum_{a \ b} \sum_{a \ b} \lambda_a \lambda_b \int_{0}^{t-R} dx \frac{(t-x)^2}{2} W_{ai}(t-x)$$

and by a change of variable we have Result 7.
## APPENDIX 2. Derivations of $Z_{ki}(Y)$ and $Q_{ki}(Y)$

We denote by $Z_{ki}(Y)$ the probability that all updates originating at center k with time stamps before $\tau$ are received at center i by time $\tau+Y$. Because the number of requests with time stamps before $\tau$ is unboun- ded, we use the following limiting argument. We consider only the upda- tes originating at k with time stamps in the interval $(\tau-T, \tau)$, then we let $T \to \infty$. This yields:

$$Z_{ki}(Y) = \lim_{T \to \infty} \sum_{n=0} \Pr[n \text{ updates from } k] \Pr[\text{all } n \text{ arrive at } i] \quad \begin{array}{l} \text{in } (\tau-T, \tau) \\ \text{by } \tau+Y \end{array}$$

Because the origination process is Poisson, the probability that n occur in an interval of length T is $\exp(-\lambda_k T) (\lambda_k T)^n / n!$ and each one of these may be considered independently as occurring at a point with uniform dis- tribution over the interval. Thus,

$$Z_{ki}(Y) = \lim_{T \to \infty} \sum_{n=0}^{\infty} e^{-\lambda_k T} \frac{(\lambda_k T)^n}{n!} \left\{ \int_{n=0}^{T} W_{ki}(h+X) \frac{1}{T} dh \right\}^n$$

which yields

$$Z_{ki}(Y) = \exp(-\lambda_k \int_{h=0}^{\infty} (1-W_{ki}(h+X))dh)$$

The probability that no status report from k with time-stamp in the in- terval $(\tau, \tau+g)$ has reached center i by $\tau+Y$ is given by

$$\begin{align*} N_{ki}(g) &= \sum_{i=0}^{\infty} \frac{(g/S)^i}{i!} e^{-g/S} \left\{ \int_{h=0}^{g} (1-W_{ki}(Y-h))dh/g \right\}^i \\ &= \exp\left(-\frac{1}{S} \int_{h=0}^{g} W_{ki}(Y-h)dh\right) \end{align*}$$

Then considering all possible values of g we obtain

$$Q_{ki}(Y) = 1 - \exp\left(-\lambda_k Y - \frac{1}{S} \int_{h=0}^{Y} W_{ki}(Y-h)dh - \int_{g=0}^{Y} dg \, k e^{-\lambda_k g} (1-W_{ki}(Y-g))\exp\left(-\frac{1}{S} \int_{h=0}^{g} W_{ki}(Y-h)dh\right)\right)$$
REFERENCES

1. [AD] Alsberg, P.A. and J.D. Day, "A principle for resilient sharing of distributed resources. Proc. 2nd Int. Conf. on Software Eng. (Oct. 1976).

2. [BSRG] P.A. Bernstein, D.W. Shipman, J.B. Rothnie and N. Goodman, The concurrency control mechanism of SDD-1 : A system for distributed data bases, Techn. Rpt. CCA-77-09, Computer Corp. of America, (Dec. 1977).

3. [B] S.R. Bunch, Automated backup, see [8]

4. [C] E. Chang, Decentralized control in distributed systems, Thesis in progress, University of Toronto.

5. [CO] W.W. Chu and G. Ohlmacher, Avoiding deadlock in distributed data bases. ACM Natl. Conf. (Nov. 1974), 156-160.

6. [EGLT] K.P. Eswaran, J.N. Gray, R.A. Lorie and I.L. Traiger, The notions of consistency and predicate locks in a data-base system. CACM 19, 11 (Nov. 1976).

7. [GLPT] J.N. Gray, R.A. Lorie, G.R. Putzolo and I.L. Traiger, Granularity of locks and degrees of consistency in a shared data base. IBM Res. Rpt. RJ 1654, (Sept. 1975), San Jose.

8. [GB] E. Grapa and G.G. Belford, Techniques for update synchronization in distributed data bases. Center for Advanced Computation, Univ. of Illinois, (1977).

9. [Gel] E. Gelenbe, J.L. Grangé, P. Mussard, Performance limits of the protocol TMM, submitted for publication.

10. [JT] P.R. Johnson and R.H. Thomas, The maintainence of duplicate data-bases. Request for comments # 677, ARPA Network Inf. Cent. Doc. # 31507, (Jan. 1975).

11. [Lam] L. Lamport, Time, clocks and the ordering of events in a distributed system, Massachusetts Comp. Assoc., Wakefield Mass., (March 1976). Report CA-7603-2911. (submitted to CACM)

12. [Lel] G. Le Lann, Distributed systems - Towards a formal approach. Proc. IFIP Congress 77, p. 155-160.

13. [S] L.C. Sekino, Multiple concurrent updates. Proc. VLDB, (1975), p. 505-507.
14. [SRL] R.E. Stearns, P.M. Lewis, and D.J. Rosenkrantz, Concurrency control for data-base systems, Proc. IEEE 17th Ann. Symp. on Foundations of Computer Science (Oct. 1976).

15. [Th] R.H. Thomas, A majority consensus approach to concurrency control for multiple copy data bases. Rpt. 3733, Bolt, Beranek and Newman, Inc. (Dec. 1977). (submitted to TODS)

16. [GM] E. Gelenbe, R. Muntz, Probabilistic models of computer systems Part. I, Acta.Informatica 7, 1 (1976).

17. [G] E. Gelenbe, On the optimum checkpoint interval, Res. Rpt. 77-4, Laboratoire de Recherche en Informatique, Univ. Paris-Sud (March 1977) to appear in JACM.