PaperlayerView exact revision on arXiv

Source-linked AI summary

XFT: Practical Fault Tolerance Beyond Crashes

Shengyun Liu, Paolo Viotti, Christian Cachin, Vivien Quéma, Marko Vukolić

arXiv:1502.05831v3cs.DC

TL;DR

Practical BFT has been hindered by extra resource cost and an adversary model that coordinates Byzantine faults with network asynchrony. The paper introduces XFT and XPaxos for SMR, showing stronger reliability than CFT, sometimes stronger than BFT, while matching state-of-the-art CFT performance.

  • Problem

    Asynchronous BFT has not been adopted practically because it costs more resources than CFT and assumes an adversary can coordinate Byzantine machines with the entire network.

  • Method

    XFT builds SMR systems that tolerate Byzantine faults with network asynchrony when a majority of replicas are correct and communicate synchronously.

  • Results

    XFT provides stronger consistency and availability guarantees than CFT, can exceed BFT under some fault probabilities, and XPaxos performs almost as well as WAN-optimized Paxos.

  • Takeaways & Limitations

    XFT offers practical resilience beyond crashes without extra replica resources compared with asynchronous CFT.

  • Takeaways & Limitations

    The paper does not explore varying tolerated faults per fault class, and its large-replica active-group modification is left outside the scope of the paper.

Abstract

from arXiv · show

Despite years of intensive research, Byzantine fault-tolerant (BFT) systems have not yet been adopted in practice. This is due to additional cost of BFT in terms of resources, protocol complexity and performance, compared with crash fault-tolerance (CFT). This overhead of BFT comes from the assumption of a powerful adversary that can fully control not only the Byzantine faulty machines, but at the same time also the message delivery schedule across the entire network, effectively inducing communication asynchrony and partitioning otherwise correct machines at will. To many practitioners, however, such strong attacks appear irrelevant. In this paper, we introduce cross fault tolerance or XFT, a novel approach to building reliable and secure distributed systems and apply it to the classical state-machine replication (SMR) problem. In short, an XFT SMR protocol provides the reliability guarantees of widely used asynchronous CFT SMR protocols such as Paxos and Raft, but also tolerates Byzantine faults in combination with network asynchrony, as long as a majority of replicas are correct and communicate synchronously. This allows the development of XFT systems at the price of CFT (already paid for in practice), yet with strictly stronger resilience than CFT --- sometimes even stronger than BFT itself. As a showcase for XFT, we present XPaxos, the first XFT SMR protocol, and deploy it in a geo-replicated setting. Although it offers much stronger resilience than CFT SMR at no extra resource cost, the performance of XPaxos matches that of the state-of-the-art CFT protocols.

1 Introduction

The paper introduces XFT to tolerate Byzantine and network faults without the extra replica cost of asynchronous BFT, targeting practical distributed systems. XPaxos implements XFT for SMR, preserving CFT reliability guarantees while providing stronger resilience and near-Paxos performance.

  • Motivation: Modern distributed systems need resilience to hardware faults, disasters, network faults, and non-crash faults that can corrupt service.Cloud-scale outages directly affect the businesses that depend on them.
  • Motivation: Asynchronous BFT requires at least 3t + 1 replicas, compared with 2t + 1 for CFT, because its adversary controls Byzantine machines and the entire network.The paper argues this adversary model is stronger than many deployed failure scenarios require.
  • XFT: XFT tolerates Byzantine faults and network asynchrony while using no extra replicas and preserving asynchronous CFT guarantees when Byzantine faults are absent.Its target setting is one where a majority of replicas remain correct and communicate synchronously.
  • XPaxos: XPaxos is the first XFT SMR protocol and uses 2t + 1 replicas, with evaluation deployed through Apache ZooKeeper across worldwide Amazon EC2 datacenters.The deployment evaluates XFT in a geo-replicated setting.
  • Evaluation: XPaxos performs almost as well as WAN-optimized Paxos in throughput and latency while offering broader failure coverage than CFT SMR.The supplied passage states that it performs significantly better than an additional comparison protocol, but the excerpt is truncated before naming it.
  • Reliability analysis: Under some independent machine- and network-fault probabilities, XFT provides stronger consistency and availability guarantees than CFT and can exceed BFT on both.The paper’s reliability analysis compares resource-optimal CFT, BFT, and XFT protocols using numbers of nines.

