程序代写代做代考 distributed system Distributed Systems Foundations

Distributed Systems Foundations

Vector Clocks

Problem: Detecting causal relations

If L(e) < L(e’) – Cannot conclude that ee’ Looking at Lamport timestamps – Cannot conclude which events are causally related Solution: use a vector clock CS171 2 Vector Clocks • Developed independently by Fidge, Mattern and Schmuck. • Time is represented by a set of n-dimensional non-negative integer vectors. • Each process has a clock Ci consisting of a vector of length n, the total number of processes vt[1..n]. vt[j ] is the local logical clock of Pj and describes the logical time progress at process Pj CS171 3 Vector Clock Protocol • Pi ticks by incrementing its own component of its clock – Ci[i] += 1 • Timestamp C(e) of event e is the clock value after ticking • Each message is piggybacked with the local vector u • Recipient updates local vector to max of u and local vector v CS171 4 5 Vector Clock Protocol • Each process i has a local vector C • Increment C[i] at each “local computation” and “send” event • When sending a message, vector clock value V is attached to the message. At each “receive” event, C = pairwise-max(C, V) user1 (process1) user2 (process2) user3 (process3) (1,0,0) (2,0,0) (3,0,0) (0,0,2) (0,2,2)(0,1,0) (0,0,1) (2,3,2) (0,0,3) C = (0,1,0), V = (0,0,2) pairwise-max(C, V) = (0,2,2) CS171 Vector clocks Protocol 1. Vector initialized to 0 at each process Vi [j] = 0 for i, j =1, …, N 2. Process increments its element of the vector in local vector before event: Vi [i] = Vi [i] +1 3. Piggyback Vi with every message sent from process Pi 4. When Pj receives message, compares vectors element by element and sets local vector to higher of two values Vj [k] = max(Vj [k], Vi [k]) for k=1, …, N CS171 6 Comparing vector timestamps Define V = V’ iff V [i ] = V’[i ] for i = 1 … N V  V’ iff V [i ]  V’[i ] for i = 1 … N V < V’ iff V  V’ and V ≠ V’ For any two events e, e’ e  e’ if and only if V(e) < V(e’) Two events are concurrent if neither V(e)  V(e’) nor V(e’)  V(e) CS171 7 Structure of the Vector Clock • In order to determine if two events e,e’ are causally related or not, just take their vector timestamps V(e) and V(e’): – if V(e)