# Shared Flashcard Set

## Details

Comp2005 - Lecture 6 - Distributed Algorithms 1: Logical tim
Alejandro Saucedo - Comp2005 Lecture 5 FlashCard Set
31
Computer Networking
05/17/2013

## Additional Computer Networking Flashcards

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 pi whre i = 1,2...N Each process executes on a single processor and the processors do not share memory Each pi in P has a state si that transforms as it executes The process state includes the values of all variables within it plus Objects, etc. Each process pi can execute either a send or receive operation that transforms pi's state An event is an occurrence of a single action A sequence of events within a single process pi is denoted by the relation -i>  e -i> e' iff event e occurs before e' at pi  We define history as history(pi) = hi =
Term
 What are the characteristics of clocks?
Definition
 Computers each contain their own Operating system reads the node's hardware clock value, Hi, scales it and adds an offset to produce a softare clock Ci(t) = ψHi + B that approximately measure real, physical time t for process pi When the real time in an absolute frame of reference is t, Ci(t) is the reading of the software clock
Term
 What is clock skew?
Definition
 The instantaneous difference between the readings of any two clocks
Term
 What is clock drift?
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) - Ci(t)| < D, for i = 1, 2, ...N and for all real times t in i.    Another way of saying this is that clocks Ci are accurate to  S within the bound D
Term
 How is internal synchornization defined?
Definition
 For a synchronization bound D>0, |Ci(t) - Cj(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 Ci 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
 What is Monotonicity?
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 mr, and receives time value t in a message mt  Process p records total round trip time Tround  P should set clock to (t + Tround/2) Accuracy is +-(Tround/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 mr, and receives time value t in a message mt  Process p records total round trip time Tround  P should set clock to (t + Tround/2) Accuracy is +-(Tround/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
 [image]
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 Happened-before 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 pi has its own logical clock Li, 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 pi with logical timestamp Ti, and e' is an event occurring at pj with logical timestamp Tj, we define the global timestamps for these events to be (Ti, pi) and (Tj, pj) such that (Ti, pi) < (Tj, pj) iff Ti < Tj or Ti = Tj and i < j
Term
 How are totally ordered logical clocks defined?
Definition
 If e is an event occurring at pi with logical timestamp Ti, and e' is an event occurring at pj with logical timestamp Tj, we define the global timestamps for these events to be (Ti, pi) and (Tj, pj) such that   (Ti, pi) < (Tj, pj) iff Ti < Tj or Ti = Tj 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, Vi, which it uses to timestamp local events: Initially set Vi[j] = 0 for i,j = 1, 2, ...N Just before pi timestamps an event it sets Vi[i]++ pi includes the value t = Vi in every message m sent When pi receives a timestamp t in a message m, it sets Vi[j] := max(Vi[j], t[j]), for j = 1, 2, ...N, before incrementing Vi[i] and timestamping event receive(m)
Term
 Show an example of vector timestamps
Definition
 [image]
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 Happened-before 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 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)
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 happened-before 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)
Supporting users have an ad free experience!