UNIT-3

Agreement Protocol in Distributed System

1 Vijay S. Katta

Topic addressed in UNIT 3

 Agreement Protocol

 Distributed Resource Management / File system

Management

 Distributed Shared Memory (Logical Implementation )

 Distributed Scheduling / Load Balancing

2 Vijay S. Katta

1
 AGREEMENT PROTOCOLS

3 Vijay S. Katta

Introduction
 Processes/Sites in distributed systems often compete as well
as cooperate to achieve a common goal.

 Mutual Trust/agreement is very much required.

 In Distributed Data bases, there may be a situation where data

managers have to decide “Whether to commit or Abort the
Transaction”.

4 Vijay S. Katta

2
 Introduction Cont…
 When there is no failure, reaching an agreement is
easy.

 However, in case of failures, processes must exchange

their values with other processes and relay the values
received from others several times to isolate the
effect of faulty processor.

 Agreement Protocols helps to reach an agreement in

presence of failures.

5 Vijay S. Katta

Synchronous VS Asynchronous Computation

 Synchronous Computation
1. Processes run in lock step manner [ Process receives a message sent to
it earlier, performs computation and sends a message to other process ] .
2. Step of Synchronous computation is called round.

 Asynchronous Computation
1. Computation does not proceed in lock step.
2. Process can send receive messages and perform computation at any
time.

Synchronous Models of Computations are Assumed

here.
6 Vijay S. Katta

3
System Model
 Agreement Problems have been studied under following System
Model:

1. ‘n’ processors and at most ‘m’ of the processors can be

faulty.
2. Processors can directly communicate with other processors
by message passing.
3. Receiver knows the identity of the sender.
4. Communication medium is reliable. (No uncertain delay)
5. Only Processors are prone to failures.

7 Vijay S. Katta

Model of processor Failures

 Processor Can Fail in three modes:
1. Crash Fault :
(i) Processor stops and never resumes operation.

2. Omission Fault :
(i) Processor Omits to send message to some processors.

3. Malicious Fault :
(i) Also known as Byzantine Faults.
(ii) Processor may send fictitious values/message to other processes to
confuse them.
(iii) Tough to detect/correct.

8 Vijay S. Katta

4
Authenticated VS Non-Authenticated Messages
 Authenticated Messages:
1. Also known as signed Message.
2. Processor can not forge/change a received message.
3. Processor can verify the authenticity of the message.
4. It is easier to reach on an agreement in this case.

 Non-Authenticated Messages:
1. Also known as Oral Message/unregistered message.
2. Processor can forge/change a received message and claims to have
received it from others.
3. Processor can not verify the authenticity of the message in this case.

9 Vijay S. Katta

Performance Aspects of Agreement Protocols

 Following Metrics are used :

1. Time: No of rounds needed to reach an agreement.

2. Message Traffic : Number of messages exchanged to reach an

agreement.

3. Storage Overhead : Amount of information that needs to stored at

processors during execution of the protocol.

10 Vijay S. Katta

5
Agreement Issue

 1 1
P2
0

 1

P1 P3
 0
 1= Commit
 0= Abort/ Do not commit

11 Vijay S. Katta

Classification of Agreement Problems

 There are three well known agreement problems in distributed
systems:
1. Byzantine Agreement Problem :

2. Consensus Problem:

3. Interactive Consistency Problem:

Cont..
12 Vijay S. Katta

6
Classification of Agreement Problems
 There are three well known agreement problems in distributed
systems:
1. Byzantine Agreement Problem :
 A single Value is to be agreed upon.
 Agreed Value is initialized by an arbitrary processor and all non faulty
processors have to agree on that value.
2. Consensus Problem:
 Every processor has its own initial value and all non faulty processors
must agree on a single common value.
3. Interactive Consistency Problem:
 Every processor has its own initial value and all non faulty processors
must agree on a set of common values.

Cont..
13 Vijay S. Katta

Classification of Agreement Problems

cont…

 In All the previous mentioned problems, all non faulty processors must
reach an agreement

 In Byzantine and Consensus problems , agreement is on a single value

 In Interactive Consistency problem , agreement is on a set of common

values.

 In Byzantine agreement problem ,only one processor initializes the value

where as in other two cases, every processor has its own initial value.

14 Vijay S. Katta

7
Byzantine Agreement Problem
 Source Processor [ Any arbitrarily chosen processor] broadcasts its
values to others.

 Solution must meet following objectives:

1. Agreement : All non-faulty processors agree on the same value.
2. Validity : If source is nonfaulty, then the common agreed value must be
the value supplied by the source processor.

“If source is faulty then all non- faulty processors can agree on any common
value”.
“Value agreed upon by faulty processors is irrelevant”

Example:- Commit, rollback, checkpoint, Byzantine fault tolerance in block

chain
15 Vijay S. Katta

Consensus Problem
 Every Processor broadcasts its initial value to all other processors.
 Initial Values may be different for different processors.
 Protocol must meet following objectives:
1. Agreement : All non-faulty processors agree on the same single value.
2. Validity : If initial value of every non-faulty processor is v , then the
common agreed value by all non-faulty processors must be v.

