CA-514
Unit-3
Agreement Protocols: 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”
• 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.
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 reliabble. 5. Only Processors are prone to failures
Classification of Agreement Problem:
, 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..
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”
Consensus Problem:
Unit-3
Agreement Protocols: 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”
• 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.
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 reliabble. 5. Only Processors are prone to failures
Classification of Agreement Problem:
, 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..
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”
Consensus Problem:
