Consensus based on time – causality

In this model, there is no explicit blocking. Whenever a process (Px) receives a value from another process (P1), and if that value was arrived at a later point in time, then Px overwrites its own copy of the value with what P1 said it was.

Generally, it is not easy to have a common clock source for all processes. The alternatives usually used are vector clocks (designed by Leslie Lamport). Essentially, a vector clock is a vector or an array of counters, one for each Process. Every time a Process sends or receives a message, this counter is incremented. When a Process shares information (the value), it also shares the vector clock it has. The receiving Process updates each element in its own vector by the maximum of the values for each element in the received vector and its own vector.

The point of this is that if every element in the received vector is more (or equal) to the vector in the receiving process, then the receiving process can assume that it has received an updated value, after a state that it's currently in. To put in another way: the process that sent the value had seen the same point in history as the receiving process and now knows a later value. Thus, the receiving process can trust the new value.

When a vector clock, Va, has every counter with a number greater than another vector clock, Vb, Va is said to be a descendant of Vb.

If, on the other hand, this situation does not hold, then the sender process did not see everything that the receiving process did and consensus is not possible through Causality. Some other mechanism must be employed.

To illustrate this, let's look at a sample consensus problem:

Alice, Bob, Charlie, and David are planning to go to a movie together, but need to decide on a day. However, they live in different places and need to call each other to confirm (and a group call is not possible!). The sequence of events is as follows:

  1. Alice meets Bob and they both decide on Wednesday.
  2. David and Charlie decide on Monday.
  3. David and Bob get talking and decide to stick with Wednesday.
  4. Bob calls Charlie, but Charlie says he's already spoken to David and decided on Monday!
  5. Dave's phone is switched off and neither Bob nor Charlie can figure out what day Dave has in mind.

The solution here would be simple if we had a sense of time. In this case, Bob and Charlie would know Dave's latest answer and reach consensus.

In the vector clock world, the ordering would look something like this (Note VC = vector clock):

  1. Alice thinks of Wednesday and send a message to Bob (Day = Wednesday, VC =[ Alice:1]).
  2. Bob acknowledges and updates his value and vector clock. Thus, the state at Bob is as follows:

Day = Wednesday, VC = [ Alice:1, Bob:1]

  1. David calls Charlie and both decide on Monday. Now, the situation for both is as follows:

David

Charlie

Day = Monday

VC = [ David:1]

Day = Monday

VC = [ David:1, Charlie:1,]

  1. Bob calls David and they decide to stick to Wednesday. Now, the situation for both is as follows:

Bob

David

Day = Wednesday

VC = [Alice:1, Bob:2, David:2]

Day = Wednesday

VC = [Alice:1, Bob:1, David:2, Charlie:1]

  1. Bob calls Charlie to propose Wednesday. The two conflicting states with Charlie are as follows:
    • Monday: VC = [ David:1, Charlie:1,]
    • Wednesday: [ Alice:1, Bob:2, David:2]

Charlie can see that David promised Wednesday after he said Monday and a consensus is reached!

The Labix package provides vector clock support in Go: https://labix.org/vclock.

This is a sample hello world example from the website:

package main

import (
"fmt"
"labix.org/v1/vclock"
)

func main() {
vc1 := vclock.New()
vc1.Update("A", 1)

vc2 := vc1.Copy()
vc2.Update("B", 0)

fmt.Println(vc2.Compare(vc1, vclock.Ancestor)) // true
fmt.Println(vc1.Compare(vc2, vclock.Descendant)) // true

vc1.Update("C", 5)

fmt.Println(vc1.Compare(vc2, vclock.Descendant)) // false
fmt.Println(vc1.Compare(vc2, vclock.Concurrent)) // true

vc2.Merge(vc1)

fmt.Println(vc1.Compare(vc2, vclock.Descendant)) // true

data := vc2.Bytes()
fmt.Printf("%#v ", string(data))

vc3, err := vclock.FromBytes(data)
if err != nil {
panic(err)
}

fmt.Println(vc3.Compare(vc2, vclock.Equal)) // will print true
}
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset