k-Dependency Vectors: A Scalable Causality-Tracking Protocol

In this paper we present a scalable causality-tracking protocol, called k-Dependency Vectors, which piggybacks on each application message a constant number k of integers (with k ≤ n). These integers are selected from a vector of size n which is local at each process. By reducing the size of the piggybacked information, only a subset of the causal dependencies can be "on-the-fly" detected by the checker The other dependencies need an extra computation time to be rebuilt (detection delay). This delay is influenced by the adopted selection strategy. In the paper several selection strategies are proposed and evaluated with respect to the detection delay experienced by the checker.