L3: Happens-before recap; Partial orders; Total orders; Lamport clocks; Vector clocks

CSE138 (Distributed Systems) by Lindsey Kuper

What is covered in this lecture?

1. Recap of happens-before

2. Partial orders and total orders

3. Lamport clocks

4. Vector clocks

Where are the notes for revising happens-before?

1. Refer Lecture 2 Notes [Link]

Partial Order & Total Order

What is partial order?

1. A given set S and

2. a binary relation, often written as ≤, that lets you compare elements of S, and has the following properties

   1. Reflexivity: for all a, b in S then a ≤ a

   2. Anti-symmetry: for all a, b in S, a ≤ b and b ≤ a ⇒ a = b

   3. Transitivity: for all a, b, c in S, a ≤ b and b ≤ c ⇒ a ≤ c

What is the set of events in case of happens-before relation?

1. Set of all events happened in a particular execution across machines/processes

Is the happens before relation transitive?

1. Yes, it's there in the definition of happen-before relationship

Is antisymmetry true for happens-before?

1. In case of happens-before anti-symmetry means an event A happened before B and also event B happened before A then A = B.

2. So, in this case we can say anti-symmetry is vacuously true

Is reflexivity true for happens-before?

1. In case of happens-before reflexivity means an event A happens before event A. It doesn't makes sense for an event to happen before itself.

2. Hence, reflexivity doesn't hold true.

Is happens-before a partial-order?

1. No, as reflexivity doesn't hold.

2. But it is referred as irreflexive partial order

3. In course, it happens-before might be referred as partial order but it actually means irreflexive partial order

What is a classic example of partial order (reflexive)?

1. Consider set s = { a, b, c }

2. Generate a set S with all possible subset of S = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

3. Binary relation is "set containment" denoted by ⊂

4. All the properties defined above for partial order holds true for (S, ⊂)

   1. [True] Reflexivity: {a} ⊂ {a}

   2. [True] Anti-symmetric: {a, b} ⊂ {b, a} and other way around implies {a, b} = {b, a}

   3. [True] Transitivity: {a} ⊂ {a, b} and {a, b} ⊂ {a, b, c} implies {a} ⊂ {a, b, c}

In above example, there will some elements which are not comparable with the given operator such as {a} and {b}.

What does incomparable pair means?

1. It means either "a operator b" or "b operator a" is not true

2. Because of incomparable pairs we have partial order

Why do we care about incomparable pairs within partial order?

1. These pairs are what we called earlier concurrent events

2. Concurrent event A and B are denoted by A || B

What is the total order?

1. Consider a natural number set and "less than equal to" as binary operator

2. For any two pair of numbers a and b either "a less than equal to b" or "b is less than equal to a" is applicable

3. Such order is called total order

Lamport Clocks

What is a Lamport clock?

1. A kind of logical clock

2. Assigning a number to an event in distributed environment

3. LC(A) = the Lamport clock of event A, it outputs a natural number

What is clock condition?

1. If A → B, then LC(A) < LC(B)

2. Lamport clocks are consistent with potential causality

3. Lamport clocks do not characterize causality

What do we mean by causality in A → B?

1. We can certainly say A happened before B

2. We can potentially say A caused B

What do we mean by "consistent with potential causality"?

1. A → B ⇒ Logical clock of A < Logical clock of B

2. Lamport clocks have this property

What do we mean by "characterizing causality"?

1. Logical clock of A < Logical clock of B ⇒ A → B

2. Lamport clocks do not have this property

What is Lamport clock algorithm?

1. Every process keeps a counter, initialized to 0

2. On every event on a process, that process is going to increment its counter by 1

3. When sending a message, a process includes its current counter

4. When receiving a message, a process sets its counter to the MAX(local, received ) + 1

What is an example of assigning LC numbers to events?

1. Following diagram demonstrates the execution of Lamport clock algorithm

In general, if we know LC(A) < LC(B) does it implies A happens-before B?

1. No, we can prove this with following example.

2. On Lamport diagram if you can reach to B from A by following lines then you know A happened before B else not.

   

What's the point of Lamport clocks? What useful information Lamport clocks provides?

1. Out of all the possible pairs they help rule out a set of relationships where "Event A has not cause event B"

How Lamport clocks help in exclusion scenario?

1. P ⇒ Q (P implies Q) also means NOT Q ⇒ NOT P (contrapositive)

2. A → B ⇒ LC(A) < LC(B), taking contrapositive, NOT (LC(A) < LC(B)) ⇒ NOT (A → B)

3. It means if LC(A) < LC(B) is not true then we can surely say A has not caused B

4. By passing just one number (low overhead for a request) this information is derived.

Vector Clocks

What is a Vector Clock?

1. Its a logical clock

2. Vector clocks are consistent with potential causality

3. Vector clocks also characterizes causality

4. A → B < = > VC(A) < VC(B), A happens-before B if and only if VC(A) is less than VC(B)

What is Vector Clock algorithm?

1. Every process keeps a vector (array) of natural numbers initialized to zeroes

2. Length of the vector = Number of processes e.g. for 3 processes vector initial vector will be [0, 0, 0]

3. On every event (send, receive, and internal), a process increments its own position in its vector clock

4. When sending a message, a process includes its current vector clock (after the increment from step (2) because sends are events)

5. When receiving a message, a process will update its vector clock to MAX(local, received) and also increment its own position because receives are events

What does MAX operation mean for vectors?

1. It performs element-wise maximum

2. For example, MAX([1, 12, 4], [7, 0, 2]) = [7, 12, 4]

How to interpret single entry such as [5, 0, 0] for [Alice, Bob, Carol] process?

1. The single needs to at particular person, let's say at Alice

2. So, we can say Alice has seen 5 events but don't know anything about events a Bob and Carol

3. In case of Lamport clocks if we will just know a number 5 - 5 events have happened but can't get more information like in Vector clocks

Next lecture will continue with example of Vector clocks.

***