MODULE 3 NOTES

DISTRIBUTED CONSENSUS IN DISTRIBUTED SYSTEMS:

• In distributed systems, achieving consensus among nodes is critical for maintaining

coherence and reliability. This module gives insights of the principles, algorithms,
challenges, and applications of distributed consensus, which are essential for ensuring
agreement across decentralized networks.
• Distributed consensus in distributed systems refers to the process by which multiple
nodes or components in a network agree on a single value or a course of action despite
potential failures or differences in their initial states or inputs.
• It is crucial for ensuring consistency and reliability in decentralized environments where
nodes may operate independently and may experience delays or failures. Popular
algorithms like Paxos and Raft are designed to achieve distributed consensus effectively.

IMPORTANCE OF DISTRIBUTED CONSENSUS IN DISTRIBUTED SYSTEMS:

• Consistency and Reliability: Distributed consensus ensures that all nodes in a distributed
system agree on a common state or decision. This consistency is crucial for maintaining
data integrity and preventing conflicting updates.
• Fault Tolerance: Distributed consensus mechanisms enable systems to continue
functioning correctly even if some nodes experience failures or network partitions. By
agreeing on a consistent state, the system can recover and continue operations smoothly.
• Decentralization: In decentralized networks, where nodes may operate autonomously,
distributed consensus allows for coordinated actions and ensures that decisions are made
collectively rather than centrally.
• Concurrency Control: Consensus protocols help manage concurrent access to shared
resources or data across distributed nodes. By agreeing on the order of operations or
transactions, consensus ensures that conflicts are avoided and data integrity is
maintained.
• Blockchain and Distributed Ledgers: In blockchain technology and distributed ledgers,
consensus algorithms (e.g., Proof of Work, Proof of Stake) are fundamental. They enable
participants to agree on the validity of transactions and maintain a decentralized,
immutable record of transactions.

CHALLENGES ON ACHIEVING CONSENSUS:

Achieving consensus in distributed systems presents several challenges due to the inherent
complexities and potential uncertainties in networked environments. Some of the key challenges
include:

• Network Partitions: Network partitions can occur due to communication failures or

delays between nodes. Consensus algorithms must ensure that even in the presence of
partitions, nodes can eventually agree on a consistent state or outcome.
• Node Failures: Nodes in a distributed system may fail or become unreachable, leading to
potential inconsistencies in the system state. Consensus protocols need to handle these
failures gracefully and ensure that the system remains operational.
• Asynchronous Communication: Nodes in distributed systems may communicate
asynchronously, meaning messages may be delayed, reordered, or lost. Consensus
algorithms must account for such communication challenges to ensure accurate and
timely decision-making.
• Byzantine Faults: Byzantine faults occur when nodes exhibit arbitrary or malicious
behavior, such as sending incorrect information or intentionally disrupting
communication. Byzantine fault-tolerant consensus algorithms are needed to maintain
correctness in the presence of such faults.

DISTRIBUTED CONSENSUS ALGORITHMS IN DISTRIBUTED SYSTEMS:

• Distributed consensus algorithms are fundamental in ensuring that nodes in a distributed

system can agree on a single value or decision despite potential failures, delays, or
differences in their initial states.
• These algorithms play a crucial role in maintaining consistency, reliability, and
coordination across decentralized networks. Here’s an in-depth explanation of key
distributed consensus algorithms:
• Paxos is a classic consensus algorithm which ensures that a distributed system can agree
on a single value or sequence of values, even if some nodes may fail or messages may be
delayed.
o Roles:
o Proposer: Initiates the proposal of a value.
o Acceptor: Accepts proposals from proposers and communicates its acceptance.
o Learner: Learns the chosen value from acceptors.
o Phases:
o Phase 1 (Prepare): Proposers send prepare requests to a majority of acceptors to
prepare them to accept a proposal.
o Phase 2 (Accept): Proposers send accept requests to acceptors with a proposal,
which is accepted if a majority of acceptors agree.
• Paxos Working:
 o Proposers: Proposers initiate the consensus process by proposing a value to be
