Concurrency Control and View Notification Algorithms for Collaborative Replicated Objects.
AbstractThis paper describes algorithms for implementing a high-level programming model for synchronous distributed groupware applications. In this model, several application data objects may be atomically updated, and these objects automatically maintain consistency with their replicas using an optimistic algorithm. Changes to these objects may be optimistically or pessimistically observed by view objects by taking consistent snapshots. The algorithms for both update propagation and view notification are based upon optimistic guess propagation principles adapted for fast commit by using primary copy replication techniques. The main contribution of the paper is the synthesis of these two algorithmic techniquesguess propagation and primary copy replicationfor implementing a framework that is easy to program to and is well suited for the needs of groupware applications.
Introduction
Synchronous distributed groupware applications
are finding larger audiences and increased interest
with the popularity of the World Wide Web. Major
browsers include loosely integrated groupware applications
like chat and whiteboards. With browser functionality
extensible through programmability (Java
applets, plug-ins, ActiveX), additional groupware applications
can be easily introduced to a large community
of potential users. These applications may vary
from simple collaborative form filling to collaborative
visualization applications to group navigation tools.
Synchronous collaborative applications can be built
using either a non-replicated application architecture
or a replicated application architecture. In a non-replicated
architecture, only one instance of the application
executes, and GUI events are multicast to all
the clients, via systems such as shared X servers [1].
In a replicated architecture, each user runs an appli-
cation; the applications are usually identical, and the
state or the GUI is "shared" by synchronously mirroring
changes to the state of one copy to each of the
others [6, 13].
Research Center,
Hawthorne, NY 10532, USA. E-mail: fstrom, banavar, klm,
mjwg@watson.ibm.com
2 Department of Electrical Engineering and Computer Sci-
ence, University of Michigan, Ann Arbor, MI, USA. E-mail:
aprakash@umich.edu
In this paper, we assume that replicated architectures
are used because they generally have the potential
to provide better interactive responsiveness and
fault-tolerance, as users join and leave collaborative
sessions. However, the domain of synchronous collaborative
applications is broader than those supported
by a fully replicated application architecture. For example

ffl the applications may have different GUIs and
even different functionality, sharing only the replicated
state,
ffl the shared state may not be the entire application
state, and
ffl an application may engage in several independent
collaborations, e.g., one with a financial planner,
another with an accountant, and each collaboration
may involve replication of a different subset
of the application state.
In order to support the development of such a large
variety of applications, it is clearly beneficial to build a
general application development framework. We have
identified the following requirements for such a frame-work

From the end-user's perspective, collaborative applications
built using the framework must be highly
responsive. That is, the GUI must be as responsive as
a single user GUI at sites that initiate updates, and
the response latency at remote sites must be minimal.
Second, collaborative applications must provide sufficient
awareness of ongoing collaborations.
From the perspective of the developer of collaborative
applications, the framework must be application-independent
and high-level. That is, it must be capable
of expressing a wide variety of collaborative appli-
cations. Second, the developer should not be required
to be proficient in distributed communication proto-
cols, thread synchronization, contention, and other
complexities of concurrent distributed programming.
We have implemented a framework called Decaf
(Distributed, Extensible Collaborative Application
Framework) that meets the above requirements.
Our framework extends the well-known Model-View-
Controller paradigm of object-based application development
[10]. In the MVC paradigm, used in GUI-
oriented systems such as Smalltalk and InterViews
[12], view objects can be attached to model objects
in order to track changes to model objects. Views
are typically GUI components (e.g., a graph or a win-
dow) that display the state of their attached model
objects, which contain the actual application data.
Controllers, which are typically event handlers, receive
input events from GUI components and, in response,
invoke operations to read and write the state of model
objects. Updated model objects then notify their attached
views of the change, so that the view may re-compute
itself based on the new values. The MVC
paradigm has several beneficial properties such as (1)
modular separation of application state components
from presentation components and (2) the ability to
incrementally track dependencies between such components

To support groupware applications, Decaf extends
the MVC paradigm as indicated in Figure 1. First,
the framework supplies generic collaborative model
objects, such as Integers, Strings, Vectors, etc. to application
developers. These model objects can have
replica relations with model objects across applica-
tions, so that replicated groupware applications can be
easily built. Second, it provides atomicity guarantees
to updates on model objects, even if multiple objects
are modified as part of an update. The framework
automatically and atomically propagates all updates
to replicas of model objects and their attached views.
Third, writers can choose whether views see updates
to model objects as they occur (optimistic) or only
after commit (pessimistic). Fourth, applications can
dynamically establish collaborations between selected
model objects at the local site and model objects in
remote applications. Finally, users may also code authorization
monitors to restrict access to sensitive objects

