Data Replication

There are two primary reasons for replicating data. First, if a resource is replicated, it is still possible to continue working with another replica when one’s crashed. Thus, it increases the reliability of a system. Another reason is performance. Having many replicas enables load balancing between processes working with replicated resources.

Vector Clocks

Lamport clocks has a problem: they do not capture causality. In practice, causality is captured by means of vector clocks. To keep track of causality, each process is assigned with number $i$ and it maintains a vector $\text{VC}_i$ with the following two properties:

  1. $\text{VC}_i[i]$ is a number of events happened at $P_i$ at the current moment.
  2. $\text{VC}_i[j \neq i]$ is a number of events happened at $P_j$ that $P_i$ is aware of.

Using these vectors we can conclude the following:

  1. $V_1=V_2$ if and only if $\forall i\in[1,n]\ : \ V_1[i] =V_2[i]$
  2. $V_1\le V_2$ if and only if $\forall i\in[1,n]\ : \ V_1[i] \le V_2[i]$
  3. $V_1<V_2$ if and only if $V_1\le V_2\quad \text{and} \quad V_1\neq V_2$
  4. $V_1\parallel V_2$ if and only if $\exists i,j:V_1[i]<V_2[i]\quad\text{and}\quad V_1[j]>V_2[j]$

And two events $a$ and $b$ are considered to be causally dependent (e.g. there exists some chain of events linked by a happens-before relation between $a$ and $b$) if $V_a<>V_b$

Using the vector clocks, processes infers information about events causality in the following way:

  1. Before executing an event, $P_i$ executes $\text{VC}_i[i]\leftarrow\text{VC}_i[i] + 1$
  2. When sending a message, the process writes $\text{VC}_i$ to the timestamp of the message.
  3. Upon the receipt of a message a process $P_j$ adjusts its own vector by setting $\text{VC}_j \leftarrow \max \left\{ \text{VC}_j[k],\text{VC}_i[k]\right\}$

Multicasting

Groups allow us to deal with a collection of processes as one abstraction. In other words, it enables us to send message to the whole group as we sent it to one entity. Groups commonly provides the following operations to be performed with them: