Abstract
For all e-collaboration systems, some degree of concurrency control is needed so that two people do not step on each other’s foot. The demand for good concurrency control is especially high for the tightly coupled, real-time e-collaboration systems. Such systems require quick responses to user’s actions, and typically require a WYSIWIS (what you see is what I see) graphical user interface (Ellis, Gibbs, & Rein, 1991). This requirement, together with the fact that users are often separated geographically across wide-area networks, favors a decentralized system design where the system state is replicated at each user’s site. This places further challenges on the design of concurrency control for these systems.
Key Terms in this Chapter
Happened Before: Given two events, e1 and e2, we say e1 happens before e2, or e1 ? e2, if one of the following conditions holds: (1) e1 and e2 happen in the same process, and e1 comes before e2; (2) if e1 is the sending of a message, and e2 is the receipt of the message. The happened-before relationship is transitive; for example, if e1 ? e2 and e2 ? e3, then e1 ? e3.
Locking (Pessimistic, Optimistic): A software lock is associated with each shared object. One must acquire a lock before updating a shared object, and must release the lock once the update is completed. In pessimistic locking, a user must wait until the lock is granted explicitly before updating an object. In optimistic locking, the user can access the shared object as soon as a tentative approval is granted. If the lock request is eventually denied in optimistic locking, the object state must be restored.
Conflicting Operations: Two concurrent operations are said to conflict with each other if both operate on the same object. The granularity of the object is determined by the concurrency control strategy.
Concurrency Control: The activity of coordinating concurrent operations that might be conflicting with each other. Concurrency control determines whether to allow, alter, postpone, or deny the execution of a user’s operation, depending on the relative ordering of the operations under consideration, and the objects on which the operations apply.
Consistency: All copies of replicated system state are identical to each other at each synchronization point. In e-collaboration systems, consistency also implies the preservation of user’s intent. Consistency is achieved through concurrency control.
Precedence Property: Given two operations o1 and o2, o1 is said to precede o2 if and only if the execution of o1 at site S happened before the generation of o2 at site S. The precedence property establishes a partial ordering on different operations.
Operational Transformation: When an out-of-order operation is detected, it is transformed before being applied to the system state to preserve consistency. The transformation requires a set of application-dependent rules.
Group Editor: A type of e-collaboration system allowing multiple geographically distributed members of a team to work on the same document collaboratively in an interactive session.
Serialization (Pessimistic, Optimistic): Serialization relies on establishing a total order of all operations in the system to preserve consistency. In pessimistic serialization, all operations must be executed according to the total order. In optimistic serialization, an operation is executed immediately at the local site and then propagated to remote sites. If an out-of-order operation is detected, either the system rolls back to a consistent state and redoes with the correct total order, or the out-of-order operations are transformed so that an equivalent total order can be realized.