2 System model

The system model defines replicas, clients, crash and non-crash faults, asynchronous communication, and partitioned replicas. SMR requires safety and liveness, while partitioning is measured relative to the largest mutually timely communicating subset.

  • Machines: The message-passing system contains n replicas, denoted Π, plus a separate set C of client machines.Clients communicate with replicas, which commit client requests.
  • Faults: Crash faults stop computation and communication, whereas non-crash faults allow arbitrary behavior without breaking cryptographic primitives.Correct machines are non-faulty; benign machines are either correct or crash-faulty.
  • Network: Network faults occur when correct replicas cannot exchange messages and responses within the known deployment-specific delay ∆.The model treats excessive processing delay as a network problem rather than a machine fault.
  • Partitioning: A replica is partitioned when it is outside the largest subset whose every pair can communicate within delay ∆.If multiple maximum subsets exist, only one is recognized as largest; up to n − 1 replicas can be partitioned.
  • Fault measures: At a given moment s, t_p(s) counts correct but partitioned replicas.This quantity complements the counts of crash-faulty and non-crash-faulty replicas.
  • SMR problem: SMR provides safety by totally ordering valid committed requests and liveness by eventually committing requests and returning client replies.Safety covers consistency and validity; liveness covers availability at correct replicas.

3 The XFT model

XFT combines crash and Byzantine fault tolerance by preserving safety under ordinary crash or partition faults and under non-crash faults when a correct synchronous majority exists. Its guarantees are stronger than asynchronous CFT in consistency and availability, stronger than asynchronous BFT in availability, and incomparable with asynchronous BFT in consistency.

  • XFT model: XFT tolerates crash machine faults regardless of network faults, while tolerating non-crash faults when faulty or partitioned replicas remain within a threshold.This redefines the boundary between machine and network fault dimensions.
  • XFT model: Anarchy occurs when at least one replica is non-crash-faulty and no correct synchronous majority exists.XFT protocols must preserve safety in every execution that never enters anarchy.
  • XFT model: XPaxos eventually provides liveness when a majority of replicas are correct and synchronous.The paper states this condition is optimal for deterministic SMR.
  • XFT versus CFT/BFT: Without non-crash faults, XFT preserves consistency despite any number of crash-faulty and partitioned replicas; with non-crash faults, it requires a correct, non-partitioned majority.XFT also guarantees availability whenever a majority of replicas are correct and not partitioned.
  • XFT versus CFT/BFT: XFT preserves consistency in a three-correct-synchronous-replica scenario where authenticated synchronous BFT may violate consistency because one replica is partitioned.XFT is nevertheless weaker when network faults are absent, since authenticated synchronous BFT tolerates more machine faults.
  • XFT versus CFT/BFT: XFT offers strictly stronger consistency and availability than asynchronous CFT, strictly stronger availability than asynchronous BFT, and incomparable consistency with asynchronous BFT.Outside anarchy, XFT remains consistent with non-crash faults in [n/3, n/2), while asynchronous BFT does not; asynchronous BFT instead remains consistent in some anarchic executions.

4 XPaxos Protocol

