Passive-space and time view: vector clocks for achieving higher performance, program correction, and distributed computing

Abstract

We have noticed two problems with viewing a process as a sequence of events. The first problem is the complete loss of information about potential intra-process concurrency for both sequential and distributed computations, and partial loss of information about potential inter-process concurrency for distributed computations. The second problem is that the resulting reasoning framework does not lend itself to refinement (from sequential computing or a given set of distributed processes) to a preferable set of distributed processes. We argue that it is more natural to view a computation, either distributed or sequential, as a partially ordered set of events. Doing so leads to a view, called passive-space and time view, which we propose. To aid users of the relation "Affects" in developing algorithms, we define vector clocks, that are global logical clocks, so that the relation "Affects", and hence all potential concurrency, between events can be identified from their timestamps assigned.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>