• Maintain consistency of distributed data (Timestamps)
• Check authenticity of request sent to a server
• Eliminate processing or duplicate updates

• We take a distributed system to consist of a collection P of N processes p_i whre i = 1,2...N
• Each process executes on a single processor and the processors do not share memory
• Each p_i in P has a state s_i that transforms as it executes
• The process state includes the values of all variables within it plus Objects, etc.
• Each process p_i can execute either a send or receive operation that transforms p_i's state
• An event is an occurrence of a single action
• A sequence of events within a single process p_i is denoted by the relation -_i> 
• e -_i> e' iff event e occurs before e' at p_i 
• We define history as history(p_i) = h_i = <e_i1,e_i2, ...>  

• Computers each contain their own
• Operating system reads the node's hardware clock value, H_i, scales it and adds an offset to produce a softare clock C_i(t) = ψH_i + B that approximately measure real, physical time t for process p_i
• When the real time in an absolute frame of reference is t, C_i(t) is the reading of the software clock

Clocks count at different rates, and so diverge

Clock drift rate is the change in offset (distance in reading) between the clock and a nominal perfect reference clock per unit of time measured by the reference clock

For a synchronization bound D > 0 and for a source S of UTC time |S(t) - C_i(t)| < D, for i = 1, 2, ...N and for all real times t in i. 

Another way of saying this is that clocks C_i are accurate to  S within the bound D

For a synchronization bound D>0, |C_i(t) - C_j(t)| < D for i, j = 1, 2, ...N, and for all real times t in N.

Another way of saying this is that the clocks C_i agree within the bound D

(t - p) (t' - t) <= H(t') - H(t) <= (1 + p) (t' - t)

Such that we define a hardware clock H to be correct if its drift rate falls within a known bound p > 0

Sometimes it si also required tha software clocks obey the condition but only under (Monotonicity means that) the condition that a clock only ever advances:

t' > t => C(t') > C(t)

• Suggests the use of a time server (UTC) to synchronize computers externally
• Upon request, process (time server) S supplies the time according to its clock
• Algorithm is probabilistic - Method achieves synchronization iff the observed round trip times between the client and the server are sufficiently short compared with required accuracy
1. Process p requests tiem in a message m_r, and receives time value t in a message m_t 
2. Process p records total round trip time T_round 
3. P should set clock to (t + T_round/2)
4. Accuracy is +-(T_round/2 - min)
• The downside is that if server fails, it would make synchronization temporarily impossible. Solution is to have time provided by a group of synchronized time servers

1. 
   Process p requests tiem in a message m_r, and receives time value t in a message m_t 
2. Process p records total round trip time T_round 
3. P should set clock to (t + T_round/2)
4. Accuracy is +-(T_round/2 - min)

P can improve accuracy of estimation by making several requests if necessary

1. Machine is chosen as the master or coordinator
2. Master asks each machine for their clock values
3. Master estimates local times for each machine based on the response + half the time taken by the request/reply
4. Master averages the values - including its own time
• Eliminates occasional readings associated with larger times than the nominal maximum time
5. Master sends the amount by which each individual clock requires adjustment (instead of sending current time)

• a -> b . a happened before b
• a || b . a and b are concurrent ~(a->b) and ~(b->a)

• If two events are in the same process, we can know if one happened before the other
• If a message is sent from one process to another we can deduce that sending happened before the receiving
• If x -> y and y -> z then x -> z

• Used to numerically represent the happens before relation. Each process p_i has its own logical clock L_i, which it uses to timestamp events.
• Each clock starts at 0
• When you timestamp event, first increment the clock by 1
• If you send a message, include the current value of your logical clock (after incrementing)
• If you receive a message, find the max of your logical clock, and the value given in the message. Increment this and timestamp the event
• x -> y implies L(x) < L(y)
• L(x) < L(y) Does NOT imply x -> y

• Method of achieving a total order of all events, by incorporating process IDs into the timestamp.
• Some pairs of distinct events, generated by diferent processes have identical Lamport timestamps
• A global logical timestamp of an event is the timestamp of a process, followed by its process ID
• If e is an event occurring at p_i with logical timestamp T_i, and e' is an event occurring at p_j with logical timestamp T_j, we define the global timestamps for these events to be (T_i, p_i) and (T_j, p_j) such that

(T_i, p_i) < (T_j, p_j) 
iff 
T_i < T_j or T_i = T_j 
and 
i < j

If e is an event occurring at p_i with logical timestamp T_i, and e' is an event occurring at p_j with logical timestamp T_j, we define the global timestamps for these events to be (T_i, p_i) and (T_j, p_j) such that

(T_i, p_i) < (T_j, p_j) 
iff 
T_i < T_j or T_i = T_j 
and 
i < j

• V = V' iff V[j] = V'[j] for j = 1, 2, ...N
• V <= V' iff V[j] >= V'[j] for j = 1, 2, ...N
• V < V' iff V <= V' and V != V'

• x => y implies V(x) < V(y)
• V(x) < V(y) implies x -> y
• (x || y) implies ~V(x) < V(y) and ~V(y) < V(x)

• x => y implies V(x) < V(y)
• V(x) < V(y) implies x -> y
• (x || y) implies ~V(x) < V(y) and ~V(y) < V(x)

• Communication channels
• Reliable communication channels exist between each pair of proecsses (all messages eventually delivered)
• Reliable communication protocol masks communication failures
• Additional bounds on delivery time in synchronous systems
• More realistic failure assumption is that failed links between processes are eventually repaired
• Behaviour
• Assume processes only fail by crashing (no arbitrary failures)
• Correct process: does not fail at any point of execution under consideration

• Returns hints: Ususpected/Suspected
• Example
• Each process sends keepalive messages to everyone else every T seconds
• Local failure detector reports Suspected if "Alive" message not delivered within T + D seconds

• Return Unsuspected or Failure (Guarantee)
• Difficult to implement in practice

• Correctness
• Safety: At most one process may execute in critical section at any time
• Liveness: Requests to enter and exit the critical section and eventually succeed
• Accesses to critical section in happening-before ordering
• Performance
• Bandwidth consumption (Number of messages sent in each entry/exit operation)
• Client delay when entering/exiting critical section
• Synchronization delay (Between one process exiting and another one entering critical section)

• Safety: at most one process may execute in critical section at any time
• Liveness: requests to enter and exit the critical section eventually succeed
• accesses to critical section in happened-before ordering

• Bandwidth consumption (number of messages sent in each entry/exit)
• Client delay when entering/exiting critical section
• Synchronization delay (between one process exiting and another one entering)