In this tutorial you are going to learn about Interactive Consistency Problem in Distributed System.
Consistency In Distributed System
Often, distributed storage systems – like file systems, relational databases or key-valued stores- store a copy of the same data on computers. This is known as replication.
Data is generally replicated to improve performance and enhance reliability. Unfortunately, the replication of the data can compromise its consistency and thereby break programs that are unaware.
The fundamental tension between performance (favouring weak consistency) and correctness (favouring strong consistency) is a recurring theme when designing concurrent and distributed systems and is both practically relevantand all theoretical interest.
Interactive Consistency
Interactive consistency was introduced by Pease, Shostak and Lamport. Distributed consensus is a most fundamental problem in computer science. The goal of the distributed consensus is to reach the agreement in a distributed system in the presence of faults.
A set of n processes, f might be faulty in any given round, are said to have achieved interactive consistency if the local consistency vectors of some n, −f processes are the same.
Interactive consistency is an agreement requirement. Validity is implicitly present in our formulation via the assumption that processes are not allowed to change their private value, combined with the assumption that process i’s consistency vector stores its private value at vector’s ith component.
In the interactive consistency problem, all the processor will have its own first or initial value and all non-faulty processes should agree on a set of values.
- All non-faulty processors should agree on the vector (V1,V2,…,Vn).
- The initial/first values of the processors can be different.
- A protocol/rule for the interactive consistency problem should meet following conditions:
- Agreement: All non-faulty processors agree on the same vector(V1,V2,…,Vn)
- Validity: If the ith processor is non faculty and the initial value is Vi, then the ith value to be agreed on by all non-faulty processors must be Vi.
In the Interactive consistency algorithm, we consider two important conditions:
C1: Any two proceeds obtains an approximately the same value for P’s clock (even if P is faulty).
This condition is important because any two processes always compute the appropriate same medium if they get approximately the same set of clock values for other processes.
C2: If q is a non-faulty process, then every non-faulty process obtains approximate values for process q’s clock.
Example to understand the Interactive Consistency Problem:
Let us consider an example where Processes 1, 3, 4 are trying to learn the local value i2 of Process 2. First, assume no process is faulty in any of the rounds. In this case, Process 2 sends i2 to all three processes in Round 1; that is, in Round 0, we have
∀i : (i2, l2) ∈ S1, S2 = S3 = Sconf = Ø
After Round 1 (focusing only on value sent by Process 2), we have
∀i, j : (ji2, l2) ∈ S2, S3 = Sconf = Ø
After Round 2 (focusing only on value sent by Process 2), we have
∀i, k : ∀j 6 = 2 : (kji2, l2) ∈ S3, ∀i, k : (k2i2, l2) Sconf
So, in Round 3, every Process i updates its consistency vector to have value i2 in cv(i) [2]
– since, for example, (iii2, i2) is received by every Process i.
This article on Interactive Consistency Problem in Distributed System is contributed by Hemalatha P. If you like TheCode11 and would like to contribute, you can also write your article and mail to thecode11info@gmail.com