With the numerous computers communicating with each other daily, how do they make decisions? Even in a database or server setup, how do the various computers within the database determine the committed values? How do they synchronize on the correct time? How do they reach a consensus?
But first, let’s understand the concept of consensus in the context of computers. Simply put, it involves all parties involved agreeing on a single value. Nevertheless, the protocol allows for dissenting, incorrect, or faulty agents. Every correct agent must respond, and all correct agents must have the same response. This is crucial for data centers or mesh networks. What happens if the network gets divided, some nodes go offline, or the software crashes unexpectedly, leading to garbled data? One of the most commonly used consensus algorithms is Raft.
1. Raft
The Raft algorithm ensures fault tolerance through an elected leader with proven guarantees. It should be noted that this elected leader can open up vulnerabilities to Byzantine failures, which will be discussed later. Raft is frequently employed by databases such as CockroachDB, Splunk, and MongoDB, as it is well-suited for enabling agents to agree on a set of state transitions, like database transactions. The Raft algorithm generally consists of two main components: leader election and log replication.
Picture a group of servers communicating with each other while a client generates messages. These messages can vary from “set register Y to 6” to “delete row with id = 1230231”. Initially, servers are in a follower state and await communication from a leader via heartbeat signals. If they do not receive a heartbeat within a specified time frame, typically 150 to 300ms, they transition into candidates for election. Servers then cast their votes for the candidates, and in case of a tie, the election term ends, and a new cycle begins. Timeouts are randomized to prevent stalemates.
The client dispatches messages to the current leader, who then replicates these messages to all followers. Once a majority of followers acknowledge the message, it is deemed committed. These messages are appended to a log to maintain consistency across all servers. In the event of leader failure, the logs of the newly elected leader are used, and inconsistent entries are purged. Since any follower vying for election must possess the most recent committed log, it guarantees that data committed by the majority remains intact.
2. Byzantine Failures
Raft/Paxos primarily safeguard against server failures rather than Byzantine failures. The term “Byzantine” is derived from the Byzantine Generals problem, where some generals are unreliable and may deceive. Raft assumes that a crashed system ceases to function and restarts. This assumption may not hold true in a hardware context, where the device might continue producing erratic data, behaving incorrectly, or even being infiltrated by a hostile entity.
However, real-time systems like those on aircraft or spacecraft must consider Byzantine failures. A component might generate incorrect data, necessitating the remaining systems to work around it. This can be achieved through additional messages to validate other servers’ actions, data signing, or even eliminating the concept of a single authoritative leader altogether.
3. Lockstep Protocol
If you’ve ever wondered how real-time strategy games maintain consistency across multiple players with varying connection speeds, consider the Lockstep Protocol. In games like Age of Empires, rather than transmitting the entire game state, only player actions are sent. Each game runs an identical simulation, and every player’s commands are simulated on all computers. While similar to Raft in message passing and log consistency, there is no centralized leader in this protocol; every server also acts as a client. Although there is a host, there exists no absolute authority on the game state.
By implementing a consistent monotonic turn number across all clients, each command is scheduled to run over two turns, facilitating message transmission, acknowledgment, and processing amidst ongoing gameplay simulation. Despite the scalability challenge of ensuring consistency across diverse machines with various processors and architectures, this approach significantly diminishes the potential for cheating.
4. Crypto
Proof of Work serves as the backbone for reaching agreement on the next hash in networks like Bitcoin. This distributed consensus algorithm can accommodate a significant portion of malicious actors. While a detailed discussion on this is beyond the scope here, it underscores the vital aspect of blockchain technology – a decentralized log of entries agreed upon unanimously. Another cryptocurrency, Chia, employs a similar principle using proof of stake instead of proof of work but retaining the fundamental concept at its core.
5. Consensus is Everywhere
Consensus mechanisms are pervasive, spanning from aviation to web services and cryptocurrencies. Consequently, there exist numerous consensus algorithms, each with distinct trade-offs and performance metrics. Next time you embark on a mesh IoT project requiring numerous nodes to concur on shared values, consider incorporating some of the concepts explored here.
Image Source: Pixabay
