PASSIVE-SPACE AND TIME VIEW - VECTOR CLOCKS FOR ACHIEVING HIGHER PERFORMANCE, PROGRAM CORRECTION, AND DISTRIBUTED COMPUTING

We have noticed two problems with viewing a process as a sequence of e vents: The first problem is the complete loss of information about pot ential intra-process concurrency for both sequential and distributed c omputations, and partial loss of information about potential inter-pro cess concurrency for distributed computations. The second problem is t hat the resulting reasoning framework does not lend itself to refineme nt (from sequential computing or a given set of distributed processes) to a preferable set of distributed processes. We argue that it is mor e natural to view a computation, either distributed or sequential, as a partially ordered set of events. Doing so leads to a view, called pa ssive-space and time view, which we propose in this paper. In the prop osed view, a point in space is a passive entity which does not order e vents that occur at it, and the order is determined by the interaction among the events. We define a relation, ''Affects'', between pairs of events, which captures the partial order on events. To aid users of t he relation ''Affects'' in developing algorithms, we define vector clo cks, that are global logical clocks, so that the relation ''Affects'', and hence all potential concurrency, between events can be identified from their timestamps assigned. Since this research is motivated by t he need to solve practical problems, we define passive-space and time view such that a user has control, in two ways, over the costs involve d. First, a process designer may choose any granularity of events and choose any mechanism for determining partial order among events on the process. Second, a user may choose a vector clock such that the exten t of potential intra-process concurrency identified depends on the cos ts associated with the identification. We give vector clocks which tra de cost incurred and concurrency identification. We compare the propos ed view with the space and time view. Finally, we give a scheme for re ducing the cost of communicating timestamps.