Logical time

In any parallel computer system, it is important that causal precedence be maintained. This is true in both multi-threaded/multi-process local systems and distributed systems. When events to accomplish the same task are executed in parallel, there needs to be some sort of synchronization mechanism in place.

Logical time is traditionally how this is accomplished in distributed systems. Logical time allows several disparate processes to reason about causal precedence. For example, assume we have three distributed processes; p1, p2, and p3. The three processes are responsible for executing a task, t1. For simplicity, lets also assume that we know exactly how many events are required to accomplish our task; 10. And finally, we'll also assume the same code to execute any possible event in our task is available at each process.

The first process might start off by assigning events to the other two processes. Although, the processes will most likely be specialized in that the carry out specific functionality. This may be considered a pseudo-event and the real events do not take place until this initial event has completed. We need a logical way of specifying the causal order. The progress of each individual process should be piggybacked along with each inter-process message.

The same holds true with multi-threaded applications. Although they are running on a single machine, they are logically distributed and therefore need to carry-out the same causality precedence property. Multi-threaded applications typically use locks that allow only a single thread to access a critical section while locked. The problem is that this only prevents multiple threads from accessing the critical section simultaneously. Locks do not prevent causal order errors. The same discipline of logical time also needs to be taken into account even on single machines.