Wally Jones

The "happened before" relation can't be defined using real clocks because they do not keep precise physical time.

Where (a) occurs before (b) if (a) "happened before" (b).

These events can be thought of as sending and receiving messages in a process.

According to the definition we can see the following is true from Fig. 1. p1 → r4

Also p3 and q3 are concurrent as P won't know what Q did until p4 is received. p3 ↛ q3 and q3 ↛ p3

The definition of this clock is based on the order in which events occur. (a) occurs before (b) if (a) happens at an earlier time than (b)

Clock Condition: if a → b then C(a) < C(b)

So if (a) and (b) are consecutive events in process Pi with: Ci(a) = 4 and Ci(b) = 7 Then the clock ticks 5, 6, 7 occurred between a & b.

Following the clock conditions we can see: C1) there is a tick line between any two process events C2) every message crosses a tick line

These process lines can be thought of as algorithms with the events representing some action of execution.

Each process has a clock represented by a register Ci: Ci(a) is the value contained by Ci during event a. Ci will change between events.

takeaways on IRs: Ci++ between successive Pi events & timestamp = Tm = Ci(a) When Pj receives (m) it must set Cj >= Tm

Total Ordering ⇒ Use arbitrary total ordering of processes to break event ties. ≺ a ⇒ b if: Ci(a) < Cj(b) || Ci(a) = Cj(b) && Pi ≺ Pj

Problem: Only one process can use a single resource at a time. -- Need algorithm to find the total ordering of events to solve the mutex.