Term
What are some characteristics on algorithms that depend on clock synchronization? 

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



Term
What problem comes up with algorithms that depend on clock synchronization? 

Definition
Ability to timestamp events at different nodes sufficiently accurately to know the order in which any pair of events occured 


Term
How to order and timestamp events that occur at a single process? 

Definition
 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}, ...>



Term
What are the characteristics of clocks? 

Definition
 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



Term

Definition
The instantaneous difference between the readings of any two clocks 


Term

Definition
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 


Term
How is external synchronization defined? 

Definition
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 


Term
How is internal synchornization defined? 

Definition
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 


Term
What is the relation between internal and external clock synchronization? 

Definition
Clocks that are internally synchronized are not necessarily externally synchronized  however if the system P is externally synchronized with a bound D, then the same system is internally synchronized with a bound of 2D. 


Term
How is the error measuring the interval between real times t and t' (t' > t) bounded? 

Definition
(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 


Term

Definition
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) 


Term
What is cristan's method for synchronizing clocks? 

Definition
 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
 Process p requests tiem in a message m_{r}, and receives time value t in a message m_{t}
 Process p records total round trip time T_{round}
 P should set clock to (t + T_{round}/2)
 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



Term
How is the Christian's Algorithm implemented? 

Definition
Process p requests tiem in a message m_{r}, and receives time value t in a message m_{t}
 Process p records total round trip time T_{round}
 P should set clock to (t + T_{round}/2)
 Accuracy is +(T_{round}/2  min)
P can improve accuracy of estimation by making several requests if necessary 


Term
What are the downsides of Christian's algorithm? 

Definition
If server fails, it would make synchronization temporarily impossible. Solution is to have time provided by a group of synchronized time servers 


Term
What is Berkeley's Algorithm? 

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



Term
Give an example of Berkeley Algorithm 

Definition


Term
What are relations in the Happened Before relation? 

Definition
 a > b . a happened before b
 a  b . a and b are concurrent ~(a>b) and ~(b>a)



Term
How do we know if process x happened before process y in the Happenedbefore relation? 

Definition
 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



Term
What are Lamport Timestamps/Logical clocks? 

Definition
 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



Term
What are totally ordered logical clocks/timestamps? 

Definition
 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 


Term
How are totally ordered logical clocks defined? 

Definition
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 


Term
How do you define Vector clocks formally? 

Definition
System of N processes in an array of N integers. Each process keeps its own vector clock, V_{i}, which it uses to timestamp local events:
 Initially set V_{i}[j] = 0 for i,j = 1, 2, ...N
 Just before p_{i} timestamps an event it sets V_{i}[i]++
 _{pi} includes the value t = V_{i} in every message m sent
 When p_{i} receives a timestamp t in a message m, it sets V_{i}[j] := max(V_{i}[j], t[j]), for j = 1, 2, ...N, before incrementing V_{i}[i] and timestamping event receive(m)



Term
Show an example of vector timestamps 

Definition


Term
What are the definitions of equality on vector timestamps? 

Definition
 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)



Term
What can Vector timestamps tell us about Happenedbefore relation? 

Definition
 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)



Term
What assumptions are made on for failure detection? 

Definition
 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



Term
What are the characteristics of unreliable falure detectors? 

Definition
 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



Term
What are the characteristics of reliable failure detectors? 

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



Term
What are the main principles to have in mind when implementing mutual exclusion? 

Definition
 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 happeningbefore 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)



Term
What does correctness means in distributed mutual exclusion? 

Definition
 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 happenedbefore ordering



Term
What performance issues are taken into account in distributed mutual exclusion? 

Definition
 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)