In this paper, we first introduce the basic concepts
of the Decaf framework (Section 2). Next, we describe
the distributed algorithms that implement consistent
update propagation (Section 3) and view notification
(Section 4). Then, we present comparison
with related work, our experience with using Decaf
(Section 5) and finally, some concluding remarks (Sec-
tion 6).
2 The DECAF Framework
As mentioned earlier, Decaf extends the Model-
View-Controller paradigm [10]. Decaf model object
classes are supplied by the framework; the application
programmer simply instantiates them (model objects
Replica
update
notifications
updates
reads/
A Replica
Model Objects
Transaction View
Collaborative Application A2
reads
Application
Framework

Figure

1: Typical structure of Decaf applications.
are shown below the horizontal line that separates the
framework from the application in Figure 1). The
application programmer writes views and controllers,
which initiate transactions (these are shown above the
horizontal line in Figure 1). In the following subsec-
tions, we describe the key concepts in the framework
and the atomicity guarantees on access to model objects
provided by the Decaf infrastructure.
2.1 Model objects
Model objects hold application state. All model
objects allow reading, writing, and attaching views.
There are three kinds of model objects: (1) Scalar
model objects, which currently are of types integer,
real, and string; (2) Composite model objects, which
support operations to embed and to remove other
model objects called children, and which may be either
lists (linearly indexed sequences of children) or
tuples (collections of children indexed by a
Association model objects, which are used to track
membership in collaborations.
Model objects can join and leave replica relationships
with other model objects. The value of an association
object is a set of replica relationships which
are bundled together for some application purpose.
For each replica relationship, the association object
contains the set of model objects which have joined,
together with their sites and object descriptions.
The operations on association objects relevant to
this paper are join and leave, by which a model object
joins or leaves a particular replica relationship as
described in Section 2.7.
2.2 Replica Relationships
A replica relationship is a collection of model ob-
jects, usually spanning multiple applications, which
are required to mirror one another's value. Replica
relationships are symmetric and transitive.
2.3 Controllers
A controller is an object which responds to end-user
initiated actions, such as typing on the keyboard,
clicking or dragging the mouse, etc. A controller may
initiate transactions to update collaborative model ob-
jects. A controller may also perform other external
interactions with the end user.
2.4 Transactions
Transactions on model objects are executed by invoking
an execute method on a transaction object. Application
programmers may define transaction objects,
with their associated execute method, for actions that
need to execute atomically with respect to updates
from other users. The execute method may contain
arbitrary code to read and write model objects within
the application. Any changes to model objects will be
automatically propagated to their replicas.
The execution of a transaction is an atomic ac-
tion. That is, it behaves as if all its operations -
those of the execute method and those which propagate
changed values to replicas - take place at a
single instant of time, totally ordered with respect to
the times of all the other atomic actions in the system.
Atomicity is implemented optimistically in Decaf.
Transactions may abort, e.g., if two transactions originated
at different sites and each transaction guessed
that it read and updated a certain value of an object
before the other transaction did, then one of the
transactions will abort. Aborted transactions are re-executed
at the originating site. The effects of aborted
transactions will be invisible to pessimistic views, and
automatically undone as seen by optimistic views.
2.5 View Objects
A view object is a user-defined object which can be
dynamically attached to one or more model objects.
When a view is attached to a model object, that view
object will be able to track changes to the model object
by receiving update notifications, as calls to its update
method. If a view object is attached to a composite
model object, it will receive notifications for changes
to the composite as well as any of its children. The
purpose of a view object is to compute some function,
e.g., a graphical rendering, of some or all of the model
objects it is attached to. When the view object receives
an update notification, its update method may
take a state snapshot by reading any of the model objects
that it is attached to. State snapshots are guaranteed
by the infrastructure to be atomic actions -
behaving as if they are instantaneous. Besides taking
a state snapshot, the update method may initiate
new transactions and perform arbitrary external in-
teractions, such as rendering on the display, printing,
playing audio data, etc.
Each update notification contains a list of all ob-
jects, and only such objects, that have changed value
since the last notification. Objects not on this list
may be assumed not to have changed value. This information
allows view objects to recompute its function
more efficiently when only a part of a large value
has changed. For example, when large composite objects
are changed, the update notification will not only
specify which composite object has changed, but also
which parts have changed, to allow incremental recalculation

2.6 Optimistic and Pessimistic Views
View objects can be either optimistic or pessimistic.
Optimistic and pessimistic views differ in the protocols
for delivery of update notifications.
An optimistic view will receive an update notification
as soon as possible after any of its attached
model objects has changed. However, the state snap-shot
may be inaccurate or inconsistent because messages
have arrived out of order or because transactions
will abort. If an optimistic view ever takes an incorrect
snapshot, the infrastructure will eventually execute a
superseding update notification. Therefore, so long
as the system eventually quiesces, the final snapshot
taken before the system quiesces will be correct. An
optimistic view will receive a commit notification (as
a call to its commit method) whenever its most recent
update notification is known to be correct. Committed
state snapshots are always correct and always occur in
monotonic order. An optimistic view therefore trades
off accuracy and the risk of wasted work in exchange
for responsiveness.
Pessimistic views receive update notifications only
when transactions updating attached model objects
have committed and when the view will be able to
see consistent values. The system makes two guarantees
to a pessimistic view: (1) never to show any
uncommitted or inconsistent values, and (2) to show
all committed values in monotonic order of applied
updates.
2.7 Collaboration Establishment
Users may create replica relationships and cause
model objects to join or leave replica relationships dy-
namically. In order for an object A at one site to join
a replica relationship involving an object B at another
site, the following steps must occur:
ffl B's owner must create an association object BAs-
soc containing at least one replica relationship
joined by B.
ffl B's owner must then publicize the right to collaborate
with B by creating an external token called
an invitation including a reference to BAssoc and
export it somewhere where A's owner can access
it (e.g., on a bulletin board).
ffl A's owner must then import this invitation and
use it to instantiate his own association object
AAssoc. Object AAssoc must then be authorized
to reveal BAssoc's replica relationships.
ffl A's owner can then read AAssoc, discover the existence
of a replica relationship involving B that
it wishes to join, and issue a join of A to that
relationship.
Since association objects are also model objects,
and can have views attached to them, changes in membership
in associations are signalled in exactly the
same way as changes in values of data objects.
3 Concurrency control
This section describes the optimistic concurrency
control algorithms for propagating updates among
model objects in replica relationships.
Each transaction is started at some originating site,
where it is assigned a unique virtual time
to execution. The V T is computed as a Lamport time
[11], including a site identifier to guarantee uniqueness

When a transaction is initiated, a transaction implementation
object is created at the originating site.
When updates are propagated to remote replicas,
transaction implementation objects are created at
those sites. Each transaction implementation object
at a site contains: the V T of the transaction, references
to all model objects updated by the transaction
at that site, and additional state information.
Each model object holds:
ffl Value History: The value history is a set of pairs
of values and V T 's, sorted by V T . The value with
the latest V T is called the current value.
ffl Replication Graph History: This is a similarly
indexed set of replication graphs. A replication
graph is a connected multigraph whose nodes are
references to model objects, and whose multi-
edges are the replication relations built by the
users. It includes the current model object, and
all other model objects which are directly or indirectly
required to be replicas of the current model
object as a result of replication relations. Since
replication graphs change very infrequently, in
practice this history will most frequently contain
only a single graph.
Histories are garbage-collected as transactions com-
mit. Committal makes old values no longer needed for
view snapshots or for rollback after abort, thus they
are discarded.
There is a function which maps replication graphs
to a selected node in that graph. The node is called
the primary copy and the site of that node is called the
primary site, adapting a replication technique used by
Chu and Hellerstein [4] and others. The correctness of
the concurrency control algorithm is based upon the
fact that the order of all reads and updates of replicas
is guaranteed to match the order of the corresponding
reads and updates at the primary copy. Whenever the
originating site of a transaction is not the primary site
of some of the objects read or written by a transac-
tion, the transaction executes optimistically, guessing
that the reads and updates performed at the originating
site will execute the same way when re-executed
at the primary sites. If these guesses are eventually
confirmed, the transaction is said to commit. If not,
the effects of the transaction are undone at all sites
and the transaction is retried at the originating site.
3.1 Concurrency Control for Scalar
Model Objects
When a transaction T is first executed, it is assigned
a V T which we call t T . As it executes, the
transaction reads and/or modifies one or more model
objects at the originating site. Each model object
records each operation in the transaction implementation
object. For each model object M read, the
transaction implementation object records the read
R , where t M
R is defined as the V T when the
current value was written. For "blind writes" (writes
into objects not read by the transaction), t M
R is defined
as equal to t T . The transaction object additionally
records the graph time t M
G , defined as the V T that
's replication graph was last changed.
Consider a transaction T given in Figure 2 that is
originated at some site. T is assigned a V T t
The current values of W, X, Y, and Z at t T are
4, written at V T 80,
3, written at V T 70, and
Assume all replication graphs were initialized at V T
(this is not shown in the figure). At the end of the
transaction execution, the transaction implementation
object records the following:
- Read object W, t W
- Read object X, t X
Y := X;
then Z := Z
Transaction T
Figure

2: Example of transaction execution.
Update object Y, t Y
Update object Z, t Z
Observe that the update to Y is a "blind write,"
since Y was not read in this transaction; hence t Y
The transaction implementation object next distributes
the modifications to all replicas of the above
model objects. The transaction requests each primary
copy to "reserve" a region of time between t M
R and t T
as write-free. Since replica graphs can also change (al-
beit slowly), the transaction must also reserve a region
of time between t M
G and t T as free of graph updates.
As mentioned earlier, the originating site of the
transaction has executed optimistically, guessing that
its reads and updates will be conflict-free at each primary
copy. Specifically, the validity of the transaction
depends upon the following types of guesses:
ffl "Read committed" (RC) guesses: That each
model object value (or graph) read by the trans-action
was written by a committed transaction.
ffl "Read latest" (RL) guesses: That for each
value (or graph) of model object M read by trans-action
T , no write of M by another transaction
occurred (or will occur) at the primary copy between
R (or t M
G ) and the transaction's t T . This
guess implies that the primary site would have
read the same version of the object had the trans-action
executed pessimistically.
ffl "No conflict" (NC) guesses: That for each
model object value (or graph) written by the
transaction, no other transaction reserved at the
primary copy a write-free region of time containing
the transaction's V T . This guess implies that
the primary site would not invalidate previous
reads by confirming this write.
CONFIRM
Y
Z
CONFIRM-READ
COMMIT
COMMIT
CONFIRM

Figure

3: Example of update propagation.
The execution of the transaction takes place op-
timistically, using strategies derived from the optimistic
guess propagation principles defined in Strom
and Yemini [15], and applied to a number of distributed
systems (e.g. optimistic call streaming [2] and
HOPE [5]). However, our algorithm makes certain
specializations to reduce message traffic.
For RC guesses, the originating site simply records
the V T of the transaction which wrote the uncommitted
value that was read. The originating site will
not commit its transaction until the transaction at the
recorded V T commits. For each uncommitted trans-action
T at a site, a list of other transactions at that
site which have guessed that T will commit is maintained

The RL and NC guesses are all checked at the site
of the primary copy of an object M . The RL guess
checks that no value (or graph) update has occurred
R (or t M
G ) and t T , and if this check succeeds,
creates a write-free reservation for this interval so that
no conflicting write will be made in the future; the NC
guess checks that no write-free reservation has been
made for an interval including t T .
For each object M read but not written, a message
is sent to the primary copy (if it is at a remote
site). This message contains t M
G , and t T . Each
primary copy object then verifies the RL guesses for
values and graphs. A confirmation message is then is-
sued, confirming or denying the guess. In the general
approach, or in Hope, this confirmation
message would be broadcast to all sites. But in the
Decaf implementation, this confirmation is sent only
to the originating site. It is a property of our Decaf
implementation that the originating site always knows
the totality of sites affected by its transaction by com-
mit/abort time. Therefore, the originating site is in
a position to wait for all confirmations to arrive and
then to forward a summary commit or abort of the
transaction as a whole to all other sites. This avoids
the need for each primary copy to communicate with
all non-primary sites, and it avoids the needs for non-primary
remote sites to be aware of guesses other than
the summary guess that "the transaction at virtual
For each object M modified by T we send a message
to all relevant sites, containing t M
the new value. However while all sites other than the
primary site simply apply the update at the appropriate
primary site additionally performs the
RL and NC guess checks and then sends a confirmation
message to the originating site.
The originating site waits for confirmations of
guesses from remote primary sites. If all guesses for
a transaction are confirmed, the originating site commits
the transaction and sends a commitmessage to all
remote sites which received update messages. If any
guess is denied, the originating site aborts the trans-action
and sends an abort message to all remote sites.
The originating site then re-executes the transaction.
If a site detects that a transaction at V T has com-
mitted, the modified model objects at that site are in-
formed. This notification can be used to schedule view
notifications and eventually to garbage-collect histo-
ries. The site retains the fact that the transaction
has committed so that if any future update messages
arrive, the updates are considered committed.
If a transaction is aborted, the modified model objects
are informed so that the value at V T can be
purged from the history. The site retains the fact that
the transaction has aborted so that if any future up-date
messages arrive, the updates are ignored.
Let us examine how these algorithms would apply
in our example, shown in Figure 3. Suppose there are
four sites, and that W and X are replicated at sites 1,
2, and 3, while Y and Z are replicated at sites 2, 3,
and 4. Suppose that T is initiated at site 2. Suppose
further that the primary site of W and X is 1, and of
Y and Z is 4. Ignoring graph times and graph updates
for now, and assuming that the three current values
read by the transaction were committed (hence there
are no RC guesses), the following messages are sent
from site 2 after the transaction is applied locally (we
perform the obvious optimization of sending messages
only to relevant sites):
1. To site 1: CONFIRM-READ t
2. To sites 3 and 4:
checks that W is write-free for the V T range
from 80 to 100 (RL guess check) and that X is write-
free for the V T range from 60 to 100 (RL guess check).
If so, it reserves those times as write-free and sends a
CONFIRM to site 2.
simply applies the updates to its Y and Z
replica objects.
Site 4 checks that Z is write-free for the V T range
from 40 to 100 (RL guess check). If so, it reserves
those times as write-free. It also checks that writing
Y or Z at V T 100 does not conflict with any previously
made read reservations (NC guess checks). If all the
above checks succeed, it applies the updates and sends
a CONFIRM to site 2.
responses. If both are confirma-
tions, it sends COMMIT 100 to all other sites involved.
3.2 Concurrency Control for Composite
Model Objects
Although the concurrency control algorithm is the
same for composite objects as for scalar objects, it
is desirable to save space by not keeping a separate
replication graph for each object inside a composite.
That is, if composite A is a replica of composite A 0 and
A 00 (see

Figure

4), we wish to avoid encoding inside
object A[103] that it is a replica of objects A 0 [103]
and A 00 [103].
Our approach is that by default, an object embedded
within a composite inherits the replication graph
of its root; e.g. A[103]'s replicas would be at the same
sites as A's replicas, at the corresponding index (103).
Similarly, if A[103] is itself a composite object, its
embedded objects, e.g. A[103]["John"][12] would be
replicated at the same sites.JohnA'
JohnA"

Figure

4: Replicas of composite model objects.
The set of indices between the root and a given
object is called its path; when an object such as
A[103]["John"][12] is modified, the change and the
path to A are then sent by A to its replicas A 0 and A 00 ,
which then use the same path name, [103]["John"][12],
to propagate the update to their corresponding components
A 0 [103]["John"][12] and A 00 [103]["John"][12].
We call this technique indirect propagation of updates,
in contrast to the direct propagation technique discussed
earlier, in which each object holds its own replication
graph and communicates directly to its replicas.
In addition to saving space, indirect replication
avoids the problem in direct replication that small
changes to the embedding structure could end up
changing a large number of objects. For example, if indirect
replication were not used, adding a new replica
A 000 to the set fA; A 0 ; A 00 g would entail updating the
replication graph for every object embedded within A
and its replicas. Similarly, removing A[103] from A
would entail updating the replication graph for every
object embedded within A[103].
3.2.1 Adjustments to support indirect propa-
gation
There are two adjustments which have to be made
to ensure the correctness of the concurrency control
algorithm in the presense of indirect propagation.
The first has to do with the relative order of
list items. A transaction at V T 100 may modify
having seen that an earlier
transaction at V T 80 deleted A[5] so that what
the originating site thinks of as A[103] may appear
to some other sites to be A[102]. This is not a concurrency
control conflict - it is simply a consequence
of the fact that path names like [103]["John"][12] are
fragile. To overcome this, rather than using the actual
list index in a path name, the propagation algorithm
uses the transaction V T as a unique identifier - e.g.
if A[103] was embedded in A at V T 40, then 40 is used
as an index. If several embeds were performed at V T
40, they are distinguished by a "subtime", e.g. 40.1
or 40.8. A composite object receiving such an indirect
propagation message can always propagate it down the
tree regardless of the order in which it has received
other structure-changing operations. During such a
propagation, if it is determined (using the transaction
that an earlier path changing update
has not yet been received, the propagation will block
until the earlier update is received.
The second adjustment has to do with guesses associated
with the paths for indirect object propagation.
The updated model objects must make RC guesses to
ensure that transactions that created their paths have
committed and RL guesses that no straggling transactions
have removed any component of their paths.
3.2.2 When indirect propagation is not possi-
ble
Indirect propagation is the default mode of propagating
value updates to objects within composites. However
indirect propagation is not always possible. Consider
the configuration in Figure 5. In this case, node
C can indirectly propagate changes to C 0 , but node B
cannot because it has a different set of replicas than
the rest of the tree. We therefore use direct replication
for objects B, B 0 , and B 00 .
A'
A
B"

Figure

5: Indirect propagation not possible for this
case.
3.3 Dynamic Collaboration Establish-
ment
The set of replica relations between objects remains
relatively static. Most transactions change the values
of objects rather than the replication graphs. But
replication graphs do change, as users join and leave
collaborations. Direct propagation graphs for embedded
objects inside composites can also change as a
result of deleting objects from composites and embedding
them elsewhere. Dynamic collaboration establishment
transactions need not be especially fast, but
they must work correctly in conjunction with all the
other transactions.
We have already seen some of the effects of dynamic
collaboration establishment in the algorithms
described above. Replication multi-graphs are time-stamped
with the transaction V T which changed
them. There is no "negotiation" for primary copy;
each node is able to map a given multi-graph to the
identity of the primary site for that configuration. A
primary copy always confirms the RL guess that the
graph hasn't changed as well as confirming whatever
else it is being asked to check: this guards against
the possibility that the originating site is propagating
to the wrong set of sites or that it is asking the
wrong primary copy because of a graph change that it
hasn't seen yet. A primary copy always reserves the
graph against changes during a region of time that a
previously confirmed transaction has assumed to be
change-free.
4 View Notification
This section describes the algorithms for implementing
the view notification semantics given in Section
2.5.
When a transaction implementation object completes
executing at a site, the Decaf infrastructure
initiates view notifications to be sent to all the view
objects attached to the model objects updated in the
transaction. View object attachments are always lo-
cal, i.e., views are always attached to model objects
at the same site. Thus, a view notification is simply
a method call to the update method implemented by
the view object. The update method can contain arbitrary
code that takes a state snapshot by reading the
view's attached model objects and recomputes its dis-
play. The infrastructure guarantees that such a state
snapshot is implicitly a consistent atomic action.
For every view notification initiated, a snapshot object
is created internal to the Decaf infrastructure.
All the snapshots associated with a particular user
level view object are managed internally by a view
proxy object. Each model object contains the set of
view proxies corresponding to its views, which it notifies
upon receiving an update or a commit.
Since a snapshot is an atomic action, it is assigned
a virtual time t S . Each snapshot is assumed to read
all the model objects attached to the view at V T t S .
These reads may be optimistic; hence, as described in
Section 3.1, their validity depends upon the read values
being the latest (RL guess) and the read values being
committed (RC guess). Confirming RL guesses involves
remote communication with the primary copies
of the objects read in the snapshot. If the RL and RC
are confirmed, the snapshot is said to commit.
Optimistic and pessimistic views differ in two re-
spects. First, they differ in the time at which view notifications
are scheduled. Optimistic notifications are
scheduled as early as possible, i.e., as soon as a model
is updated and a snapshot thus initiated, whereas pessimistic
notifications are scheduled after it is known
that the snapshot is valid, i.e., that the view will read
consistent committed values. Second, they differ in
the lossiness of notifications. Pessimistic views are
notified losslessly of every single update in monotonic
order of updates whereas optimistic views are notified
only of the latest update. Subsections 4.1 and 4.2
describe these behaviors in more detail.
As described in Section 2.5, view notifications are
incremental, i.e., each notification provides only that
part of the attached model object state that has
changed since the last notification. However, for the
sake of simplicity, the algorithms presented in this section
do not incorporate incrementality; each snapshot
is assumed to read the set of attached model objects
in its entirety. Furthermore, notifications may be bundled
to enhance performance, i.e., a single view notification
may be delivered for multiple model objects
that were updated in a single transaction.
4.1 Optimistic Views

Figure

6 shows an optimistic view V attached to
model objects A and B. The view proxy object V P
represents V internally. A and B have committed current
values (i.e., values with the latest V T ) at V T 's
100 and 80 repectively. A transaction T runs at V T
110 and updates A, which notifies its view proxy V P .
The primary requirement of optimistic views is fast
response. Consequently, as soon as V P is notified, it
performs the following:
1. It creates a snapshot object and assigns it a V T
equal to the greatest of the V T 's of the current
values of all attached model objects. In this case,
2. It schedules a view notification, i.e., calls the
view's update method.
A

Figure

View notification.
At the end of the snapshot, the snapshot object
records that all attached model objects were read at
t S . In order for the snapshot in this example to com-
mit, two guesses must be confirmed (as before, we ignore
guesses related to the graph):
1. An RC guess that the update by transaction T at
T 110 has committed. This requires receiving a
COMMIT message from the site that originated
transaction T .
2. An RL guess that the V T interval from 80 to
110 is update free for B. This requires sending a
CONFIRM-READ message to B's primary copy
and waiting for the response.
Eventually, if these guesses are confirmed, then the
snapshot commits, and a commit notification is sent
to V , i.e., its commit method is called.
If, on the other hand, an RC guess turns out to
be false, the view proxy re-runs the snapshot with a
new t S . In the example of Figure 6, if the RC guess
was denied as a result of transaction T at V T 110
aborting, a new snapshot is run. This snapshot will
have since that is now the greatest V T of the
current values of all attached model objects. Notice
from this example that optimistic view notifications
are not necessarily in monotonic V T order.
In the case that an RL guess is denied by the primary
copy, that means that the requested interval is
not update free, and thus a straggler update is yet to
arrive at the guessing site. In this case, the straggler
itself will eventually arrive and cause a rerun of the
view notification. In the example in Figure 6, if the
RL guess was denied as a result of a straggler update
to B at V T 105, the update at V T 105 will trigger a
new view notification at t
This algorithm implements the liveness rule for optimistic
views that an update notification is followed
either by a commit notification or, in the case of an
invalid optimistic guess or a subsequent update, a new
update notification.
An optimistic view proxy maintains at most one
uncommitted snapshot - the one with the latest t S
- at any given time. If a new update arrives before
the current snapshot has committed, then we're
obliged to notify the new update to the view due to
the responsiveness requirement. The system may as
well discard the old snapshot since there is no way to
notify the view of its commit (as we don't expose V T 's
to views). As a result, an optimistic view gets a commit
notification only when the system quiesces, that
is, when no new updates are initiated in the system
before existing updates are committed.
4.2 Pessimistic Views
Recall that the system makes two guarantees to a
pessimistic view: (1) never to show any uncommitted
values, and (2) to show all committed values in
monotonic order of applied updates.
A pessimistic view proxy initiates a snapshot at
every V T that one or more of its attached model objects
receive a committed update. However, it does-
n't schedule a view notification for the snapshot until
the snapshot commits. Snapshot committal depends
on (1) the validity of model object reads at the snap-
shot's t S , and (2) whether its preceding snapshots have
already committed (this is due to the monotonicity
requirement). When one or more snapshots commit,
the view is notified, once for each committed snapshot,
in V T sequence. Thus, unlike an optimistic proxy, a
pessimistic proxy manages several uncommitted snap-shots

A pessimistic view proxy thus contains a list of
snapshot objects sorted by V T . It also contains a
field lastNotifiedVT which is the V T of the last up-date
notification.
To illustrate pessimistic view notification, let us say
that the view V in the example of Figure 6 is a pessimistic
view. Suppose that lastNotifiedVT = 80. Suppose
further that the snapshot at V T 100 is as yet uncommitted
and thus A's committed update at V T 100
is not yet notified. When the transaction at V T 110
commits, it informs the model object A, which in turn
informs the pessimistic view proxy V P . V P creates
a snapshot object, assigns it a t records
the following guesses:
1. A "snapshot committed" guess (SC guess) that
the preceding snapshot at V T 100 will commit.
This stems from the monotonicity requirement.
2. An RL guess that the V T interval from 100 to
committed updates for A. This also
stems from the monotonicity requirement. This
requires sending a CONFIRM-READ message to
A's primary copy and waiting for a response.
3. An RL guess that the V T interval from 100 to 110
is free of committed updates for B. This requires
a CONFIRM-READ message as above.
Eventually, if all the guesses made by a particular
snapshot object are confirmed, it commits, and it
can confirm the SC guess of its successor snapshot.
When any snapshot commits, all contiguous committed
snapshots after lastNotifiedVT are notified, and
lastNotifiedVT is updated.
A straggling committed update, say at
for B in the example, may cause an RL guess to be
negated. In this case, when the straggling committed
update is notified to the proxy, a new snapshot is
created at V T 105 as given above. Additionally, the
RL guess made by the succeeding snapshot at V T 110
(guess (3) above) is revised to be for the V T interval
from 105 to 110 for B.
This algorithm implements the consistency and monotonicity
requirements for pessimistic views.
5.1 Related Work
The Decaf framework is designed for collaborative
work among a small and possibly widely distributed
collection of users. Consistency, responsiveness, and
ease of programming are important objectives.
ISIS [3] provides programming primitives for consistent
replication, although its implementation strategies
are pessimistic.
Interactive groupware systems have different performance
requirements and usage characteristics from
databases, leading to different choices for concurrency
control algorithms. First, almost all databases use
pessimistic concurrency control because it gives much
better throughput, a major goal of databases. In interactive
groupware systems, on the other hand, pessimistic
concurrency control strategies are not always
suitable because of impact on response times to user
actions - ensuring interactive response time is often
more important than throughput. Second, possibilities
of conflicts among transactions is lower in groupware
systems because people typically use social protocols
to avoid most of the conflicts in parallel work.
Optimistic protocols based on Jefferson's Time
Warp [8] were originally designed for distributed simulation
environments. They have been successfully applied
in other application areas as well[7]. However,
one important characteristic of distributed simulation
is that there is usually an urgency to compute the final
result, but not necessarily to commit the intermediate
steps. In these protocols, the primary purpose
of "committing" is to free up space in the logs, not to
make the system state accessible to view. But in a co-operative
work environment such as ours, fast commit
is essential. The delay associated with waiting for at
most a single primary site per model object in Decaf
is typically considerably less than a Time Warp style
global sweep of the system would be.
The ORESTE [9] implementation provides a useful
model in which programmers define high-level operations
and specify their commutativity and masking re-
lations. One drawback is that there are no high-level
operations on multiple objects, nor are there ways of
combining multiple high-level operations into transac-
tions. To get the effect of transactions, one must combine
what are normally thought of as multiple objects
into single objects and then define new single-operand
operations whose effects are equivalent to the effects
of the transaction. One must then explicitly specify
the interactions between the new operations and all
the other operations.
There is also a subtle difference between the correctness
requirements in Decaf and in ORESTE.
This difference results from the fact that ORESTE
only considers quiescent state - the analysis does not
consider "read transactions" (e.g., snapshots) which
can coexist with "update transactions". For instance,
in the ORESTE model, a transaction which changes
an object's color can reasonably be said to commute
with a transaction which moves an object from container
A to container B, since for example, starting
with a red object at A and applying both "change
to blue" and "move to B" yields a blue object at B
regardless of the order in which the operations are ap-
plied. But once viewers or read-only transactions or
system state in non-quiescent conditions is taken into
account, some sites might see a transition in which a
blue object was at A and others a transition in which
a red object was at B.
Finally, in ORESTE a state cannot be committed
to an external viewer until it is known that there is
no straggler; this involves a global sweep analogous to
Jefferson's Global Virtual Time algorithm. In a system
with a single group of collaborating applications,
this may not be too severe a problem. In a world-wide
web in which sites A, B, and C are collaborating, and
independently sites C, D, and E are collaborating, and
and F are collaborating, etc., it is preferable not to
have commit depend on the global state of the net-
work, but rather on a small number of objects.
A recent system, COAST [14], also attempts to use
optimistic execution of transactions with the MVC
paradigm for supporting groupware applications. Key
differences with our system are the following. First,
COAST only supports optimistic views. Second, concurrency
algorithms used in COAST assume that all
model objects in the application are shared among all
participants. Furthermore, the optimistic algorithm
implemented in COAST is based on a variation of the
algorithm discussed above.
5.2 Status and Experience
A substantial implementation of the Decaf frame-work
has been completed in the Java programming
language. The framework currently supports scalar
model objects, transactions, and optimistic and pessimistic
views. The implementations of these objects
use the algorithms described in this paper. Several
optimizations are forthcoming, including commit del-
egation, faster commit of snapshots, and incremental
propagation. We are currently implementing composite
model objects.
Several collaborative applications have been successfully
built using the current prototype implemen-
tation. These include several groupware applications
that allow an insurance agent to help clients understand
insurance products via data visualization and
fill out insurance forms, a multi-user chat program,
and simple games. Our preliminary experience is that
it is easy to write new applications or to modify existing
programs to use our MVC programming para-
digm. Optimistic views have been very useful due to
their fast response, and also due to the low conflict
rate in typical use. Pessimistic views have also been
useful for viewers that want to track all changes to the
values of model object.
6 Conclusions
The Decaf framework's major objectives are ease
of programming, and responsiveness in the context of
systems of collaborating applications.
The ease of programming is achieved primarily
through hiding all concerns about distribution, multi-
threading, and concurrency from users. Programmers
write at a high level, using the Model-View-Controller
paradigm, and our implementation transparently converts
operations on model objects to operations on
distributed replicated model objects. The View Notification
algorithm automatically schedules view snap-shots
at appropriate times and also allows viewers
to respond efficiently to small changes to large ob-
jects. Model objects for standard data types (Inte-
gers, Strings, etc.) and collections (e.g., Vectors) are
provided as part of the Decaf infrastructure.
The responsiveness results from the use of optimism
combined with the fast commit protocol of the primary
copy algorithm. If a transaction updates objects
A and B, then a viewer of B 0 , a replica of B, sees the
commit as soon as A's primary site and B's primary
site have each notified the originating site that the
updates are non-conflicting, and the originating site
has notified B 0 's site that the transaction has com-
mitted. This is a small delay, even for a pessimistic
view. Users can get even more rapid response time
using optimistic views, and most of the time their optimistic
view will later be committed with the same
speed as the pessimistic view.
Our experience with using Decaf has shown the
architecture and algorithms to be well suited for a variety
of groupware applications.

Acknowledgements

We gratefully acknowledge Gary Anderson's input to
the design of our framework. He has also built several
collaborative applications and components on top of
our framework.



--R

XTV: A frame-work for sharing X window clients in remote synchronous collaboration
Optimistic parallelization of communicating sequential processes.
Pat Stephen- son
The exclusive- writer approach to updating replicated files in distributed processing systems

Concurrency control in groupware systems.
The time warp mechanism for database concurrency control.
Virtual time.
An algorithm for distributed groupware applications.
A Cookbook for Using the Model-View-Controller User Interface Paradigm in Smalltalk-80


Support for building efficient collaborative applications using replicated objects.
Jan Schum- mer
Synthesizing distributed and parallel programs through optimistic transformations.
--TR

--CTR
Sumeer Bhola , Mustaque Ahamad, 1/k phase stamping for continuous shared data (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.181-190, July 16-19, 2000, Portland, Oregon, United States
Guruduth Banavar , Sri Doddapaneni , Kevan Miller , Bodhi Mukherjee, Rapidly building synchronous collaborative applications by direct manipulation, Proceedings of the 1998 ACM conference on Computer supported cooperative work, p.139-148, November 14-18, 1998, Seattle, Washington, United States
Christian Schuckmann , Jan Schmmer , Peter Seitz, Modeling collaboration using shared objects, Proceedings of the international ACM SIGGROUP conference on Supporting group work, p.189-198, November 14-17, 1999, Phoenix, Arizona, United States
James Begole , Randall B. Smith , Craig A. Struble , Clifford A. Shaffer, Resource sharing for replicated synchronous groupware, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.833-843, December 2001
Wanlei Zhou , Li Wang , Weijia Jia, An analysis of update ordering in distributed replication systems, Future Generation Computer Systems, v.20 n.4, p.565-590, May 2004
optimistic concurrency control;pessimistic views;optimistic views;groupware;replicated objects;model-view-controller programming paradigm