XPaxos is an XFT state-machine replication protocol that combines CFT-like common-case communication with decentralized view changes and fault detection. It uses synchronous groups of t + 1 replicas, supports stronger fault scenarios without extra replica resources, and preserves consistency and availability under stated conditions.

  • 4.1 XPaxos overview: XPaxos targets geo-replicated systems with high latency and heterogeneous bandwidth, designing SMR specifically for the XFT model.Its three components are a signed common-case protocol, decentralized leaderless view change, and fault detection.
  • 4.2 Common case: The common-case protocol uses communication roughly comparable to Phase 2 of Paxos, while digital signatures harden replicated request ordering.For t ≥2, the primary prepares and forwards requests, followers commit, and replicas execute after receiving t signed follower commits.
  • 4.4 Fault detection: Fault detection uses signed commit-log evidence to detect potentially dangerous data-loss faults outside anarchy before they can combine with enough other faults to threaten consistency.A faulty preceding primary would need data loss in both its commit and prepare logs to violate consistency; signed follower and primary logs expose these faults outside anarchy.
  • 4.1 XPaxos overview: During common-case operation, XPaxos synchronously replicates requests to a synchronous group of t + 1 active replicas among n = 2t + 1 total replicas.Each view determines the group and its primary; commit logs preserve signed proofs for view changes.
  • 4.3 View change: XPaxos reconfigures the entire synchronous group during view change, with all t + 1 new active replicas transferring state in a decentralized process.The mapping from views to synchronous groups is known to all replicas, and groups rotate across views.
  • 4.6 Correctness: XPaxos provides consistency outside anarchy and eventual liveness when a majority of replicas are correct and synchronous.Availability is guaranteed when the synchronous group contains only correct, synchronous replicas, and the protocol eventually completes view change with such a group.

5 Performance Evaluation

The evaluation measures XPaxos in geo-replicated Amazon EC2 deployments, comparing its performance, resource use, and fault scalability with CFT and BFT protocols. XPaxos performs close to Paxos and better than the evaluated BFT protocols, while signature overhead remains bounded.

  • Experimental setup: The evaluation uses geo-replicated Amazon EC2 datacenters to compare XPaxos with PBFT, Zyzzyva, and a WAN-optimized Paxos variant.The study examines throughput, latency, CPU cost, fault-free and faulty scenarios, and ZooKeeper integration.
  • Synchrony parameter: During three months of measurements, inter-datacenter round-trip latency was below 2.5 sec 99.99% of the time, leading to ∆ = 1.25 sec.The measurements used six worldwide EC2 datacenters and least expensive micro instances; network faults lasted up to three minutes.
  • Fault-free performance: XPaxos significantly outperforms PBFT and Zyzzyva in both 1/0 and 4/0 microbenchmarks because its simpler communication pattern reduces WAN costs.The 1/0 benchmark uses 1 kB requests and 0 kB replies; the 4/0 benchmark uses 4 kB requests and 0 kB replies.
  • Fault scalability: With t = 2, XPaxos again clearly outperforms PBFT and Zyzzyva and achieves performance very close to Paxos.Paxos and XPaxos suffer only a moderate performance decrease relative to the t = 1 case.
  • CPU cost: XPaxos uses more CPU than the other protocols because of digital signatures, but its usage remains below half of the eight available cores.CPU usage is higher for 1/0 than for 4/0 because the former handles more messages per unit time.
  • ZooKeeper macro-benchmark: In the ZooKeeper macro-benchmark, XPaxos outperforms BFT protocols and achieves performance close to Paxos while exceeding built-in Zab.The WAN bottleneck is leader bandwidth; XPaxos sends requests to t followers, whereas Zab sends them to all other 2t replicas.

6 Reliability Analysis

The reliability analysis compares XPaxos with asynchronous CFT and BFT under independent machine and network fault probabilities. XPaxos can add reliability over CFT and, under some availability conditions, exceed BFT consistency and availability guarantees.

  • Model: The analysis models machine fault states as independent and identically distributed random variables, with synchrony independently characterized by p_synchrony.A machine is available when it is both correct and synchronous.
  • Consistency: For small configurations, CFT typically loses one nine of consistency relative to the likelihood that a single replica is benign.The approximation applies when n < 10 and p_benign is close to 1.
  • XPaxos vs. CFT: XPaxos adds consistency nines over CFT in proportion to the nines of correct or synchronous machines, rather than directly to p_benign.For t = 1, the paper gives examples where XPaxos adds 2 or 3 nines over CFT.
  • XPaxos vs. BFT: When XPaxos has better consistency than BFT, the advantage is slight and does not produce additional nines in the analyzed cases.One example instead gives BFT 2 additional consistency nines over XPaxos.
  • Availability: For availability, XPaxos matches BFT at t = 1 and adds 1 nine over BFT at t = 2.Against CFT, one example gives XPaxos 5 availability nines versus 4 for CFT.

