1/k Phase Stamping for Continuous Shared Data
Sumeer Bhola and Mustaque Ahamad
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
Interactive distributed applications, such as distributed virtual environments,
collaborative design systems and visualization and on-line steering of
scientific applications are a relatively new class of applications that
are enabled by sharing continuously evolving data across distributed sites
(and users). The data characteristics include very fine-grained updates
that can atomically access a subset of the shared data, masking of update
effects, and irregular locality and contention for access. Due to a number
of reasons, existing programming approaches are not appropriate for programming
such continuous shared data in a wide-area environment. We define an object-set
abstraction, where a set is replicated at sites interested in the objects,
and is modified using add, delete and update operations. The key features
of this abstraction are issue-time access information for update operations,
and the potential for replicating the computation associated with updates.
Ordering of operations is an important problem, and we present a fast,
scalable ordering algorithm, 1/k phase stamping, that uses distributed
tokens that correspond to objects in the set. This algorithm provides substantially
better performance than alternative algorithms, is deadlock and abort free,
and requires no queuing at the tokens. Therefore, tokens can be located
inside a programmable `active' network. The precise stamps generated with
1/k phase stamping enable a dynamic communication optimization technique,
effect and stamp merging, which can reduce communication and allow utilization
of best-effort message delivery. These algorithms have been implemented
in the RAGA system which is fault-tolerant to crash failures.