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.