In the field of distributed systems, it is crucial for various replicas to agree on a single, consistent state of events, even if some of them fail. Consensus algorithms are used for this purpose, ensuring that the system never accepts conflicting values, and thus the replica logs never diverge. Typical implementations of consensual systems, such as distributed key-value stores, commonly rely on established algorithms like Raft, Paxos, or Viewstamped Replication. These algorithms are well-researched and function reliably in local networks.
However, when deployed on a global scale, where systems are spread across continents and interconnected by networks with high and variable latency, common consensus algorithms encounter fundamental problems. Their reliance on a single leader, who is responsible for the system's progress, becomes an Achilles' heel. If the leader fails, slows down, or disconnects, the entire consensus system either slows down or becomes unavailable until a new leader is elected. For modern distributed systems requiring continuous availability, this situation is unacceptable.
One of the key problems is what is known as destructive interference, which occurs when multiple processes simultaneously attempt to achieve consensus. Take, for example, the Paxos algorithm, which consists of two phases: proposal and acceptance. If, during these phases, two or more proposers concurrently send their proposals, they can block each other, leading to an endless cycle of contention and hindering system progress. To prevent this phenomenon, most implemented consensus algorithms introduce a dedicated leader, who is the sole authorized proposer. While this accelerates decision-making under stable conditions, it also makes the system vulnerable to leader failure.
When a leader fails, the system must elect a new one. Paradoxically, the process of electing a new leader often reintroduces destructive interference. For instance, in the Raft algorithm, candidates contend for a majority of votes, and if multiple candidates attempt to gain votes simultaneously, they can block each other. This can lead to a metastable failure, where the leader election problem persists even after the original cause of the failure (e.g., a short-term network outage) has subsided. An ideal consensus algorithm should do without complex recovery processes that are prone to interference and contribute to outages.
Another fundamental problem is error detection. In large-scale, asynchronous networks like the internet, where messages do not always arrive at predictable times, it is extremely difficult to distinguish between an actual server failure and a mere message delay in the network. Error detectors thus have to "guess" whether the leader is fine or has failed. An incorrect guess triggers the election of a new leader, which halts the system and delays progress. Even when error detection is accurate, it is usually slow – detection timeouts must be set conservatively high, often to multiples of network latency, which in global systems means delays on the order of seconds.
Considering these challenges, the QuePaxa consensus algorithm was developed and published in 2023 by researchers Tennage and Băsescu et al. QuePaxa is designed to effectively achieve consensus in asynchronous environments, without reliance on precise timing or a faultless network. The key principles of QuePaxa are: an optional leader, complete elimination of reliance on error detection, and a design for constructive interference among proposers, meaning cooperation rather than contention.

Planning a new website or app?
Tell me what you have in mind — I will take a look and advise on the best way forward.
In QuePaxa, there are proposers and acceptors. Instead of competing, proposers cooperatively strive for the acceptance of a single proposal. Each proposal is assigned a priority (a random number), with the optional leader always having the highest priority. When a proposer receives a proposal with a higher priority, it adopts it as its own and begins to disseminate it itself. Proposers thus collectively converge on the highest-priority proposal known to them collectively. This prevents mutual blocking, and the system can continuously move forward, albeit with random probability in each round.
The leader in QuePaxa is optional; however, their presence enables a fast path to a decision in a single network round if their proposal is propagated first. Clients can send requests to any proposer, so even if the leader fails, the system does not stop. To leverage this fast path without creating a single point of failure, clients "hedge" their requests by sending them to all replicas. Non-leader replicas then wait for a short "hedging" timeout to allow the leader to decide. If the leader does not decide within this time, other proposers become active.
This "hedging" timeout fundamentally differs from the timeouts used for error detection in other algorithms. It is not tied to network latency but is locally determined by the replicas and can be very short. While a short timeout in Raft would freeze the system, in QuePaxa it only increases the number of active proposers, which might increase network traffic but allows for a faster reaction to changes in the leader's state. Through this approach, QuePaxa proactively addresses leader failure by hedging, instead of reactively detecting errors.
QuePaxa operates in phases that repeat in rounds. Each round consists of four phases. In the first phase (Propose and Adopt), proposers select random priorities and disseminate their proposals. If the leader's proposal (with the highest priority) reaches a majority of acceptors first, the leader immediately decides. Due to the majority intersection property, it is guaranteed that no other proposal can be accepted. If the leader's fast path fails, proposers in subsequent phases (Spread, Check and Decide, Carry Forward) cooperate to converge on the best-known proposal with the highest priority. This gradual convergence ensures that even if the first round fails, work is not lost, and the system continuously moves towards a decision.
In practice, it has been found that systems using QuePaxa continuously process requests, even if the leader fails, disconnects, or slows down, without the system ever completely stopping. Most decisions, typically over 95%, are made by the leader in the first phase, maintaining stable throughput. In cases where a decision is not made in the first phase, throughput temporarily decreases, but the system merely slows down, it does not stop. QuePaxa also allows for dynamic leader change during cluster operation without a significant impact on system stability. This confirms that QuePaxa is a robust and flexible solution for demanding global distributed environments.