agreed upon.
o Acceptors: Acceptors receive proposals from proposers and can either accept or
reject them based on certain criteria.
o Learners: Learners are entities that receive the agreed-upon value or decision once
consensus is reached among the acceptors.
o Safety and Liveness:
o Paxos ensures safety (only one value is chosen) and liveness (a value is eventually
chosen) properties under normal operation assuming a majority of nodes are
functioning correctly.
• Use Cases:
o Paxos is used in distributed databases, replicated state machines, and other
systems where achieving consensus among nodes is critical.
• Raft Algorithm:
o The Raft algorithm is a consensus algorithm designed to achieve consensus
among a cluster of nodes in a distributed system.
o It simplifies the complexities of traditional consensus algorithms like Paxos while
providing similar guarantees.
o Raft operates by electing a leader among the nodes in a cluster, where the leader
manages the replication of a log that contains commands or operations to be
executed.
• Raft working:
o Key Concepts:
o Leader Election: Nodes elect a leader responsible for managing log replication
and handling client requests.
o Log Replication: Leader replicates its log entries to followers, ensuring
consistency across the cluster.
o Safety and Liveness: Raft guarantees safety (log entries are consistent) and
liveness (a leader is elected and log entries are eventually committed) under
normal operation.
o Phases:
o Leader Election: Nodes participate in leader election based on a term number and
leader’s heartbeat.
o Log Replication: Leader sends AppendEntries messages to followers to replicate
log entries, ensuring consistency.
o Use Cases:
o Raft is widely used in modern distributed systems such as key-value stores,
consensus-based replicated databases, and systems requiring strong consistency
guarantees.
BYZANTINE FAULT TOLERANCE (BFT) ALGORITHM:

• Byzantine Fault Tolerance (BFT) algorithms are designed to address the challenges posed
by Byzantine faults in distributed systems, where nodes may fail in arbitrary ways,
including sending incorrect or conflicting information. These algorithms ensure that the
system can continue to operate correctly and reach consensus even when some nodes
behave maliciously or fail unexpectedly.
• Key Concepts:
o Byzantine Faults: Nodes may behave arbitrarily, including sending conflicting
messages or omitting messages.
o Redundancy and Voting: BFT algorithms typically require a 2/3 or more
agreement among nodes to determine the correct state or decision.
• Examples:
o Practical Byzantine Fault Tolerance (PBFT): Used in systems where safety and
liveness are crucial, such as blockchain networks and distributed databases.
o Simplified Byzantine Fault Tolerance (SBFT): Provides a simpler approach to
achieving BFT with reduced complexity compared to PBFT.
• Use Cases:

A practical Byzantine Fault Tolerant system can function on the condition that the
maximum number of malicious nodes must not be greater than or equal to one-third of all
the nodes in the system. As the number of nodes increase, the system becomes more
secure.

• PBFT consensus rounds are broken into 4 phases.

o The client sends a request to the primary(leader) node.
o The primary(leader) node broadcasts the request to the all the secondary(backup)
nodes.
o The nodes(primary and secondaries) perform the service requested and then send
back a reply to the client.
o The request is served successfully when the client receives ‘m+1’ replies from
different nodes in the network with the same result, where m is the maximum
number of faulty nodes allowed.

CHALLENGES AND CONSIDERATIONS:

[Link] Partitions and Delays: Algorithms must handle network partitions and communication
delays, ensuring that nodes eventually reach consensus.

[Link]: As the number of nodes increases, achieving consensus becomes more challenging
due to increased communication overhead.
3. Performance: Consensus algorithms should be efficient to minimize latency and maximize
system throughput.

4. Understanding and Implementation: Many consensus algorithms, especially BFT variants, are
complex and require careful implementation to ensure correctness and security.

PRACTICAL APPLICATIONS OF DISTRIBUTED CONSENSUS IN DISTRIBUTED

SYSTEMS:

Below are some practical applications of distributed consensus in distributed systems:

• Blockchain Technology:
o Use Case: Blockchain networks rely on distributed consensus to agree on the
validity and order of transactions across a decentralized ledger.
o Example: Bitcoin and Ethereum use consensus algorithms (like Proof of Work
and Proof of Stake) to achieve decentralized agreement among nodes.
• Distributed Databases:
o Use Case: Consensus algorithms ensure that distributed databases maintain
consistency across nodes, ensuring that updates and transactions are applied
uniformly.
o Example: Google Spanner uses a variant of Paxos to replicate data and ensure
consistency across its globally distributed database.
• Cloud Computing:
o Use Case: Cloud providers use distributed consensus to manage resource
allocation, load balancing, and fault tolerance across distributed data centers.
o Example: Amazon DynamoDB uses quorum-based techniques for replication and
consistency among its distributed database nodes.

NAKAMOTO CONSENSUS:

• Nakamoto Consensus, named after the pseudonymous creator of Bitcoin, Satoshi

