Consensus and agreement
algorithms
Vidya Academy of Science & Technology, Thrissur
Sivadasan E T
Associate Professor
Department of CSE.
Consensus and agreement
algorithms - Introduction
• Agreement among the processes in a
distributed system is a fundamental
requirement for a wide range of applications.
• Many forms of coordination require the
processes to exchange information to
negotiate with one another.
Consensus and agreement
algorithms - Introduction
• To eventually reach a common
understanding or agreement, before taking
application-specific actions.
• A classical example is that of the commit
decision in database systems.
Assumptions
We first state some assumptions underlying our
study of agreement algorithms:
Assumptions
1. Failure models : Among the n processes in
the system, at most f processes can be faulty.
A faulty process can behave in any manner
allowed by the failure model assumed.
The various failure models – fail-stop, send
omission and receive omission, and Byzantine.
Assumptions
Recall that in the fail-stop model, a process may
crash in the middle of a step, which could be
the execution of a local operation or processing
of a message for a send or receive event.
Assumptions
2. Synchronous/asynchronous communication:
If a failure-prone process chooses to send a
message to process Pi but fails, then Pi cannot
detect the non-arrival of the message in an
asynchronous system because this scenario is
indistinguishable from the scenario in which the
message takes a very long time in transit.
Assumptions
In a synchronous system, however, the scenario in
which a message has not been sent can be
recognized by the intended recipient, at the end of
the round.
The intended recipient can deal with the non-arrival
of the expected message by assuming the arrival of
a message containing some default data, and then
proceeding with the next round of the algorithm.
Assumptions
3. Network connectivity : The system has full
logical connectivity, i.e., each process can
communicate with any other by direct message
passing.
Assumptions
4. Sender identification : A process that receives
a message always knows the identity of the sender
process.
This assumption is important – because even with
Byzantine behavior, even though the payload of the
message can contain fictitious data sent by a
malicious sender, the underlying network layer
protocols can reveal the true identity of the sender
process.
Assumptions
5. Channel reliability : The channels are reliable,
and only the processes may fail (under one of
various failure models). This is a simplifying
assumption in our study.
Assumptions
6. Authenticated vs. non-authenticated
messages : In our study, we will be dealing only
with unauthenticated messages. With
unauthenticated messages, when a faulty process
relays a message to other processes,
(i) it can forge the message and claim that it was
received from another process, and
(ii) (ii) it can also tamper with the contents of a
received message before relaying it.
Assumptions
Using authentication via techniques such as digital
signatures, it is easier to solve the agreement
problem because, if some process forges a
message or tampers with the contents of a received
message before relaying it, the recipient can detect
the forgery or tampering. Thus, faulty processes
can inflict less damage.
Assumptions
7. Agreement variable : The agreement variable
may be boolean or multivalued, and need not be an
integer.
When studying some of the more complex
algorithms, we will use a boolean variable.
The Byzantine agreement
The Byzantine agreement problem : The
Byzantine agreement problem requires a
designated process, called the source process, with
an initial value, to reach agreement with the other
processes about its initial value, subject to the
following conditions:
The Byzantine
• Agreement All non-faulty processes must agree
on the same value.
• Validity If the source process is non-faulty, then
the agreed upon value by all the non-faulty
processes must be the same as the initial value
of the source.
• Termination Each non-faulty process must
eventually decide on a value.
The Byzantine
• Agreement All non-faulty processes must agree
on the same value.
• Validity If the source process is non-faulty, then
the agreed upon value by all the non-faulty
processes must be the same as the initial value
of the source.
• Termination Each non-faulty process must
eventually decide on a value.
The Byzantine
• The validity condition rules out trivial solutions,
such as one in which the agreed upon value is a
constant. It also ensures that the agreed upon
value is correlated with the source value.
The Byzantine
• If the source process is faulty, then the correct
processes can agree upon any value.
• It is irrelevant what the faulty processes agree
upon – or whether they terminate and agree
upon anything at all.
Other popular flavors of the
Byzantine agreement problem
• The consensus problem: The consensus
problem differs from the Byzantine agreement
problem in that each process has an initial value
and all the correct processes must agree on a
single value.
The consensus problem:
Formally:
• Agreement: All non-faulty processes must agree
on the same (single) value.
• Validity If all the non-faulty processes have the
same initial value, then the agreed upon value by
all the non-faulty processes must be that same
value.
• Termination Each non-faulty process must
eventually decide on a value.
The interactive consistency
problem
The interactive consistency problem differs from the
Byzantine agreement problem in that each process
has an initial value, and all the correct processes
must agree upon a set of values, with one value for
each process.
The interactive consistency
problem
The formal specification is as follows:
• Agreement: All non-faulty processes must agree
on the same array of values A[v1…vn].
The interactive consistency
problem
• Validity If process i is non-faulty and its initial
value is Vi, then all non-faulty processes agree
on Vi as the ith element of the array A. If process j
is faulty, then the non-faulty processes can agree
on any value for A[j].
• Termination Each non-faulty process must
eventually decide on the array A.
THANK YOU !
