A framework algorithm for dynamic, centralized dimension-bounded timestamps

Vector timestamps can be used to characterize causality in a distributed computation. This is essential in an observation context where we wish to reason about the partial order of execution. Unfortunately, all current dynamic vector-timestamp algorithms require a vector of size equal to the number of processes in the computation. This fundamentally limits the scalability of such observation systems. In this paper we present a framework algorithm for dynamic vector timestamps whose size can be as small as the dimension of the partial order of execution. While the dimension can be as large as the number of processes, in general it is much smaller.The algorithm consists of three interleaved phases: computing the critical pairs, creating extensions that reverse those critical pairs, and assigning vectors to each event based on the extensions created. We present complete solutions for the first two phases and a partial solution for the third phase.