Safety

The Agreement property, also called uniformity, ensures that no two correct processes decide on different values. This is the core of consensus: all non-faulty nodes must output the same final decision.

• Formal Definition: If a correct process decides value v, then no other correct process decides any value other than v.
• Violation Example: In a blockchain, this would manifest as a fork where two valid chains exist, breaking the single source of truth.
• Mechanisms: Protocols like Paxos, Raft, and PBFT are explicitly designed to guarantee agreement even under failure conditions.

The Validity property ensures that the agreed-upon value is sensible and originates from the system. It prevents trivial solutions where nodes could agree on a predetermined, meaningless value.

• Formal Definition: If all correct processes propose the same value v, then any correct process that decides must decide v. Furthermore, a decided value must have been proposed by some process.
• Purpose: It links the consensus output to the actual inputs of the participants, ensuring the system is useful.
• Contrast with Agreement: Agreement says "everyone gets the same answer." Validity says "the answer must be one of the proposed inputs."

Integrity ensures that a process decides at most once. This property prevents a single node from flip-flopping or producing multiple conflicting decisions for the same consensus instance.

• Formal Definition: No correct process decides twice. Once a value is decided, it is final for that process.
• Relation to Finality: In blockchain contexts, integrity is a component of finality—the guarantee that a block cannot be reverted after being decided.
• Implementation: Consensus protocols achieve this by maintaining persistent state and adhering to strict decision rules that, once triggered, do not re-evaluate.

Irreversibility, often called persistence in blockchain contexts, is the guarantee that once a value is decided by a correct process, it remains decided forever and will not be changed. This is safety over time.

• Contrast with Liveness: Safety (irreversibility) says "nothing bad will happen" (a correct decision won't be undone). Liveness says "something good will eventually happen" (a decision will be made).
• Probabilistic vs. Absolute: Nakamoto Consensus (Bitcoin) provides probabilistic irreversibility (depth-confirmed blocks are extremely unlikely to be reverted). BFT protocols like Tendermint provide absolute irreversibility (instant finality).
• Critical for Applications: Financial settlement and state machine replication depend entirely on this property.

A system is Byzantine Fault Tolerant (BFT) if it maintains safety (and liveness) even when some components fail in arbitrary, malicious ways. This is the strongest form of fault tolerance and a direct enabler of safety in adversarial environments.

• Byzantine Failure: A failure where a node can behave arbitrarily, including lying, sending conflicting messages, or colluding. This models hacking or malicious actors.
• Resilience Threshold: Classical BFT protocols (e.g., PBFT) require that fewer than one-third of the total voting power is Byzantine (n > 3f, where f is the number of faulty nodes).
• Key Mechanism: Redundancy and voting. Enough honest nodes must agree to overcome the votes or influence of malicious ones.

The Safety vs. Liveness trade-off, formalized by the FLP Impossibility result, is a fundamental constraint in asynchronous distributed systems. It states that in an asynchronous network (where messages can be delayed indefinitely), no deterministic consensus protocol can guarantee both safety and liveness in the presence of even a single crash failure.

• FLP Impossibility: Proven by Fischer, Lynch, and Paterson. It means perfect solutions are impossible under perfect models.
• Engineering Solutions: Real-world protocols circumvent this by making partial synchrony assumptions (e.g., messages eventually arrive) or using randomness (e.g., Algorand).
• Protocol Design: This trade-off forces architects to explicitly choose which property is prioritized during network partitions, as reflected in the CAP theorem.

Liveness is the guarantee that a distributed system will eventually make progress and decide on a value, despite delays or failures. It is the complementary property to safety. While safety ensures "nothing bad happens" (e.g., no two correct nodes decide on different values), liveness ensures "something good eventually happens" (e.g., the system eventually reaches a decision). In asynchronous networks, the FLP impossibility result proves that consensus is impossible to guarantee with both perfect safety and liveness in the presence of even a single crash failure, leading to the use of partial synchrony models or probabilistic guarantees in practical systems.

Byzantine Fault Tolerance (BFT) is a property of a distributed system that allows it to reach consensus and continue operating correctly even when some of its components fail arbitrarily, including through malicious or Byzantine behavior. This is a stricter fault model than crash-failure tolerance, as it accounts for nodes that may lie, send conflicting messages, or otherwise deviate from the protocol. Achieving BFT is critical for safety in adversarial environments like open blockchain networks or multi-agent systems with untrusted participants. Classic BFT protocols like Practical Byzantine Fault Tolerance (PBFT) require that less than one-third of the replicas are faulty to guarantee safety and liveness.

Linearizability is the strongest consistency model for concurrent systems, guaranteeing that operations appear to take effect instantaneously at a single point between their invocation and response. This preserves the real-time ordering of operations across all nodes. In the context of consensus and State Machine Replication (SMR), linearizability ensures that all replicas process client requests in an order consistent with their real-time occurrence, which is a key safety property for building predictable, deterministic services. It is stronger than sequential consistency and provides a simple mental model for reasoning about system behavior.

Atomic Broadcast is a communication primitive in distributed systems that guarantees two core properties: Total Order (all correct processes deliver the same set of messages in the same order) and Reliability (if a correct process delivers a message, all correct processes eventually deliver it). Solving Atomic Broadcast is equivalent to solving consensus. It is a fundamental building block for implementing State Machine Replication (SMR), where the totally ordered stream of commands ensures all replicas reach identical states, directly enforcing the safety guarantee that all correct processes agree.

A quorum is the minimum number of votes or participant acknowledgments required in a distributed system to approve an operation, make a decision, or achieve consensus. Quorum systems are designed to ensure safety by guaranteeing that any two quorums have a non-empty intersection of correct nodes. Common patterns include:

• Majority Quorum: Requires responses from a simple majority of nodes.
• Weighted Quorum: Used in systems like Paxos, where a proposal must be accepted by a majority of acceptors. The correct sizing of a quorum is critical to tolerate failures while preventing conflicting decisions.

Two-Phase Commit (2PC) is a distributed algorithm that coordinates all participating processes to either all commit or all abort a transaction, ensuring atomicity across distributed systems. While not a consensus algorithm for arbitrary values, it enforces a critical safety property for distributed transactions:

1. Prepare Phase: The coordinator asks all participants if they can commit.
2. Commit Phase: If all participants vote "yes," the coordinator instructs them to commit; otherwise, it instructs abort. Its main drawback is that it is a blocking protocol—if the coordinator fails, participants may remain in an uncertain state indefinitely, impacting liveness.