7 Related work and concluding remarks

The paper concludes that XFT enables software-only protocols with stronger fault resilience than CFT at roughly comparable cost, while distinguishing XFT from hybrid and hardware-assisted approaches. It also identifies varying fault thresholds and applying XFT beyond SMR as future directions.

  • Concluding remarks: XPaxos uses 2t + 1 replicas, preserves CFT reliability guarantees, and tolerates non-crash faults when a majority of replicas are correct and communicate synchronously.The paper reports roughly the same communication complexity, performance, and resource cost as CFT protocols.
  • Related work: XFT is realized entirely in software, unlike approaches that reduce BFT replica costs through trusted hardware.The paper also distinguishes XPaxos from PASC, which uses ASC-hardening and a fault-diversity assumption.
  • Limitations and future work: The paper does not explore varying the number of tolerated faults per fault class, an issue addressed by hybrid fault models.Hybrid models separate thresholds for non-crash faults affecting safety and faults affecting availability.
  • Related work: VFT separately fixes thresholds for non-crash and network faults, whereas XFT cannot be expressed by choosing specific VFT thresholds.The paper characterizes this distinction as fundamental rather than notational.
  • Limitations and future work: The paper proposes examining distributed storage and blockchain through the XFT approach in future work.These problems build on state-machine replication.

Appendix A XPaxos example execution

The XPaxos example shows view changes triggered by both network and non-crash faults. With fault detection enabled, the protocol advances through an additional view and transfers accumulated logs to recover progress.

  • Example setup: Figure 11 illustrates an XPaxos execution with t = 1, showing each replica’s role across views.The example uses Table 2 to identify replica roles in each view.
  • Without fault detection: Without fault detection, a network fault causes s0 to receive only one timely commit message and activate a view change to i + 1.The execution begins with requests r0, r1, and r2 prepared by s0 and committed locally by s1.
  • With fault detection: With fault detection enabled, XPaxos carries commit and prepare logs into view i + 1, where s0 and s2 commit the prior requests and a new request r3.The same execution then identifies s0 as non-crash faulty and changes the view to i + 2.

Appendix B XPaxos pseudocode

The appendix gives XPaxos pseudocode for normal operation, view changes, and client retransmission. It defines replica state, signed message exchanges, log transfer, fault suspicion, and recovery across active replicas.

  • Appendix organization: The appendix organizes XPaxos pseudocode into common-case processing, view change, client request retransmission, and fault-detection view change.Figure 12 defines message fields and local variables, while Figure 13 shows the fault-detection message pattern.
  • Common case: In the common case, clients send requests to the primary, replicas maintain prepare and commit logs, and clients deliver replies after matching signed responses.The protocol has separate common-case algorithms for t = 1 and t > 1.
  • Common case: For t = 1, the primary sends a commit message to the follower, which executes the request, returns a signed result digest, and records the commit log.The primary verifies the follower’s result before returning a reply to the client.
  • View change: During view change, replicas broadcast suspicions, enter views in order, exchange commit logs, and construct a new view from the collected information.Replicas suspect a view when logs do not match or the view-change timer expires.
  • View change: The view-change protocol uses vc-final messages and selects the highest-view commit-log entries before the new primary disseminates the resulting prepare log.Replicas accept the new view when the prepare log matches their commit log.
  • Client retransmission: Client retransmission broadcasts an unacknowledged request to active replicas, which forward it, monitor progress, sign replies, or suspect the current view.A client forwards a suspicion to the next view and resends the request to its primary.

Appendix C XPaxos correctness proof

Appendix C establishes XPaxos’s safety, liveness, and fault-detection properties. It uses the notation introduced in Figure 14 for predicates over benign clients and replicas.

  • Appendix C XPaxos correctness proof: XPaxos’s correctness proof covers safety, liveness, and fault detection.The appendix proves consistency, availability, and fault-detection properties in Sections C.1–C.3.
  • Appendix C XPaxos correctness proof: The proof notation is defined with respect to benign clients and replicas.Figure 14 supplies the notation used throughout the XPaxos proof.

C.1 Safety (Consistency)

