1/k Phase Timestamping for Replica Consistency in Interactive Collaborative Applications

Abstract

Interactive Collaborative applications, such as distributed virtual environments, collaborative CAD and multi-player games, are enabled by the data being shared across distributed users. The need to support such applications in a wide-area environment, and at the same time provide fast response to users, motivates replication of this shared data. The key characteristics of this shared data include short, incremental atomic operations for modifying this data,and the application's ability to predeclare access information for these operations. This and certain other differences from conventional replicated databases, motivate a different architecture for algorithms maintaining replica consistency. The main architectural differences include a complete separation of timestamping (for consistently ordering the operations) and execution of operations, propagation of the operation itself (instead of its effect) and local commit. We describe a specific consistency algorithm which does 2 phase timestamping (analogous to 2 phase locking) by sequentially acquiring stamps for objects accessed by an operation. Then we show how to eliminate the shrink phase and reduce the grow phase by a factor of k (when an operation accesses k objects), by concurrently getting all the stamps. This new algorithm is deadlock free and does not abort any operations.