Symmetry all the way down Ignacio Amores-Sesar1 , Christian Cachin2 , Simon Holmgaard Kamp3 , and Juan Villacis2 1
Aarhus University, Denmark University of Bern, Switzerland 2 Ruhr University Bochum, Germany
arXiv:2607.04887v1 [cs.DC] 6 Jul 2026
2
Abstract Asymmetric trust generalizes classical symmetric quorum systems by allowing each process to specify its own failure assumptions. While this flexibility enables tolerance of strictly more failure scenarios, it is not known if, in these cases, it is actually possible to solve distributed tasks, and if so, which. We answer this question using the depth hierarchy for asymmetric trust (Amores-Sesar et al., OPODIS ’25), which characterizes how much a process must rely on others to solve a task. We prove that asymmetric trust does not increase the solvability of tasks requiring depth two or more, such as reliable broadcast or consensus. Specifically, for any Byzantine asymmetric quorum system, every failure scenario that permits solving a task requiring depth at least two can also be tolerated by a suitably constructed Byzantine symmetric quorum system. We show this via a compiler that transforms asymmetric quorum systems into symmetric ones. The additional failure patterns tolerated exclusively by asymmetric trust correspond to scenarios in which only simpler tasks requiring depth one or less (such as consistent broadcast) can be solved. We further prove that this result is tight in the depth hierarchy, meaning that there exist no compilers that produce symmetric quorum systems that are valid also in failure scenarios where correct processes have depths one or less. Our results clarify the precise power of asymmetric trust. While it strictly enlarges the set of tolerable failure patterns, it does not provide additional strength for solving tasks requiring depth two or higher.
1
Introduction
Solving problems in distributed systems requires making explicit assumptions about the types and patterns of failures that may occur. Most classical systems rely on global adversarial thresholds, which assume that at most f out of n processes may be faulty at any given time. A more general abstraction is provided by symmetric quorum systems [25]. Instead of bounding the number of faulty processes, quorum systems characterize the sets of processes that may concurrently fail, often based on shared properties such as geographic location, operating system, or administrative domain. Under these models, all participants adopt the same trust assumptions. Accordingly, these are referred to as symmetric trust assumptions, and protocols built upon them as symmetric protocols. However, the symmetric model does not capture the heterogeneous and subjective trust relationships that occur in the real world. To address this limitation, asymmetric trust was introduced [13]. In this setting, each process operates under its own trust assumptions, formalized through an asymmetric quorum system. Processes may define their quorums independently, reflecting individual views of which failures are expected. Protocols designed for this environment are known as asymmetric protocols. Another benefit provided by asymmetric trust is that, in fully permissionless environments [20], it provides an alternative to traditional consensus protocols [27, 29] that mitigate Sybil attacks 1
by requiring external resources, such as computational power or capital. A prominent example is the Stellar Consensus Protocol (SCP) [26], which relies exclusively on local, subjective trust decisions, from which global asymmetric quorums emerge organically. By decoupling security from physical or economic resources, asymmetric trust enables consensus in permissionless networks through a completely different approach, based solely on trust relationships, which more closely resembles traditional permissioned BFT algorithms. This gives rise to more efficient and fast protocols. Asymmetric trust has been extensively studied [13, 26, 23, 32, 1, 5, 3, 21] and has been deployed in systems like the XRP Ledger and Stellar. The flexibility of asymmetric trust comes at a cost. Algorithms for this model are typically more complex and difficult to design than their symmetric counterparts. In contrast, symmetric protocols have been studied for decades, and efficient solutions are known for most fundamental tasks. Correct processes in asymmetric trust are characterized using the depth hierarchy [3], a measure of the quality of their trust assumptions with respect to a failure scenario and which generalizes the binary distinction between faulty and correct processes in symmetric systems. Task solvability in the asymmetric setting is tightly connected to depth [3]. Given a failure scenario, for processes with depth zero no tasks can be solved. For processes with depth one, only simple tasks, such as consistent broadcast, are solvable, since this category restricts how much information can be exchanged in the protocol. In contrast, all more complex tasks can only be solved for processes with higher depths of at least two. This includes in particular reliable broadcast or consensus that form the basis of many large-scale distributed systems. The hierarchy that highlights this relationship is a key finding of this work (Table 1). One of the main advantages of asymmetric trust is its ability to tolerate strictly more failure patterns than symmetric trust [1]. In the latter, if the actual failure pattern violates the global assumption (for example, having more than f faults with a threshold failure assumption), correctness may fail for all processes. In asymmetric trust, the impact of such misguided trust assumptions is mostly local to the process that made them, but can still affect other processes. The relationship between this additional fault tolerance and task solvability is poorly understood. In particular, it is unclear if it is actually possible to solve problems in the extra fault tolerance cases, and if so, which tasks can be solved. In this paper, we study this exact relationship. Contribution. We show that for every asymmetric quorum system, all failure scenarios that leave at least one process with depth two can also be tolerated by a suitably constructed symmetric quorum system. The latter is derived from the individual quorum systems of all processes. In the remaining scenarios tolerated only by the asymmetric system, all correct processes have depth at most one, making it impossible to solve tasks that require depth two or more. Thus, for such tasks, every solvable failure scenario under asymmetric trust is also solvable under symmetric trust, enabling the use of simpler symmetric algorithms. Our proof is constructive (Figure 1): we present a compiler that transforms any asymmetric quorum system into a symmetric one with identical fault tolerance for all scenarios containing a process of depth at least two. The resulting quorum system can be efficiently used given the trust assumptions. This improves the best previously existing compiler, which achieved this only for processes with infinite depth [3]. We also show that no compiler exists that achieves the same for all scenarios with a process with depth one. Overall, although asymmetric trust tolerates more failure patterns, this extra tolerance does not increase solvability for tasks requiring depth two or more. For primitives such as reliable broadcast and consensus, symmetric trust is therefore sufficient.
2
Failure scenarios tolerated by asymmetric quorum system Q
Only tasks requiring depth 1 can be solved here
Failure scenarios tolerated by symmetric quorum system S
Figure 1. The set of failure scenarios tolerated by any asymmetric quorum system Q (in striped red) is strictly larger than that which can be tolerated by the symmetric quorum system S = C(Q) derived by the compiler from Q (in green). However, in the failure patterns tolerated by Q but not S, only tasks requiring depth one can be solved, this excludes problems like reliable broadcast or consensus. Organization. The remainder of this paper is organized as follows. Section 2 introduces the model and reviews the key concepts underlying our approach. Section 3 formalizes the asymmetric trust model. Sections 4 presents our main result, the study of the relationship between fault tolerance and task solvability in asymmetric trust. Sections 5 and 6 analyze our results in the two settings asymmetric trust. Section 7 surveys related work on asymmetric trust. Finally, Section 8 presents the conclusions and points to different avenues for future work.
2
Preliminaries
2.1
Model
All algorithms proposed in this paper operate in the asynchronous unauthenticated setting. We consider a system of n processes P = {p1 , . . . , pn } that interact by exchanging messages. A protocol for P consists of a collection of programs, one for each process. We describe protocols using the event-based notation of Cachin et al. [11]. A process that follows its protocol throughout an execution is called correct. A faulty process, also referred to as Byzantine, may crash or deviate arbitrarily from its specification. We assume authenticated channels for message exchange between processes. For a system A ⊆ 2P , the notation A∗ denotes the collection of all subsets of the sets in A, that is, A∗ = {A′ | A′ ⊆ A, A ∈ A}.
2.2
Symmetric trust overview
A symmetric fail-prone system is defined as a family of sets F ⊆ 2P , where each F ∈ F with F ⊆ P is called a fail-prone set and contains all processes that may at most fail together in some execution [25]. They represent the assumption on the possible failure patterns that can occur and, as such, specify all sets of faulty processes that must be tolerated by a protocol. A protocol designed for F achieves its properties as long as the set F of actually faulty processes satisfies F ∈ F ∗ . Symmetric quorum systems, which are specified with respect to a fail-prone system, are specified in Definition 2.1. Definition 2.1 ((Symmetric) Byzantine quorum system [25]). A (symmetric) Byzantine quorum system for F is a collection of sets of processes Q ⊆ 2P where no set is contained in another and each Q ∈ Q is called a quorum, such the following properties hold: Consistency: The intersection of any two quorums contains at least one process that is not faulty, i.e., ∀Q1 , Q2 ∈ Q, ∀F ∈ F : Q1 ∩ Q2 ̸⊆ F. 3
Availability: For any set of processes that may fail together, there exists a disjoint quorum in Q, i.e., ∀F ∈ F : ∃Q ∈ Q : F ∩ Q = ∅. This is a generalization of threshold failure assumptions for Byzantine faults [30]. In the same way in which many tasks can only be solved if n > 3f in the threshold case, Byzantine quorum systems also require a bound on the faulty processes. This is captured through the Q3 condition. Definition 2.2 (Q3 -condition [25, 17]). A fail-prone system F satisfies the Q3 -condition, abbreviated as Q3 (F), whenever it holds ∀F1 , F2 , F3 ∈ F : P ̸⊆ F1 ∪ F2 ∪ F3 . The bijective complement of a process set S ⊆ 2P is defined as S = {P \ S|S ∈ S}. The quorum system Q = F is called the canonical quorum system of F. Lemma 2.1 shows that a Byzantine quorum system exists if and only if the fail-prone system satisfies the Q3 condition. Lemma 2.1 (Byzantine quorum system existence [17]). Given a fail-prone system F, a Byzantine quorum system for F exists if and only if Q3 (F). In particular, if Q3 (F) holds, then F, the canonical quorum system associated to F, is a Byzantine quorum system.
3
Asymmetric trust
We consider the asymmetric trust model proposed by Alpos et al. [1]. We refer the reader to their paper for a full presentation. In protocols with asymmetric trust, each participant is free to make its own individual trust assumptions about others, captured by an asymmetric quorum system. Given a set of processes P, an asymmetric fail-prone system F = [F1 , . . . , Fn ], where Fi represents the failure assumptions of process pi , captures the heterogeneous model. Each Fi is a collection of subsets of P such that some F ∈ Fi with F ⊆ P is called a fail-prone set for pi and contains all processes that, according to pi , may at most fail together in some execution [13]. We can, in turn, proceed to define asymmetric Byzantine quorum systems, denoted by Q. Definition 3.1. An asymmetric Byzantine quorum system Q for F is an array of collections of sets Q = [Q1 , · · · , Qn ] where Qi ⊆ 2P for i ∈ [1, n]. The set Qi ⊆ 2P is a symmetric quorum system of pi and any set Qi ∈ Qi is called a quorum for pi . The system Q must satisfy the following two properties. Consistency: The intersection of two quorums for any two processes contains at least one process for which either process assumes that it is not faulty, i.e., ∀i, j ∈ [1, n], ∀Qi ∈ Qi , ∀Qj ∈ Qj , ∀Fij ∈ Fi∗ ∩ Fj∗ : Qi ∩ Qj ⊈ Fij . Availability: For any process pi and any set of processes that may fail together according to pi , there exists a disjoint quorum for pi in Qi , i.e., ∀i ∈ [1, n], ∀Fi ∈ Fi : ∃Qi ∈ Qi : Fi ∩ Qi = ∅. A kernel is a set of processes that intersects all quorums of a process. That is, for a process pi with quorum system Qi , K is a kernel when K ∩ Q ̸= ∅, ∀Q ∈ Qi . We denote by Ki the set containing all kernels of a process pi . Given an asymmetric fail-prone system F, there will exist a valid asymmetric quorum system for F if and only if F satisfies the B 3 condition [13, 1]. This property is defined as follows. 4
Definition 3.2 (B 3 -condition). An asymmetric fail-prone system F satisfies the B 3 -condition, abbreviated as B 3 (F), whenever it holds that ∀i, j ∈ [1, n], ∀Fi ∈ Fi , ∀Fj ∈ Fj , ∀Fij ∈ Fi ∗ ∩ Fj ∗ : P ̸⊆ Fi ∪ Fj ∪ Fij If B 3 (F) holds, then the canonical quorum system, defined as the complement of the asymmetric fail-prone system, is a valid asymmetric quorum system. Throughout this work, we assume that all quorum systems are canonical, which simplifies the analysis; however, our results also extend to non-canonical systems. Accordingly, when we say that a quorum system satisfies the B 3 or Q3 property, we mean that its associated canonical fail-prone system satisfies the property. In asymmetric systems, processes are still classified as correct or faulty, but correctness admits multiple levels depending on the accuracy of a process’s trust assumptions in a given execution. Let F denote the set of faulty processes. This set is unknown to the processes and can be identified only by an external observer or the adversary. A process pi is said to correctly foresee F if F ∈ Fi∗ , that is, if F is contained in one of its fail-prone sets. Unlike in the symmetric setting, asymmetric systems may include processes that correctly foresee F alongside others whose trust assumptions are incorrect and fail to capture the actual failures. This heterogeneity is captured by the notion of depth [3]. In contrast, symmetric systems implicitly assume that F is always foreseen by the common quorum system. The depth of a process reflects its level of correctness and determines how much it can rely on other processes. We formalize this notion in Definition 3.3. Definition 3.3 (Depth of a process). For an execution with faulty processes F , we recursively define the notion of a correct process having depth d as follows • Any correct process pi has depth 0. • Additionally, a correct process pi has depth d ≥ 1 if it has a quorum such that all processes contained in it have depth at least d − 1, i.e., ∃Q ∈ Qi , ∀pj ∈ Q : pj is correct, has depth s, and s ≥ d − 1 A process with maximal depth d also has depth d′ for all 0 ≤ d′ ≤ d. We focus on the maximal depth of a process. Processes with depth 0, although correct, cannot rely on any of their quorums, processes with depth ∞ can have absolute reliance on other processes. Note that in symmetric systems all processes have either depth ∞ (when trust assumptions hold) or 0 (otherwise).
3.1
Quorum knowledge
Among the many works that study asymmetric trust, some [1, 3, 32] assume that each participant’s trust choices are globally known, while others [26, 23, 21] assume that these choices are known only locally. Despite their prevalence, these settings have not been formally distinguished, and limited attention has been paid to their impact on solvability and algorithm design. We therefore distinguish between the known quorums and unknown quorums settings. In the known quorums setting, each process knows the trust assumptions of every other process, as formalized in Definition 3.4. This setting can be conceptualized via a trusted third party that collects and distributes quorum systems. Upon joining, each process pi submits its quorum system Qi to this party, which verifies the B 3 property, combines the systems into a global quorum system Q, and distributes it to all processes. The consensus protocols of Alpos et al. [1] and Amores-Sesar et al. [3, 5] are designed for this setting. This setting applies in the permissioned, quasi-permissionless, and dynamically available models in the hierarchy of LewisPye and Roughgarden [20]. 5
Definition 3.4 (Known quorums setting). Given an asymmetric quorum system Q and a set of processes P, in the known-quorums setting, each process pi ∈ P has knowledge of Q. In the unknown quorums setting, each process knows only its own quorum system Qi , as formalized in Definition 3.5. This setting raises fundamental challenges for solvability. In particular, many problems require quorum systems to be pairwise intersecting, yet in this setting processes have no way of verifying whether this condition holds. A common approach in the literature [26, 23] is to assume pairwise intersection without providing guarantees when this assumption is violated. The reliable broadcast protocols of Alpos et al. [1] and Amores-Sesar et al. [3], as well as the consensus protocol of Mazières [26], exemplify this approach. Although techniques developed for the unknown quorums setting also apply to the known quorums setting, solutions tailored to the latter often achieve stronger guarantees and better efficiency. This setting applies in the fully permissionless model in the hierarchy of Lewis-Pye and Roughgarden [20]. Definition 3.5 (Unknown quorums setting). Given an asymmetric quorum system Q and a set of processes P, in the unknown-quorums setting, each process pi ∈ P only has knowledge of its own quorum system Qi ∈ Q.
3.2
Characterizing tasks through depth
Problems in distributed computing are typically characterized by abstractions that specify the safety and liveness properties required to hold in an execution [11]. For example, a consensus protocol must satisfy agreement, validity, and termination. A protocol solves a task if every admissible execution of the protocol satisfies the task specification. If such a protocol exists, it is said that the task is solvable. In the symmetric setting, little attention is paid to which processes must satisfy these properties, as it is generally assumed that all correct processes do so. This is reasonable, since correct processes are not meaningfully distinguished from one another in this setting. This changes under asymmetric trust, where correct processes are no longer identical. Instead one can distinguish between naive and wise correct processes [1] and more generally organize them into a depth hierarchy [3], based on the strength of their trust assumptions with respect to a given failure pattern. Their ability to satisfy task properties depends directly on their depth. As such, properties in asymmetric tasks incorporate depth as a parameter for the processes. As an example, consider the asymmetric consistent broadcast task presented in Definition 3.6. Definition 3.6 (Depth-characterized asymmetric Byzantine consistent broadcast). A protocol for asymmetric Byzantine consistent broadcast with sender ps that solves the task for depth d, shortened as CB[d], defined through the events dac-broadcast(m) and dac-deliver(m) satisfies the following properties: • Validity: If a correct process ps dac-broadcasts a message m then eventually all processes with depth d dac-deliver m. • Consistency: If a process with depth d dac-delivers m and another process with depth d dac-delivers m′ , then m = m′ . • Integrity: Every process with depth d dar-delivers m at most once. A protocol is said to solve a task with depth d if, for all executions and failure scenarios having at least one process with depth d, all processes having depth d satisfy the task properties at the end of the execution. If such a protocol exists, one can also say that the task is solvable with depth d. This raises the question of the minimum depth for which there exists a protocol that solves the task. We call this the minimum depth required to solve a task. Finding such depths for different tasks is an open research problem. 6
For consensus and reliable broadcast, the minimum known depths for which there are protocols that solve the problem are ten and three respectively [3]. Decreasing such depths to the lowest values possible is an open research question. It has been shown that there exist no protocols that solve such tasks for depth one [3]. Therefore, the minimum required depth for such problems is at least two, but it could be higher. Similarly, it has been proven that there are no tasks that can be solved for depth 0, as a consequence, all asymmetric tasks require depth at least one [3]. At depth one, only simple tasks requiring minimal inter-process communication can be solved. Consistent broadcast is the main example of such a task. Note that if a task requires depth d, but a failure scenario only leaves processes having depths d′ < d, the task is said to not be solvable for such scenario, as no process is guaranteed to satisfy all the properties required by the task definition. Table 1 summarizes the current characterization of tasks by minimum depths for which a protocol exists, in both quorum knowledge settings. Depth ∞ .. .
Known quorums setting
Unnown quorums setting Partially-synchronous consensus [26]
10 .. .
Asynchronous consensus [3]
3 2 1 0
Reliable broadcast [3]
Reliable broadcast [3]
Consistent broadcast [1]
Consistent broadcast [1]
Table 1. Characterization of tasks by lowest depth for which there is a protocol that solves it, in both settings of asymmetric trust. The red highlighted depth (0) shows the space where no tasks are solvable, the orange highlighted depth (1) shows the space where only simple tasks, like consistent broadcast, can be solved. Many core distributed tasks such as reliable broadcast and consensus require depth at least two.
4
On the fault tolerance of asymmetric trust
One of the main advantages of asymmetric trust is its greater fault tolerance compared to symmetric trust [13]. Its complex and heterogeneous structure enables the tolerance of failure patterns that cannot be handled by standard symmetric quorum systems. Consider the asymmetric quorum system presented in Example 4.1. This trust structure tolerates a wider range of failure patterns than any symmetric quorum system could handle (since the Q3 property is not satisfied). In particular, this is achieved by having heterogeneous notions of fault-tolerance. For a given failure pattern, some processes might tolerate it while others might not. This contrasts with symmetric systems, where either all processes tolerate the failure scenario or none does. In this work, we investigate which tasks remain solvable in these additional scenarios. Our analysis relies on the notion of depth and its relationship to task solvability, introduced in Section 3.2. It is known that no tasks are solvable for depth zero, and that only simple tasks can be solved for depth one. In contrast, many core problems in distributed computing, such as reliable broadcast and consensus, require depth at least two. Since each failure scenario determines the depths of the correct processes, this characterization enables a simple and systematic study of task solvability under different fault patterns. Specifically, if a fault pattern tolerated by an asymmetric quorum system leaves only processes with depth zero or one, then only a very restricted class of tasks can be solved, those requiring depth one. If, however, at least one process has depth two or higher, the system enters a regime in which more complex tasks become solvable, tasks requiring depth two or more. Even 7
though a task requiring depth d > 2 can’t be solved if the maximum depth of a process is two, in all scenarios where it is solvable (i.e., there is at least one process with depth d), there will be at least a process with depth two (since a process with depth d also has depth d′ for all d′ < d). We refer to the scenario where the maximum depth of any process is one or less as the simple scenario and to the latter as the complex scenario. We study how the fault tolerance of asymmetric trust differs significantly between those two scenarios. We show that the additional fault tolerance provided by asymmetric trust lies entirely within the simple scenario. In contrast, all fault patterns under which complex tasks remain solvable can also be tolerated by an appropriate symmetric quorum system. Example 4.1. Consider a system with five processes P = {p1 , p2 , p3 , p4 , p5 } and asymmetric quorum system Q. This is a valid asymmetric quorum system as it satisfies the B 3 property. Q1 = {p1 , p2 }, {p1 , p2 , p3 , p5 } Q2 = {p2 , p3 , p4 }, {p1 , p2 , p3 , p5 } Q : Q3 = {p1 , p3 , p4 }, {p1 , p2 , p3 , p5 } Q4 = {p2 , p3 , p4 , p5 }, {p1 , p2 , p3 , p5 } Q5 = {p2 , p3 , p4 , p5 }, {p1 , p2 , p3 , p5 } The quorum system Q can tolerate more faults than any symmetric quorum system, as it does not satisfy the Q3 property. For example, failure patterns F = {p3 , p4 , p5 }, F = {p1 }, F = {p2 }, F = {p3 }, F = {p4 }, or F = {p5 } can be tolerated, something not possible for any symmetric quorum system. However, this extra expressive power lies in fault scenarios in which only tasks requiring depth 1 can be solved. When F = {p3 , p4 , p5 }, process p2 has depth 0 and process p1 has depth 1. Since the maximum depth of a process is 1, it is not possible to solve problems such as reliable broadcast or consensus. Note that all failure scenarios that allow tasks requiring depth two to be solved (F = {p4 }, F = {p5 }) could be handled with a 4-out-of-5 symmetric threshold quorum system, in fact, such symmetric quorum system would be able to guarantee solvability of problems for more failure scenarios than Q. We generalize this in Lemmas 4.1 and 4.2, where we show that, for any asymmetric quorum system, all fault patterns that allow tasks requiring depth two to be solved with asymmetric trust could also be handled with symmetric trust. More precisely, we show that for any asymmetric quorum system Q, there exists a symmetric quorum system S such that, for every failure pattern tolerated by Q in which complex problems can be solved, S can also tolerate that pattern and support the solution of the same tasks. Consequently, when attention is restricted to scenarios in which complex tasks are solvable, symmetric and asymmetric trust provide identical fault-tolerance guarantees. In Example 4.1, the system Q tolerates the failure pattern F = p3 , p4 , p5 . However, these failures cause all correct processes to have depth zero or one, and therefore tasks requiring higher depths can’t be solved. We establish this result by developing a quorum compiler that transforms any asymmetric quorum system into a symmetric quorum system. We show that, in every execution in which at least one process has depth at least two, the resulting symmetric quorum system satisfies the standard consistency and availability properties. This guarantees that it is a valid symmetric quorum system and that it can be used within symmetric algorithms to solve distributed tasks. We also show that there exist no compilers that guarantee that the symmetric quorum system generated satisfies the consistency and availability properties if the maximum depth of any process is one. Together, these results provide a tight characterization of the power and limitations of compilers with respect to depth.
4.1
Compiler
In this section we study the problem of translating trust assumptions from the asymmetric to the symmetric world. We first introduce the notion of a set of failures induced by a depth for 8
a particular asymmetric quorum system (Definition 4.1). That is, a set of failures such that if any of those occur, the system will have one or more processes with the inducing depth. Definition 4.1. Given an asymmetric quorum system Q, denote by F [d] ⊆ 2P the set of all failure patterns that allow at least one process to have depth d or more. That is, a set F ⊆ P belongs to F [d] if and only if there is a process p ∈ P such that when the parties in F are faulty, depth(p) ≥ d. Having defined F[d], we define the notion of a quorum compiler parametrized by depth. This is a program that translates asymmetric quorum systems into symmetric counterparts while keeping the same fault-tolerance guaranties if there is at least one process with a certain depth. Definition 4.2 (Depth-parametrized quorum compiler). A quorum compiler with depth d, shortened as C[d], is a program that takes as input any asymmetric quorum Q that satisfies the B 3 property and produces as output a symmetric quorum system S, such that for all failure patterns in F[d], the resulting symmetric quorum system S satisfies the following properties 1. ∀ Q1 , Q2 ∈ S, ∀F ∈ F[d] : Q1 ∩ Q2 ⊈ F 2. ∀ F ∈ F[d], ∃Q ∈ S : Q ∩ F = ∅ That is, S satisfies the quorum consistency and availability properties when considering F[d] as the fail-prone system whose faults have to be tolerated. We parametrize the compiler using depth since this is the best existing tool to characterize asymmetric trust. Note, however, that there could exist other parameterizations that allow even more expressive power at the time of characterizing processes in asymmetric trust. We now show a compiler construction that implements C[2]. Before this, the best existing construction [3] implemented C[∞]. Afterwards, we show that it is not possible to construct a compiler that implements C[1]. This shows that it is not possible to get a compiler with a lower depth parameter than the one presented here. Algorithm 1 presents the code to implement the compiler DC. Algorithm 1 Asymmetric to symmetric quorum compiler DC 1: S ← ∅ // stores the symmetric quorum system 2: for each Qi ∈ Q do 3: for each Qi ∈ Qi do 4: expand(Qi , 0, ∅) 5: return S 6: function expand(Q, j, currentquorum) 7: if j < |Q| do 8: pk ← Q[j] // process at index j in Q 9: for each Q′ ∈ Qk do 10: expand(Q, j + 1, currentquorum ∪ Q′ ) 11: else 12: S ← S ∪ currentquorum
Definition 4.3 (Compiler DC). Given any B 3 -satisfying asymmetric quorum system Q = [Q1 , . . . , Qn ], we define the compiler DC as follows. It takes as input Q and outputs a symmetric quorum system S = DC(Q). The compiler transforms an asymmetric quorum system into a symmetric one by expanding each quorum. More precisely, for every quorum Q ∈ Qi ∈ Q in the local quorum systems of 9
all processes, the compiler considers each process p ∈ Q and replaces it with one of its local quorums from Qp . It enumerates all possible combinations of such choices (i.e., the Cartesian product), takes the union of the selected sets, and collects every resulting union into the output system S. Intuitively, each original quorum is ”expanded” by substituting every member with one of its local quorums, and the symmetric quorum system consists of all sets that can be formed this way. Given a symmetric quorum S ∈ S, we denote by O(S) the original quorum that was “expanded” to produce S, i.e., the quorum Qi in Line 4 of the algorithm. From S, we can also define its associated canonical fail-prone system N = {P \ S | S ∈ S}. Lemma 4.1 shows that if Q satisfies B 3 , then S satisfies Q3 . Lemma 4.2 shows that if a process has depth at least 2, S satisfies quorum consistency and availability. Together, these results show that C produces a valid symmetric quorum system. Lemma 4.1. Let Q be an asymmetric Byzantine quorum system among processes P with asymmetric fail-prone system F and let S = DC(Q) be the symmetric Byzantine quorum system obtained with compiler DC. Let N be the canonical fail-prone system associated to S. If B 3 (F) then Q3 (N ). Proof. See Appendix A. Lemma 4.2. The compiler DC implements C[2] Proof. See Appendix A. Lemma 4.3. Consider an execution with faulty processes F , a process pi such that depth(pi ) ≥ 1 and any of its quorums Qi ∈ Qi . For any other process pj with depth(pj ) ≥ 1, ∃Kj ∈ Kj such that Kj ⊆ Qi \ F . Proof. See Appendix A. Corollary 4.1. Consider an execution with faulty processes F , and two processes pi , pj with depth at least one. For any pair of their quorums Qi ∈ Qi , Qj ∈ Qj , Qi ∩ Qj ⊈ F . This result implies that all failure patterns contemplated by F[2] are tolerated by the symmetric quorum system. However, if no process has depth two or more, the compiler does not guarantee consistency or availability. For tasks requiring depth two or more, no asymmetric protocol could provide a solution in these cases anyway. This is the reason why every failure scenario that permits solving a task requiring depth at least two can also be tolerated by the symmetric quorum system produced by the compiler.
4.2
Impossibility of compilers for depth one
In Section 4.1 a compiler from an asymmetric quorum system Q to a symmetric quorum system S with depth parameter two was presented, denoted as C[2]. It maintains the same fault-tolerance guarantees for all failure patterns that leave at least one process with depth two. In this section we show that there cannot exist a compiler that implements C[1]. This shows a tight bound on the existence of compilers parametrized by depth. Lemma 4.4 proves this result. Lemma 4.4. There exists no compiler that implements C[1]. Proof. See Appendix A. As discussed in Section 4.1, our results do not rule out every possible characterization of compilers using other concepts rather than depth. Depth is the most expressive concept for asymmetric quorum systems; nonetheless, we leave a complete characterization of compilers as future work. 10
5
Impact on the known-quorums setting
In the previous section, we showed that for any asymmetric quorum system Q, there exists a symmetric quorum system S that tolerates the same failures in scenarios where tasks requiring depth two or more are solvable. For fault scenarios tolerated by Q but not S, only tasks requiring depth one can be solved. This existential result applies to both the known and unknown quorums settings, though its practical application differs between the two. In the known quorums setting, all processes have full knowledge of Q, allowing each to locally compute S = C(Q). They can then execute any symmetric protocol A with S to solve tasks, avoiding more complex asymmetric protocols. For tasks requiring depth two or more, every execution of a symmetric protocol with S allows each correct process to obtain a correct output from the execution. Processes with depths zero and one benefit most, since an asymmetric protocol for depth two would not guarantee a solution for them. Thus, using the compiled symmetric quorum system can offer stronger guarantees than asymmetric protocols. The cost of building and using this system is discussed in Section 5.1.
5.1
Cost of using the compiler
A quorum system can in principle describe the power set of all processes and thus be exponentially large in n. This mean that in some scenarios, checking if a certain message has been received from a quorum could already be computationally expensive. Thus explicitly executing the compiler in Algorithm 1 to construct the symmetric quorum system may be impractical, as it incurs quadratic complexity in the size of the original asymmetric system. Fortunately, checking whether a set contains a quorum can be done efficiently without explicitly constructing the full system. An on-the-fly procedure can determine if a set of received messages contains a quorum produced by the compiler, incurring only an additional O(n) overhead compared to checking quorum inclusion in the original asymmetric system. We note that this linear computational overhead is unavoidable in a compiled system since the original system may rely critically on the assumptions of one particular process (e.g. the only process with a certain depth), and the compiler must work regardless of which processes has maximal depth.1 Recall that the compiler constructs symmetric quorums by expanding a single asymmetric quorum: starting from a quorum of one process, it selects, for each member, one of that member’s own quorums. A set of received messages contains a symmetric quorum if it contains this twolevel structure. Suppose a process has received messages from a set M . The check proceeds in two steps: Filter parties: For each party p ∈ P, check whether p has a quorum fully contained in M . Parties that fail this check cannot belong to any symmetric quorum contained in M . Let M ′ ⊆ M denote the parties that pass this check. Identify originating quorum: Check whether there exists a party p ∈ P with a quorum Q ∈ Qi , such that Q ⊆ M ′ . If so, M contains a quorum generated by the compiler, which resulted from expanding asymmetric Q. Each step requires checking quorum inclusion for every party. Hence, the total cost of determining whether a symmetric quorum exists is at most 2n quorum checks in the original asymmetric system. 1 If the compiler is allowed to guess a process with maximal depth, a trivial solution is to simply output the quorums of that process.
11
6
Impact in the unknown quorums setting
In the unknown quorums setting, each process pi does not know the complete asymmetric quorum system Q, only their own trust assumptions Qi . It is possible for processes to exchange trust assumptions between them; however, since we are in the Byzantine setting, processes could lie or send conflicting information about their own trust assumptions. Additionally, processes can report local quorums that cause the B 3 property to break. Combined, this makes it very difficult for processes to learn or agree on the same asymmetric quorum system Q. Consequently, using the compiler to produce a symmetric quorum system is not immediately possible. Lemmas 4.1 and 4.2 still guarantee the existence of a symmetric quorum system with the same fault tolerance for cases where tasks requiring depth two or more can be solved, however, constructing it is not straightforward. We leave as an open question whether it is possible to apply ideas like the ones presented in this work also in the unknown-quorums setting.
7
Related work
Thresholds and symmetric quorum systems are fundamental tools in distributed computing, widely used to guarantee correctness in protocols [28, 25, 6, 11]. They are also core components of many practical systems, including cloud platforms [19, 18] and cryptocurrencies [15, 9, 10]. A key limitation is that all participants must rely on the same quorum system, which limits the expression of heterogeneous trust assumptions. The asymmetric trust model, introduced by Damgård et al. [13] and further developed by Alpos et al. [1], generalizes the symmetric paradigm by allowing participants to make independent trust choices. These choices can reflect social relationships or external information unavailable to the protocol. In this model, each participant defines its own quorum system, operating under individualized trust assumptions. Amores-Sesar et al. [5] show that algorithms designed for symmetric quorum systems cannot, in general, be applied directly to the asymmetric setting, as key quorum properties may no longer hold. This motivates adapting symmetric protocols and redefining classical correctness properties for asymmetric trust. A growing body of work has focused on designing primitives and protocols specifically for the asymmetric model. Alpos et al. [1] introduce asymmetric variants of fundamental building blocks, including reliable broadcast, binary consensus, and common coin. Building on these primitives, Amores-Sesar et al. [5] develop a DAG-based consensus protocol tailored to asymmetric trust. Sheff et al. [32] propose a variant of Paxos that incorporates heterogeneous trust assumptions. Losa et al. [23] propose an alternative modeling approach that replaces fail-prone sets with strengthened quorum definitions, requiring each quorum to contain a quorum for each of its members. Li et al. [21] extend this framework by identifying quorum properties necessary or sufficient to solve fundamental asymmetric problems such as consensus. Finally, AmoresSesar et al. [3] refine these results, showing that reliable broadcast and consensus can be solved under significantly weaker assumptions than previously thought. Asymmetric consensus protocols have also been deployed in blockchain systems, most notably the XRP Ledger2 [12] and Stellar3 [26, 22]. In the XRP Ledger, each participant specifies its trust assumptions by listing nodes whose votes it considers [12, 4]. Stellar follows a similar approach, with each participant maintaining a set of trusted nodes and waiting for a sufficient majority to agree on a transaction before finalizing it [26, 23, 22]. Translating problems between computational models has a long history in distributed computing [16, 14, 24]. In the context of asymmetric trust, Senn and Cachin [31] were the first to study quorum compilers, focusing on transformations between asymmetric and symmetric trust in the crash-fault models. In the Byzantine setting, Amores-Sesar et al. [5] proposed a quorum 2 3
https://xrpl.org https://stellar.org
12
compiler that transforms asymmetric quorum systems into symmetric ones, though the resulting system guarantees correctness only under very restrictive operating conditions, namely, under the existence of processes with infinite depth.
8
Conclusion and future work
This paper investigated task solvability in failure scenarios that are uniquely tolerated by asymmetric trust, through the lens of the depth hierarchy. Our main result shows that asymmetric trust does not allow to solve tasks requiring depths at least two, such as reliable broadcast and consensus, in more failure scenarios than symmetric trust does. For any asymmetric quorum system, every failure scenario that permits solving a task requiring depth at least two can also be tolerated by a suitably constructed Byzantine symmetric quorum system. In the remaining failure scenarios, which are uniquely tolerable by asymmetric trust, it would not be possible to solve such tasks anyway, since all processes have depth at most one. We establish this by presenting a compiler that transforms asymmetric quorums into symmetric ones while preserving fault tolerance. In contrast, depth one tasks emerge as the primary beneficiaries of asymmetric trust. They are the only tasks that can be solved in failure scenarios that are uniquely supported by asymmetric quorum systems, highlighting a precise boundary in the hierarchy. Consistent broadcast, one of these tasks, has been proposed and deployed as a consensusless building block in several systems [7, 2, 8], demonstrating that, despite its simplicity, it remains a useful component. Incorporating it into asymmetric systems would enable them to fully exploit the additional fault tolerance that asymmetric quorum systems provide. Our results show that, for many tasks, equivalent symmetric trust assumptions exist; however, constructing and deploying them efficiently remains an open question. In the knownquorums setting, while the compiler is optimal in terms of depth, it introduces a linear computational overhead which may be relevant in complex systems. One could hope to eliminate this overhead using a natively asymmetric protocol, for which the problem of achieving optimal depth remains open. In the unknown-quorums setting, constructing a symmetric quorum system from an asymmetric one remains open.
Acknowledgments This work was supported by the Swiss National Science Foundation (SNSF) under grant agreement Nr. 219403 (Emerging Consensus), by the Initiative for Cryptocurrencies and Contracts (IC3), by the Cryptographic Foundations for Digital Society, CryptoDigi, DFF Research Project 2, Grant ID 10.46540/3103-00077B, and by the European Union, ERC2023-StG-101116713. Views and opinions expressed are those of the author(s) only and do not necessarily reflect those of the European Union. Neither the European Union nor the granting authority can be held responsible for them.
References [1] Orestis Alpos, Christian Cachin, Björn Tackmann, and Luca Zanolini. Asymmetric distributed trust. Distributed Comput., 37(3):247–277, 2024. [2] Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros. pod: An optimal-latency, censorship-free, and accountable generalized consensus layer. In Dariusz R. Kowalski, editor, 39th International Symposium on Distributed Computing, DISC 2025, Berlin, Germany, October 27-31, 2025, volume 356 of LIPIcs,
13
pages 4:1–4:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. URL: https: //doi.org/10.4230/LIPIcs.DISC.2025.4, doi:10.4230/LIPICS.DISC.2025.4. [3] Ignacio Amores-Sesar, Christian Cachin, Simon Holmgaard Kamp, and Juan Villacis. Weaker assumptions for asymmetric trust. In OPODIS, volume 361 of LIPIcs, pages 8:1– 8:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. [4] Ignacio Amores-Sesar, Christian Cachin, and Jovana Micic. Security analysis of ripple consensus. In OPODIS, volume 184 of LIPIcs, pages 10:1–10:16. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2020. [5] Ignacio Amores-Sesar, Christian Cachin, Juan Villacis, and Luca Zanolini. Dag-based consensus with asymmetric trust. In PODC, pages 151–161. ACM, 2025. [6] Hagit Attiya and Jennifer L. Welch. Distributed computing - fundamentals, simulations, and advanced topics (2. ed.). Wiley series on parallel and distributed computing. Wiley, 2004. [7] Mathieu Baudet, George Danezis, and Alberto Sonnino. Fastpay: High-performance byzantine fault tolerant settlement. In Sarah Meiklejohn and Abhi Shelat, editors, Proceedings of the 2nd ACM Conference on Advances in Financial Technologies, AFT 2020, New York, NY, USA, October 21-23, 2020, pages 163–177. ACM, 2020. doi:10.1145/3419614. 3423249. [8] Sam Blackshear, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris KokorisKogias, Xun Li, Mark Logan, Ashok Menon, Todd Nowacki, Alberto Sonnino, Brandon Williams, and Lu Zhang. Sui lutris: A blockchain combining broadcast and consensus. In Bo Luo, Xiaojing Liao, Jun Xu, Engin Kirda, and David Lie, editors, Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS 2024, Salt Lake City, UT, USA, October 14-18, 2024, pages 2606–2620. ACM, 2024. doi: 10.1145/3658644.3670286. [9] Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on BFT consensus. CoRR, abs/1807.04938, 2018. [10] Vitalik Buterin and Danny Ryan. Ethereum 2.0: Proof of stake and shard chains. https: //ethereum.org/en/eth2/, 2018. Accessed: 2025-08-19. [11] Christian Cachin, Rachid Guerraoui, and Luı́s E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.). Springer, 2011. [12] Brad Chase and Ethan MacBrough. Analysis of the XRP ledger consensus protocol. CoRR, abs/1802.07242, 2018. [13] Ivan Damgård, Yvo Desmedt, Matthias Fitzi, and Jesper Buus Nielsen. Secure protocols with asymmetric trust. In ASIACRYPT, volume 4833 of Lecture Notes in Computer Science, pages 357–375. Springer, 2007. [14] Giovanni Deligios and Mose Mizrahi Erbes. Closing the efficiency gap between synchronous and network-agnostic consensus. In Marc Joye and Gregor Leander, editors, Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part V, volume 14655 of Lecture Notes in Computer Science, pages 432–461. Springer, 2024. doi:10.1007/978-3-031-58740-5\_15.
14
[15] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. In SOSP, pages 51–68. ACM, 2017. [16] Oded Goldreich and Erez Petrank. The best of both worlds: Guaranteeing termination in fast randomized byzantine agreement protocols. Inf. Process. Lett., 36(1):45–49, 1990. [17] Martin Hirt and Ueli M. Maurer. Player simulation and general adversary structures in perfect multiparty computation. J. Cryptol., 13(1):31–60, 2000. [18] Patrick Hunt, Mahadev Konar, Flavio Paiva Junqueira, and Benjamin C. Reed. Zookeeper: Wait-free coordination for internet-scale systems. In USENIX ATC. USENIX Association, 2010. [19] Avinash Lakshman and Prashant Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Oper. Syst. Rev., 44(2):35–40, 2010. [20] Andrew Lewis-Pye and Tim Roughgarden. Permissionless consensus. CoRR, abs/2304.14701, 2023. URL: https://doi.org/10.48550/arXiv.2304.14701, arXiv: 2304.14701, doi:10.48550/ARXIV.2304.14701. [21] Xiao Li, Eric Chan, and Mohsen Lesani. Quorum subsumption for heterogeneous quorum systems. In DISC, volume 281 of LIPIcs, pages 28:1–28:19. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2023. [22] Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafal Malinowsky, and Jed McCaleb. Fast and secure global payments with stellar. In SOSP, pages 80–96. ACM, 2019. [23] Giuliano Losa, Eli Gafni, and David Mazières. Stellar consensus by instantiation. In DISC, volume 146 of LIPIcs, pages 27:1–27:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. [24] Julian Loss and Tal Moran. Combining asynchronous and synchronous byzantine agreement: The best of both worlds. IACR Cryptol. ePrint Arch., page 235, 2018. URL: http://eprint.iacr.org/2018/235. [25] Dahlia Malkhi and Michael K. Reiter. Byzantine quorum systems. Distributed Comput., 11(4):203–213, 1998. [26] David Mazieres. The stellar consensus protocol: A federated model for internet-level consensus. Stellar Development Foundation, 32:1–45, 2015. Available online from https: //stellar.org/learn/stellar-consensus-protocol. [27] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, October 2008. White paper. URL: https://bitcoin.org/bitcoin.pdf. [28] Moni Naor and Avishai Wool. The load, capacity, and availability of quorum systems. SIAM J. Comput., 27(2):423–447, 1998. [29] Rafael Pass and Elaine Shi. Fruitchains: A fair blockchain. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 315–324. ACM, 2017. doi:10.1145/3087801.3087809. [30] Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228–234, 1980. doi:10.1145/322186.322188. 15
[31] Michael Senn and Christian Cachin. Asymmetric failure assumptions for reliable distributed systems. In PaPoC@EuroSys, pages 8–14. ACM, 2025. [32] Isaac C. Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C. Myers. Heterogeneous paxos. In OPODIS, volume 184 of LIPIcs, pages 5:1–5:17. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2020.
16
A
Proofs
Lemma 4.1. Let Q be an asymmetric Byzantine quorum system among processes P with asymmetric fail-prone system F and let S = DC(Q) be the symmetric Byzantine quorum system obtained with compiler DC. Let N be the canonical fail-prone system associated to S. If B 3 (F) then Q3 (N ). Proof. We will proceed by contradiction. Assume that N does not satisfy the Q3 -condition. Therefore, there exist N1 , N2 , N3 ∈ N such that N1 ∪ N2 ∪ N3 = P. We will denote by S1 = P \ N1 , S2 = P \ N2 , S3 = P \ N3 the corresponding canonical quorums. Denote by also Q1 = O(S1 ), Q2 = O(S2 ), and Q3 = O(S3 ). By the asymmetric quorum consistency property, there are processes pi , pj such that pi ∈ Q1 ∩ Q2 and pj ∈ Q2 ∩ Q3 . By the definition of S, there exists a quorum Qi ∈ Qi such that Qi ⊆ S1 and there is another quorum Q′i ∈ Qi such that Q′i ⊆ S2 . Denote by Fi = P \ Qi and Fi′ = P \ Q′i the canonical asymmetric fail-prone sets associated to Qi , Q′i . Since Fi = P \ Qi , Qi ⊆ S1 , and N1 = P \ S1 , it follows that N1 ⊆ Fi . Reasoning the same logic we obtain that N2 ⊆ Fi . Therefore, N1 ∈ Fi and N2 ∈ Fi . By the definition of S, there is another quorum Qj ∈ Qj such that Qj ⊆ S2 and there is a quorum Q′j ∈ Qj such that Q′j ⊆ S3 . Denote by Fj = P \ Qj and Fj′ = P \ Q′j the canonical asymmetric fail-prone sets associated to Qj , Q′j . Since Fj = P \ Qj , Qj ⊆ S2 , and N2 = P \ S2 , it follows that N2 ⊆ Fj . Applying the same reasoning we get N3 ⊆ Fj . Therefore, N2 ∈ Fj and N3 ∈ Fj . This constitutes the contradiction since pi with fail-prone sets N1 , N2 and pj with fail-prone sets N2 , N3 violate the B 3 -condition in Q as N1 ∪ N3 ∪ (N2 ∩ N2 ) = N1 ∪ N3 ∪ N2 = P. Lemma 4.2. The compiler DC implements C[2] Proof. We want to show that the compiler DC implements C[2]. Consider a set of processes P and any B 3 -satisfying asymmetric quorum system Q and its associated canonical fail-prone system F. To prove the lemma we must show that S = DC(Q) satisfies the following properties 1. ∀Q1 , Q2 ∈ S, ∀F ∈ F[2] : Q1 ∩ Q2 ⊈ F 2. ∀F ∈ F [2], ∃Q ∈ S : Q ∩ F = ∅ We start by proving the first property. Consider any fault scenario F ∈ F[2]. Since F ∈ F[2], there is at least one process pi ∈ P such that depth(pi ) ≥ 2. Thus, there is at least one quorum Qi ∈ Qi such that all its members have depth at least one, that is, for each pi′ ∈ Qi , F ∈ Fi∗′ . Consider now any two quorums Q1 , Q2 ∈ S. We know that O(Q1 ) ∈ Qj for Qj ∈ Q for some process pj and that O(Q2 ) ∈ Qk for Qk ∈ Q for some process pk . By the quorum consistency property of asymmetric quorum systems, we know that Qi ∩ Qj ̸= ∅. Let us denote with pm any process belonging to Qi ∩ Qj . Similarly, we know that Qi ∩ Qk ̸= ∅. Let us denote with pn any process belonging to Qi ∩ Qk . Let Am ∈ Qm be the quorum of pm contained within Q1 , that is, Am ⊆ Q1 . Similarly, let Bn ∈ Qn be the quorum of pn contained within Q2 . Since pm and pn have depth 1, from Corollary 4.1 it follows that Am ∩ Bn ⊈ F . Therefore, Q1 ∩ Q2 ⊈ F . This proves the first property. To prove the second property, consider again the party pi and its quorum Qi ∈ Qi where all processes have depth at least one. For each process pj in Qi , it follows that F ∈ Fj∗ . This implies that there is a quorum Qj ∈ Qj such that F ⊆ P \ Qj . Let S ′ ∈ S be the symmetric quorum where each pj ∈ Qi is replaced by the quorum Qj ∈ Qj such that F ∩ Qj = ∅. Since S ′ is the union of such quorums, and for each quorum its intersection with F is empty, it follows that S ′ ∩ F = ∅, which proves the second property.
17
Lemma 4.3. Consider an execution with faulty processes F , a process pi such that depth(pi ) ≥ 1 and any of its quorums Qi ∈ Qi . For any other process pj with depth(pj ) ≥ 1, ∃Kj ∈ Kj such that Kj ⊆ Qi \ F . Proof. Since pi and pj both have depth at least 1, it holds F ∈ Fi∗ and F ∈ Fj∗ . This implies F ∈ Fi∗ ∩ Fj∗ . Then, the set Qi \ F intersects every quorum of pj by the quorum consistency property, and therefore contains a kernel for pj . Lemma 4.4. There exists no compiler that implements C[1]. Proof. Suppose there exists a compiler C that implements C[1], meaning that it is able to produce symmetric quorum systems S that satisfy the following properties 1. ∀ Q1 , Q2 ∈ S, ∀F ∈ F[1] : Q1 ∩ Q2 ⊈ F 2. ∀ F ∈ F[1], ∃Q ∈ S : Q ∩ F = ∅ Consider the system with three processes P = {p1 , p2 , p3 } and asymmetric quorum system Q: Q1 = {p1 , p2 } Q2 = {p2 , p3 } Q3 = {p3 , p1 } Note that this is a valid asymmetric quorum system since the canonical fail-prone system associated to it satisfies the B 3 property. We will show that there cannot exist a compiler C that produces a symmetric quorum system that satisfies the aforementioend properties. We proceed by contradiction. Suppose that there is a compiler C that produces a symmetric quorum system that satisfies both properties. If the input is Q, the compiler should produce the same output S regardless of the classification of processes as faulty or correct. First, consider the case where p3 is faulty. From the example quorum system it follows that p1 has depth one (p1 , p2 are correct) and p2 has depth zero. Since S = C(Q) should satisfy both properties, from the second one it is known that there must be a quorum Q1 ∈ S such that Q1 ⊆ {p1 , p2 }. We first show that |Q1 | > 1. Suppose that Q1 only has one element. Without loss of generality assume that it is p1 . By the first property it follows that all other quorums in S would need to contain p1 (since ∅ ∈ F[1]). However, the failure scenario F = {p1 } is also contained in F [1] (p2 has depth one), so S would still need to satisfy both properties. But this would mean that if p1 is faulty, ∀Q ∈ S, Q∩F ̸= ∅, which breaks the second property. Therefore, Q1 = {p1 , p2 }. Using the same analysis for the cases when p1 is faulty and when p2 is faulty, it follows that S should also contain quorums Q2 = {p2 , p3 } and Q3 = {p1 , p3 }. Therefore, {Q1 , Q2 , Q3 } ⊆ S. However, S cannot contain all these quorums, as this leads to breaking the properties required for the compiler. For example, Q1 ∩ Q2 = {p1 , p2 } ∩ {p2 , p3 } = {p2 }, but {p2 } ∈ F[1], so the first property would be broken. Another way of reaching this conclusion is by noting that for the asymmetric quorum system Q, F[1] does not satisfy the Q3 property, which by Lemma 2.1 implies that no quorum system exists for it. Therefore, since a compiler that implements C[1] must work for all asymmetric quorum systems and for all failure scenarios contemplated by F[1], we have shown that such a compiler cannot exist. Therefore, C[2] is the compiler with the lowest depth parameter that can be implemented.
18