The safety proof shows that XPaxos delivers replies from correct execution and preserves a consistent request order across replicas and views. Its lemmas establish uniqueness, durability, and ordered execution of committed requests.

  • C.1 Safety (Consistency): XPaxos safety guarantees that distinct delivered requests are ordered, and accepted requests likewise have a consistent order.Theorem 1 orders distinct delivered requests; Theorem 2 establishes the same ordering for accepted requests.
  • C.1 Safety (Consistency): Accepted replies are produced by correct replicas, and a delivered reply corresponds to an accepted request in some view.Lemma 2 connects delivery with acceptance, while Lemma 3 establishes reply correctness.
  • C.1 Safety (Consistency): If sn < sn′, XPaxos ensures that the request at sn precedes the request at sn′ for benign active replicas.Theorem 3 derives cross-view prefix ordering from the execution and commitment lemmas.
  • C.1 Safety (Consistency): A request executed at a sequence number has been committed, and commitment at the same sequence number is unique and durable across later views.Lemmas 5–8 connect execution to commitment, prove uniqueness, and preserve the committed request across views.

C.2 Liveness (Availability)

The liveness proof shows that correct clients eventually obtain replies. XPaxos either accepts a request in the current view or changes views, and eventual synchrony yields a view containing only correct active replicas.

  • C.2 Liveness (Availability): A correct client’s request eventually becomes accepted in the current view or triggers a change to the next view.Lemma 12 gives this progress-or-view-change alternative.
  • C.2 Liveness (Availability): If a request is not accepted, the correct client resends it to every active replica when its client timer expires.The retry behavior supports continued progress across view changes.
  • C.2 Liveness (Availability): Under sufficient synchrony with a correct client and entirely correct active replicas in a view, the request is eventually accepted.Lemma 13 also states that no timer expires and no view change occurs under these conditions.
  • C.2 Liveness (Availability): Every correct client request is eventually delivered.Theorem 4 uses eventual synchrony and a view containing only correct active replicas to establish liveness.

C.3 Fault detection (FD)

XPaxos’s fault detector is proved strongly complete and strongly accurate outside anarchy. Faults that could cause inconsistency are eventually detected, while benign replicas are never falsely detected.

  • C.3 Fault detection (FD): Outside anarchy, XPaxos’s fault detector has strong completeness and strong accuracy for relevant non-crash faults.The section defines these properties as eventual detection of faulty senders and no detection of correct replicas.
  • C.3 Fault detection (FD): A replica that fails in a way that would cause inconsistency in anarchy is detected as faulty outside anarchy.Theorem 5 states the strong-completeness guarantee.
  • C.3 Fault detection (FD): A benign replica is never detected as faulty by XPaxos’s fault detector.Theorem 6 states the strong-accuracy guarantee.
  • C.3 Fault detection (FD): Once one correct active replica detects a fault during view change, every correct replica eventually detects it.Lemma 15 establishes propagation of fault detection across correct replicas.

Appendix D Reliability analysis (examples)

The appendix compares consistency and availability reliability, expressed in nines, across CFT, BFT, and XPaxos for t=1 and t=2 under practical parameter ranges.

  • Consistency: Tables 5 and 6 compare the nines of consistency for CFT, BFT, and XPaxos when t=1 and t=2.The comparisons use practical values of 9benign, 9synchrony, and 9correct.
  • Availability: Tables 7 and 8 compare the nines of availability for CFT, BFT, and XPaxos when t=1 and t=2.The availability comparisons use 9available and 9benign values in the stated ranges.
  • Consistency: For consistency, the t=1 comparison covers 3 ≤9benign ≤8, 2 ≤9synchrony ≤6, and 2 ≤9correct < 9benign.Table 5 reports 9ofC(CFTt=1), 9ofC(XPaxost=1), and 9ofC(BFTt=1).
  • Availability: For availability, the t=1 comparison covers 2 ≤9available ≤6 and 9available < 9benign ≤8.Table 7 reports 9ofA(CFTt=1), 9ofA(BFTt=1), and 9ofA(XPaxost=1).
Loading 1502.05831v3…