Nakamoto, is a Byzantine Fault Tolerant (BFT) consensus mechanism that combines
Proof-of-Work with the "longest chain" rule to create a consensus protocol that
adequately maintains the authenticity of decentralized blockchain networks.
• First implemented in Bitcoin and later adopted by many subsequent cryptocurrencies,
Nakamoto Consensus is the critical innovation that allowed Bitcoin to become the first
BFT system that could scale organically without ever experiencing downtime. It's worth
pointing out that while Nakamoto Consensus is often confused with Proof-of-Work,
they're different. Nakamoto Consensus is a broader consensus protocol that incorporates
Proof-of-Work but also other innovative ideas that make it unique.
• Because Nakamoto Consensus is what makes Bitcoin a Byzantine Fault Tolerant system,
it’s worth first exploring what that means.
• Nakamoto Consensus is said to be a BFT consensus mechanism because it provides a
solution to the Byzantine Generals Problem, a notorious thought experiment in computer
science that grapples with the question of whether it’s possible to achieve lasting
consensus in a computer network composed of independent, geographically distributed
nodes.
• BFT is basically a characteristic of distributed computer networks that can still work even
when some of their nodes are going rogue or acting unpredictably or maliciously. Since
blockchains are exactly that—distributed computer networks—they implement complex
protocols to achieve consensus in a “Byzantine Fault Tolerant” way.
• Nakamoto Consensus Explained as already mentioned, Nakamoto Consensus combines
two novel ideas to achieve Byzantine Fault Tolerance: Proof-of-Work, and the “longest
chain” rule.
• Nakamoto Consensus: Proof-of-Work
• Proof-of-Work (PoW) is a cryptographic mechanism used in blockchain networks to
validate transactions and maintain the network's security. In the case of Bitcoin, it is used
as a consensus algorithm to determine the most valid block in the blockchain.
• The process of validating blockchain transactions involves miners attempting to find a
valid solution to a cryptographic puzzle associated with a new block of transactions.
• The only way for miners to find the solution to the Proof-of-Work puzzle is through trial
and error, or by making thousands of guesses per second until they find one answer that
matches the protocol's criteria.
• The first miner to find the correct answer gets to mine a new block (that, once validated
by all the other full nodes in the network, is appended to the blockchain) and, in return, is
rewarded with newly minted cryptocurrency.
• Finding the Proof-of-Work solution, however, requires significant computing power and
energy consumption, meaning miners also have something to lose, not only gain.
• This means that the Proof-of-Work algorithm relies on a robust incentive mechanism
o guarantees adequate punishment for any individual entity trying to circumvent or
cheat the protocol and
o awards sufficient privileges to all distributed entities that follow the rules of the
agreement.
• Colloquially, this is also known as the "carrot and stick" approach, where the stick is the
electrical energy required for computing complex problems that every mining node must
do to participate in the mining process (i.e., the process of validating transactions), and
the carrot is the block rewards in the form of newly minted bitcoin.
• In other words, the mining nodes that follow the rules of the Proof-of-Work protocol get
rewarded with newly minted bitcoins, while cheating nodes are left with nothing but a
hefty electrical bill for doing useless work.
• This is how Proof-of-Work-based blockchains can achieve real-time consensus between
all participating nodes on the ledger's true state.
• Nakamoto Consensus: Longest Chain Rule
• The longest chain rule, a key component of Nakamoto Consensus, states that in the event
of competing blockchain forks, the chain with the most accumulated computational work,
as measured by the number of blocks in the chain, is considered the correct and valid
chain.
• This means that miners are incentivized to extend the blockchain with the most
accumulated computational work because doing so increases the likelihood that their
blocks will be added to the correct chain and rewarded with cryptocurrency.
• In other words, the longest chain rule encourages miners to work on the same chain and
ensures that the blockchain is maintained and extended by the majority of the network.
• The longest chain rule helps prevent attacks on the network by making it extremely
difficult for an attacker to create a longer valid chain than the existing one.
• Any attacker attempting to create a new, competing chain would need more
computational power than the rest of the network combined, which is currently infeasible
for most blockchains due to the high cost of acquiring and maintaining that much
computational power.
• Overall, the longest chain rule is a critical aspect of Nakamoto Consensus, as it provides
a simple and effective way for the network to converge on a single, valid version of the
blockchain, ensuring that the network operates securely and reliably.
• By utilizing Proof-Work and the longest chain rule, Nakamoto Consensus ensures that
blockchains remain secure and resistant to attacks.
• While it has limitations, this consensus mechanism has proven to be a powerful and
reliable tool for maintaining the integrity of blockchain networks.
• For this reason, many cryptocurrencies beyond Bitcoin use different implementations of
Nakamoto Consensus in their protocols.
• For example, Nervos’ Layer 1, Common Knowledge Base uses Nakamoto Consensus
Max (NC-Max), an improved version of the original Nakamoto Consensus that provides
better security and performance.