Resettable Vector Clocks
Anish Arora, Sandeep S. Kulkarni and Murat Demirbas
Abstract
Vector clocks (VC) are an inherent component of a rich class of
distributed applications. In this paper, we first consider the
problem of realistic implementation ---more specifically,
bounded-space and fault-tolerant--- of applications that use vector
clocks (VC). 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. This interface contract
is designed for phase-based applications that provide certain
communication guarantees. Based on such substitution and the use of
the interface contract, we show how to transform the client so that it
is itself realistically implemented. We illustrate our method in the
context of Ricart-Agrawala's mutual exclusion program and Garg-Chase's
predicate detection program.
Paper:
Return to the publication list
Return to the Sandeep's home page