Time, Clocks, and Ordering of Events

Defined by ->

Event A happened before event B:
-If A and B are in the same process, and A comes before B
-If A is sending a message by a process and B is the precipient of the same message by some other process
-If A -> B, and B -> C, then A -> C

Defined by || (A || B)

Neither event influences each other, and neither A -> B and B -> A

History of messages sent by different users, including where they're going to and who they're from, sent onwards throughout the chain

A clock based on a numbering system not related to the passage of time. Clocks are written as Ci(a)

For any event a, b, if a -> b, then C(a) < C(b).

Only satisfied if:
-a and b are events in Pi and a < b (Ci(a) < Ci(b))
-a is sending a message through Pi, and b is the recipient of that message by Pk (Ci(a) < Ck(b))

Each process has a register Ci (Ci(a) holds value contined in Ci during event a)

Each process increments Ci immediately after the occurence of a local event

If a is an event representing the sending of a message m from Pi to Pj, then m contains the timestep Tm = Ci(a)
-On recieving of m by process Pj at b, peek at m and increment Cj if necessary to ensure Cj(b) > Tm

Defined by =>

Removing of concurrency, getting the events in their complete order.

a => b if (ontop of the other rules):
-Ci(a) < Cj(b)
-Ci(a) = Cj(b) AND Pi < Pj

Events may not happen in an order consistent with the ordering indicated by the clock numbers

This is due to outside events the system cannot account for, such as verbal communication, hence the internal clocks are not incremented

If a => b then C(a) < C(b)

This cannot be attained by a logical clock due to the lack of respect for the real passage of time.

Clocks that run continuously, ticking with the passage of a standard reference time.

Requires two things:
-For a small known constant k (k<1, typically 10^-6) such that for all times t:
--1-k < Ri or Ri <= 1+k (Ri = rate at which the clock Ci runs relative to real time)
--d - kd <= Ci(t+d) - Ci(t) <= d + kd (d = time interval)

-For all i, j and t:
--Either 0 <= Ci(t) - Cj(t) <= sync error (Ci faster than Cj)
--Or 0 <= Cj(t) - Ci(t) <= sync error (Cj faster than Ci)

The allowed error between two different clocks in a system.

This needs to be small enough to prevent anomalous behaviours, but big enough to exist as a sync error of 0 is impossible.

We guarentee avoidance of anomalous behaviour if sync error < (1-k)u (u = time elapsed between sending an recieving) (sync error < minimum transmission time)

Adjust the running rate directly while the crystal oscillations are being turned into the clock "ticks"

A Synchronised clock = physical clock + adj (adj = register containing necessary adjustment)

This is done gradually as to avoid jumps or rollbacks

A reference clock periodically transmits its value to all clocks in the system.

Upon recieving the timestamped message, the clocks A and B set their readings to the indicated value.
-Need to adjust this value based on the maximum travel time (u(mx))
-The most the sync error can be is u(mx)-u