` 6 D. Mazieres v1 v6 v2 Q(v) = {v,v } i i (i mod 6)+1 v5 v3 v4 Fig. 4. Cyclic quorum structure example twomiddletiernodes.Notethatv andv maypickdisjointslicessuchas{v ,v }and 9 10 5 6 {v ,v }; nonetheless, both will indirectly depend on the top tier. 7 8 In practice, the top tier could consist of anywhere from four to dozens of widely known and trusted financial institutions. As the size of the top tier grows, there may not be exact agreement on its membership, but there will be significant overlap be- tween most parties’ notions of top tier. Additionally, one can imagine multiple middle tiers, for instance one for each country or geographic region. This tiered structure resembles inter-domain network routing. The Internet today is held together by individual peering and transit relationships between pairs of net- works. No central authority dictates or arbitrates these arrangements. Yet these pair- wise relationships have sufficed to create a notion of de facto tier one ISPs [Norton 2010]. Though Internet reachability does suffer from firewalls, transitive reachability is nearly complete—e.g., a firewall might block The New York Times, but if it allows Google, and Google can reach The New York Times, then The New York Times is tran- sitively reachable. Transitive reachability may be of limited utility for web sites, but it is crucial for consensus; the equivalent example would be Google accepting statements only if The New York Times does. If we think of quorum slices as analogous to network reachability and quorums as analogoustotransitivereachability,thentheInternet’snearcompletetransitivereach- ability suggests we can likewise ensure worldwideconsensuswithFBA.Inmanyways, consensus is an easier problem than inter-domain routing. While transit consumes re- sources and costs money, slice inclusion merely requires checking digital signatures. Hence,FBAnodescanerronthesideofinclusiveness,constructingconservativeslices withgreaterinterdependenceandredundancythantypicallyseeninpeeringandtran- sit arrangements. Anotherexamplenotpossiblewithcentralizedconsensusiscyclicdependencystruc- tures, such as the one depicted in Figure 4. Such a cycle is unlikely to arise intention- ally, but when individual nodes choose their own slices, it is possible for the overall system to end up embedding dependency cycles. The bigger point is that, compared to traditional Byzantine agreement, an FBA protocol must cope with a far wider variety of quorum structures. 3.3. Safety and liveness Wecategorizenodesaseitherwell-behavedorill-behaved.Awell-behavednodechooses sensiblequorumslices(discussedfurtherinSection4.1)andobeystheprotocol,includ- ing eventually responding to all requests. An ill-behaved node does not. Ill-behaved nodes suffer Byzantine failure, meaning they behave arbitrarily. For instance, an ill-