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.