1/k phase stamping for continuous shared data

Abstract

Interactive distributed applications are a relatively new class of applications that are enabled by sharing continuously evolving data across distributed sites (and users). The characteristics of application data 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. 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 can tolerate crash failures.