Resettable Vector Clocks
Anish Arora, Sandeep Kulkarni, and Murat Demirbas
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
Vector clocks (VC) are an inherent component of a rich class of distributed
applications. In this paper, we consider the problem of realistic ---more
specifically, bounded space and fault-tolerant--- implementation of these
client applications. To this end, we generalize the notion of VC to resettable
vector clocks (RVC), and provide a realistic implementation of RVC. Further,
we identify an interface contract under which our RVC implementation can
be substituted for VC in client applications, without affecting the client's
correctness. Based on such substitution, we show how to transform the client
so that it is itself realistically implemented; we demonstrate our method
in the context of Ricart-Agrawala's mutual exclusion program and Garg-Chase's
predicate detection program.