“If initial value of non-faulty processors are different then all non- faulty
processors can agree on any common value”.
“Value agreed upon by faulty processors is irrelevant”

Example:- 2 phase/3 phase commit/ rollback, Blockchain (Proof of work, Proof

of stake used in Bitcoin, Ethereum and selection of next node by miner),
consensus in cloud computing services(D3, Dynamo DB), Distributed file
system (G- Drive), clock synchronization, voting problems

16 Vijay S. Katta

8
Interactive Consistency Problem

 Every Processor broadcasts its initial value to all other processors.

 Initial Values may be different for different processors.

 Protocol must meet following objectives:

1. Agreement : All non-faulty processors agree on the same vector

(v1,v2,…vn).

2. Validity : If ith processor is non-faulty and its initial value is vi, then the
ith value agreed by all non-faulty processors must be vi.

“If jth processor is faulty then all non- faulty processors can agree on
any common value vj”.

“Value agreed upon by faulty processors is irrelevant”

Example:- Channel access in broadcast, multicast, fault tolerance in flight
17 control system. Vijay S. Katta

Solution for Byzantine Agreement Problem

 First Defined and solved by Lamport.
 Source Broadcasts its initial value to all other processors.
 Processors send their values to other processors and also relay received
values to others.
 During Execution faulty processors may confuse by sending conflicting
values.
 However if faulty processors dominate in number, they can prevent non-
faulty processors from reaching an agreement.
 No. of faulty processors should not exceed certain limit.
 Pease showed that in a fully connected network, it is impossible to reach
an agreement if number faulty processors ‘m’,
 m > (n-1)/3.
where n = number of processors

18 Vijay S. Katta

9
Lamport-Shostak-Pease Algorithm
 This algorithm also known as Oral Message Algorithm OM(m) where
m is the number of faulty processors.

 ‘n’ = Number of processors and n >= 3m+1

 Algorithm is Recursively defined as follows:

 Algorithm OM(m=0) i.e OM(0)

1. Source processor sends its values to every processor.
2. Each processor uses the value it receives from source. [If no value is
received default value 0 is used].

19 Vijay S. Katta

Lamport-Shostak-Pease Algorithm Cont…

 Algorithm OM(m), m>0
1. The source processor sends its value to every processor.

2. For each i, let vi be the value processor i receives from source.[ Default
value 0 if no value received]
3. Processor i acts as the new source and initiates Algorithm OM(m-1)
where it sends the value vi to each of the n-2 other processors.
4. For each i and j (not i), let vj be the value processor j received from
processor i in STEP 3. Processor j uses the value majority(v1,v2….vn-1).

“The function majority(v1,v2….vn-1) computes the majority value if

exists otherwise it uses default value 0.”

20 Vijay S. Katta

10
Po non faulty source and P2 is faulty

21 Vijay S. Katta

Byzantine Agreement Can not be reached among three

processors if one processor is faulty

P0 is source processor

P0 is NON-Faulty P0 is Faulty

P0
P0
1 0
1 1
1
1 P1 P2
P1 P2
0
1

22 Vijay S. Katta

11
Applications of Agreement Algorithms
1. Fault-Tolerant Clock Synchronization
 Distributed Systems require physical clocks to synchronized.
 Physical clocks have drift problem.
 Agreement Protocols may help to reach a common clock value.

2. Atomic Commit in DDBS

 DDBS sites must agree whether to commit or abort the transaction.
 Agreement protocols may help to reach a consensus.

23 Vijay S. Katta

Fault –Tolerant Clock Synchronization

 Works on following Assumptions:-
A1:- All clocks are initially synchronized to approximately
the same value
A2:- A nonfaulty process’s clock runs at approximately the
correct rate( one second of clocktime per second real
clock time.)
A3:- A nonfaulty process can read the clock value of
another nonfaulty process with at most a small error
ε.

24 Vijay S. Katta

12
Fault –Tolerant Clock Synchronization
 Satisfy following two condition
A. At any time, the value of clocks of all non-faulty
processors are approximately the same value.

B. There is a small bound on the amount by which

the clock of a non-faulty process is changed
during each resynchronization.

25 Vijay S. Katta

Clock synchronization algorithm

 Interactive Convergence Algorithm

 Interactive Consistency algorithm

26 Vijay S. Katta

13
Interactive Convergence Algorithm

 Interactive Convergence Algorithm assumes that clocks

are initially synchronized and that they are re-
synchronized often enough so that two nonfaulty clocks
never differ by more than ∂

27 Vijay S. Katta

(1) Interactive Convergence Algorithm

 Algorithm:-

 All process reads the value of other processors clock

and set value to the average of these values.

 However, if clock values differs from its own clock

value by more than ∂,it replace that value by its own
clock value when taking average.

28 Vijay S. Katta

14
(2) Interactive Consistency algorithm
 Use median of clock value rather than mean.
 When faulty values are less median provide good
approximation.

 To find the median number:

 Put all the numbers in numerical order.
 If there is an odd number of results, the median is the
middle number.
 If there is an even number of results, the median will be
the mean of the two central numbers.

29 Vijay S. Katta

Dolev et al.’s Algorithm of agreement

Home Work protocol.
(Book: Shivaratri. Page:- 187)

30 Vijay S. Katta

15