Early-Stabilizing Counting
arXiv:2605.18171v1 [cs.DC] 18 May 2026
CHRISTOPH LENZEN, Aalto University, Finland and Reykjavik University, Iceland JULIAN LOSS, Ruhr University Bochum, Germany Synchronous Counting is the task of reaching agreement on a common round counter in a synchronous system of 𝑛 nodes with up to 𝑡 Byzantine faults in a self-stabilizing manner. That is, after transient faults may have arbitrarily corrupted the system state and ceased, the at least 𝑛 − 𝑡 non-faulty nodes need to (re-)establish that (i) their local outputs are identical and (ii) increase by 1 modulo 𝐶 in each round. An overhead-free reduction from consensus shows that all known lower bounds and impossibilities for consensus carry over to the counting problem. In the other direction, prior work has established that a consensus algorithm A can be turned into a counting algorithm at small overhead relative to the running time and bit complexity of A, without losing resilience. Taking inspiration from early-stopping consensus protocols, in this work we introduce the concept of early stabilization. That is, if there are 0 ≤ 𝑓 ≤ 𝑡 (persistent) faults in an execution, the algorithm should stabilize in a number of rounds that depends on 𝑓 only. Likewise, we seek to achieve an amortized bit complexity that is adaptive in the number of actual faults 𝑓 . By developing a number of modular building blocks suitable to these goals, we develop a 𝐶-counting algorithm that stabilizes within asymptotically optimal 𝑂 (𝑓 + 1) rounds, has message size 𝑂 (log2 𝑛 + log 𝐶), and has amortized bit complexity 𝑂 (𝑛(𝑓 log 𝐶 + log2 𝑛)).
1
Introduction & Related Work
Synchronous Counting, a.k.a. Byzantine digital clock synchronization, asks the nodes of a synchronous system to agree on a common round counter despite arbitrary initial states and interference from Byzantine faulty parties. This task naturally arises once its big brother, Byzantine faulttolerant pulse synchronization [11, 18], has been solved: this problem establishes synchronized, self-stabilizing regular pulses in a system where nodes are equipped with local clocks of bounded relative drift and exchange messages whose communication delay varies within known bounds. These pulses can serve as a clock signal establishing the synchronous abstraction despite both bounded Byzantine and and unbounded transient faults, but the resulting rounds are “anonymous.” This gets in the way of basic operations like initiating a subroutine that should be executed regularly, but not every round, or responding coherently to external signals that are not necessarily observed by all nodes in the same round. The latter can be achieved by solving the closely related firing squad problem, cf. [17]. Thus, at first glance, counting is a fundamental challenge with practical utility. However, the latter demands a more nuanced perspective. While applying pulse synchronization naively results in unlabeled rounds, one can use them as a “heartbeat” to stabilize a faster, more accurate pulse synchronization algorithm that would not stabilize on its own, but labels pulses modulo 𝐶 [15]. This comes at the expense of slowing down the heartbeat by a factor of Θ(𝐶), which negatively impacts the stabilization time of the overall protocol stack. Ben-Or et al. [3] achieve a much smaller constant expected time overhead, by leveraging a self-stabilizing stream of weak shared coins. However, this comes at the expense of large communication overhead and additional assumptions.1 Alternatively, one can build large clocks from smaller ones [16], turning the multiplicative overhead in stabilization time of [15] into an additive one. This work gives a deterministic algorithm that runs in 𝑂 (𝑡) rounds and tolerates 𝑡 < 𝑛/3 Byzantine faults, alongside a randomized solution that 1 The classic protocol by Feldman and Micali would require Ω (𝑛 3𝜅 ) bits per heartbeat, where 𝜅 is the security parameter,
and is secure against a static, computationally bounded adversary. One cannot use more efficient protocols that rely on a trusted setup, as transient faults could reveal any pre-shared secret information. Authors’ Contact Information: Christoph Lenzen, Aalto University, Helsinki, Finland and Reykjavik University, Reykjavik, Iceland, [email protected]; Julian Loss, Ruhr University Bochum, Bochum, Germany, [email protected].
2
Christoph Lenzen and Julian Loss
achieves stabilization within 𝑂 (𝑡 + log 𝐶) rounds with probability 1 − 2−𝑡 +log 𝐶 . These bounds are optimal up to small factors in the worst case [5, 13, 20] due to a folklore reduction from consensus to counting. A remaining niche case is when the goal is to stabilize within 𝑆 ∈ log𝑂 (1) 𝑛 rounds. 𝑂 (1) Here, combining [17] and [18] achieves this property with probability 1 − 2− log 𝑛 , at the expense of higher communication complexity (depending on the consensus algorithm plugged into their framework). This can be viewed a generalization of the aforementioned earlier work by Ben-Or et al. [3] that also solves the problem of generating the heartbeats, without needing to rely on a shared coin primitive. So, should we cast aside the counting problem or at least reduce it to the status of a theoretical curiosity? We argue that this would be premature, as the above characterization limits its view to assuming a worst-case number of faults. The round lower bound for consensus breaks down when considering executions with 𝑓 ≪ 𝑡 faults [9], or more precisely, requires a more fine-grained argument that yields a round complexity of min{𝑓 + 2, 𝑡 + 1} [10]. Regarding bit complexity, current solutions all send Ω(𝑛𝑡) bits per round, factor 𝑡 beyond what the strongest known lower bound for consensus implies for counting [1, 8]. Accordingly, in this work we explore the question how much can be gained by optimizing stabilization time and bit complexity as function of 𝑓 rather than 𝑡. 1.1
Our Contributions
To the best of our knowledge, this work is the first to carry over the concept of early-stopping consensus algorithms, which terminate within 𝑂 (𝑓 +1) rounds, to the realm of self-stabilization. We coin algorithms in which the stabilization time depends only on 𝑓 , i.e., 𝑆 = 𝑆 (𝑓 ), early-stabilizing. Likewise, we are unaware of prior attempts to reduce the communication cost of fault-tolerant self-stabilizing algorithms in executions with few faults. On a high level, we perceive three key benefits in doing so. (1) Reducing communication complexity simply saves resources. While it is true that larger bandwidth still needs to be available if there is a large number of faults, these might not simultaneously affect all parts of the system or network. Hence, if communication resources are shared with other subroutines or subsystems, it can even be possible that overall bandwidth requirements are reduced for achieving the same level of resilience. (2) Reduced stabilization time can clearly improve system availability. However, in the context of self-stabilization, we emphasize a compounding impact that goes way beyond shorter recovery time after a burst of transient faults overwhelms the system. Quicker recovery affects also how quickly nodes undergoing transient faults reattain a state consistent with the system when the fault threshold 𝑡 is not reached. This entails that they contribute again to the quorum of 𝑛 − 𝑡 synchronized nodes required to count despite Byzantine faults. For example, if 𝑡 = ⌊(𝑛 − 1)/3⌋ and in each round each node suffers a transient fault with independent probability 9/𝑛 (and there are no other faults), straightforward calculations and concentration bounds show the following. (i) Within 𝑡 rounds, with probability 1−2−Ω (𝑛) , more than 𝑡 distinct nodes suffer a transient fault. Hence, a system in which 𝑡 +1 or more rounds are required for individual nodes to recover from transients would be virtually guaranteed to fail globally within 𝑡 rounds.2 (ii) Within 𝑡/3 rounds, the probability that more than 𝑡 nodes fail or that during each subinterval of 𝑆 (0) ∈ 𝑂 (1) rounds some transient fault occurs is 2−Ω (𝑛) . Thus, an algorithm that stabilizes in 𝑆 (0) rounds when there are no faults is guaranteed to maintain count for 2Ω (𝑛) rounds with probability 1 − 2−Ω (𝑛) . 2 For this informal line of reasoning, we assume that a transient fault will invalidate a node’s state and it will take the full
stabilization time to recover a consistent state.
Early-Stabilizing Counting
3
Put simply, early stabilization fundamentally improves the ability of the system to contain transient faults. (3) In [18], the authors mention that their work on pulse synchronization builds on earlier results on counting, where key techniques were developed in the “sandbox” provided by the more structured synchronous model. We hope the techniques we develop here for counting can be utilized in a similar way. Concretely, we craft a set of modular tools that ultimately achieve the following main result; we fix optimal 𝑡 := ⌊(𝑛 − 1)/3⌋ from hereon. Theorem 1.1. There is a 𝐶-counting algorithm with stabilization time 𝑂 (𝑓 + 1), message size 𝑂 (log2 𝑛 + log 𝐶), and bit complexity of 𝑂 (𝑛(𝑓 log 𝐶 + log2 𝑛)) amortized over 𝑛 rounds. Compared to the state of the art [16, 17], this reduces the stabilization time from being larger than 𝑡 to asymptotically optimal 𝑂 (𝑓 + 1) and the bit complexity from Ω(𝑛 2 ) to (amortized) 𝑂˜ (𝑛(𝑓 + 1)) per round. Paper Organization In Section 2, we discuss the system model, formalize the counting problem, and introduce two tasks that are highly useful in modularizing our solutions. Next, in Section 3 we provide an overview of the key challenges in obtaining our results and sketch the ideas underlying our algorithms and proofs. To prepare for the technical exposition, in Section 4 we introduce a number of conventions we use in pseudocode to hide important, but distracting book-keeping operations and other details.3 Section 5 discusses how to achieve stabilization time 𝑂 (𝑓 + log 𝑛), focusing on the core idea in obtaining a stabilization time dominated by 𝑓 instead of 𝑡. We follow up by reducing amortized bit complexity to 𝑂˜ (𝑛(𝑓 + 1)) in Section 6. To arrive at our main result, Section 7 introduces additional building blocks and modifies the recursion template to remove the additive 𝑂 (log 𝑛) overhead from the stabilization time. We conclude the paper with a discussion of open questions in Section 8. 2
Model and Preliminaries
Communication Model. We consider a fully connected synchronous system with node set 𝑉 := [𝑛], where we use the shorthand [𝑘] := {0, . . . , 𝑘 − 1}. That is, algorithms proceed in rounds, in which nodes send and receive messages and perform computations in lock-step. When a node 𝑣 sends a message 𝑚 to another node 𝑤 at the onset of a round 𝑟 ∈ N, 𝑤 receives and processes 𝑚 by the end of round 𝑟 , knowing that 𝑚 was sent by 𝑣. The round complexity of a (non-stabilizing) protocol is the maximum number of rounds until all nodes have decided on their output and terminated, i.e., cease to send messages. Fault Model. In this work, we seek so-called self-stabilizing solutions, i.e., the system recovers correct operation after a period of unbounded transient faults. We assume that by the start of the first round (that we analyze), the most recent such period is over. In addition, we require that the system can sustain any number of Byzantine faulty nodes 𝑓 ≤ 𝑡 := ⌊(𝑛 − 1)/3⌋, where recovery should succeed despite these ongoing faults. Accordingly, the non-Byzantine nodes, which we refer to as correct, may initially have an arbitrary state, but the model assumptions on the communication network and the number of correct nodes hold again at the beginning of round 1.4 The goal is for the system as a whole to recover correct operation again within a bounded number of rounds 3 Readers familiar with self-stabilization should not be surprised by any of them, and a conceptual understanding does not
require examining them closely. However, they imbue the pseudocode with a sufficiently rigorous meaning to enable proofs. 4 In particular, the code of the algorithm must be protected against alterations by transient faults, e.g. by being stored in
more resilient non-volatile memory.
4
Christoph Lenzen and Julian Loss
𝑆. This bound is referred to as stabilization time. Note that self-stabilizing algorithms can never terminate; the stabilization time is their closest equivalent to round complexity [2]. We consider deterministic algorithms, i.e., the system must stabilize for any initial states of correct nodes and behavior of the faulty nodes. This is equivalent to assuming a powerful adversary that controls initial states and has perfect knowledge of the system, as the initial states and messages sent by faulty nodes fully determine an execution. In contrast, the algorithm is not aware of 𝑓 , and must achieve its guarantees based on the knowledge that 𝑓 ≤ 𝑡 only. This is crucial, as in this work we are interested in a stabilization time that depends on 𝑓 , not 𝑡 or 𝑛: we set out to achieve 𝑆 ∈ 𝑂 (𝑓 + 1). In analogy to the concept of early-stopping algorithms [9], we refer to this as early stabilization. As a secondary optimization criterion, we seek to minimize the amortized bit complexity of our algorithms. That is, if honest parties send a total of 𝐵(𝑟 ) bits in round 𝑟 , there should be a value 𝑅 Í such that ( 𝑟𝑅=1 𝐵(𝑟 ))/𝑅 ≤ 𝐵. In this case, the algorithm has bit complexity of 𝐵 amortized over 𝑅 rounds. We remark that it is common to ignore any communication by faulty nodes altogether, as they could send anything. However, our algorithms use short messages of polylogarithmic length, so that correct nodes can safely ignore longer messages without processing them, i.e., no backdoor through which an attacker could overtax correct nodes’ computational capacity is introduced. Finally, our self-stabilizing algorithms will list the variables that are maintained between rounds, where we use subscript 𝑣 to indicate the node. Note that subroutines may come with their own variables, but we will use their outputs only. For analysis purposes, we will refer to the state of a variable 𝑋 𝑣 of node 𝑣 at the end of round 𝑟 ∈ N by 𝑋 𝑣,𝑟 , where 𝑋 𝑣,0 refers to the (arbitrary) initial state of 𝑋 𝑣 . We do the same for output variables of self-stabilizing subroutines. Definitions The core task we consider in this work is digital clock synchronization or synchronous counting. Definition 2.1 (𝐶-Counting). Suppose that each node maintains 𝐶 𝑣 ∈ [𝐶], where 2 ≤ 𝐶 ∈ N. We say that these variables 𝐶-count iff they satisfy for all correct nodes 𝑣 and 𝑤 and 𝑟 ∈ N that • Agreement: 𝐶 𝑣,𝑟 = 𝐶 𝑤,𝑟 . • Validity: 𝐶 𝑣,𝑟 +1 = 𝐶 𝑣,𝑟 + 1 mod 𝐶. We say that the variables 𝐶 𝑣 𝐶-count from round 𝑟 ∈ N iff the above conditions hold in rounds 𝑟′ ≥ 𝑟. We formalize a task that is a core step in the construction used in [17], which we will need to implement in a different way. Intuitively, filtering distributes a 𝐶-counter that is (recursively) generated by a subset 𝑇 of the nodes to all, while limiting the inconsistency in views it the subset contains too many faulty nodes to correctly generate and distribute its shared count. More concretely, the requirement is that over any 𝑋 consecutive rounds, there is only a single count value that increases by one modulo 𝐶 in each round that may be output by correct nodes; the only other feasible output is ⊥, a special symbol indicating (possibly transient) faults. Definition 2.2 ((𝐶, 𝑋,𝑇 )-Clock Filtering). Suppose that 𝑣 ∈ 𝑉 maintains a variable 𝐹 𝑣 ∈ [𝐶] ∪ {⊥}, where 2 ≤ 𝐶 ∈ N. Moreover, there is a designated clock set 𝑇 ⊂ 𝑉 that maintains variables 𝐶 𝑣 ∈ [𝐶]. The variables 𝐹 𝑣 (𝐶, 𝑋,𝑇 )-filter 𝐶 𝑣 from round 𝑟 ∈ N iff the following properties are true: • Validity: If fewer than |𝑇 |/2 nodes in 𝑇 are faulty and the variables 𝐶 𝑣 𝐶-count, then the variables 𝐹 𝑣 𝐶-count from round 𝑟 . • 𝑋 -round Crusader Agreement: If for 𝑟 ′ ≥ 𝑟 and correct 𝑣 it holds that 𝐹 𝑣,𝑟 ′ = 𝑐 mod 𝐶, then for all correct 𝑤 and rounds 𝑟ˆ ∈ {𝑟 ′, . . . 𝑟 ′ + 𝑋 }, it holds that 𝐹 𝑤,𝑟ˆ ∈ {𝐹 𝑣,𝑟ˆ + 𝑟ˆ − 𝑟 ′ mod 𝐶, ⊥}.
Early-Stabilizing Counting
5
For the sake of notational convenience, we adopt the following conventions with respect to the above definitions. First, if 𝐶, 𝑋 , or 𝑇 are clear from context, we may omit them. Second, when we say that an algorithm solves one of these problems with stabilization time 𝑆, we mean that it maintains variables that count or filter from round 𝑆, respectively. Lemma 2.3 (implicit in [17, 19]). (𝐶, 𝑋,𝑇 )-Clock Filtering can be solved with stabilization time 𝑆 = 𝑋 + 2, where each node sends an 𝑂 (log |𝐶 |)-sized message to each other node in each round. A well-known building block of consensus algorithms is graded agreement, which will come in handy as a subroutine for us as well. Definition 2.4 (Graded Agreement). The Graded Agreement problem is specified as follows. Each node 𝑣 has input 𝑥 𝑣 ∈ V and computes an output (𝑦 𝑣 , 𝑔𝑣 ) ∈ V ×{0, 1} with the following guarantees: • Validity: If there is 𝑥 ∈ V so that 𝑥 𝑣 = 𝑥 for all correct 𝑣, then (𝑦 𝑣 , 𝑔𝑣 ) = (𝑥, 1) for all correct 𝑣. • Graded Agreement: If 𝑔𝑤 = 1 for some correct 𝑤, then 𝑦 𝑣 = 𝑦 𝑤 for all correct 𝑣. Lemma 2.5 (implicit in [4], see also [12]). Graded agreement can be solved in 2 rounds, with each node sending an 𝑂 (log |V |)-sized message to each other node in each round. Finally, we will make use of variants of the central building block of the Phase King algorithm from [4], which can be generalized to solve the following weaker form of multi-valued consensus. Definition 2.6 (King Consensus). In the King Consensus problem, each node 𝑣 has input (𝑥 𝑣 , ℓ𝑣 ) ∈ V × (𝑉 ∪¤ {⊥}) and computes output 𝑦 𝑣 ∈ V ∪¤ {⊥} with the following guarantees: • Validity: If there is 𝑥 ∈ V so that 𝑥 𝑣 = 𝑥 for all correct 𝑣, then 𝑦 𝑣 ∈ {𝑥, ⊥} for all correct 𝑣. • Default: If ℓ𝑣 = ⊥ for all correct 𝑣, then 𝑦 𝑣 = ⊥ for all correct 𝑣. • King Agreement: If there is correct ℓ ∈ 𝑉 so that ℓ𝑣 = ℓ for all correct 𝑣, then 𝑦 𝑣 = 𝑦ℓ ≠ ⊥ for all correct 𝑣. King consensus relaxes classic (multi-valued) consensus in two ways. If all nodes’ inputs agree on the same correct leader ℓ, intuitively it behaves like consensus: all outputs agree, and if 𝑥 𝑣 = 𝑥 for all nodes 𝑣, then this output is going to be 𝑥. However, we relax the validity condition in that if 𝑥 𝑣 = 𝑥 for all nodes 𝑣, then it is sufficient to output 𝑥 or ⊥. This provides leeway to save on communication when nodes think that there is no need to execute consensus at all, represented by ℓ𝑣 = ⊥. The second relaxation is that agreement is only guaranteed if all nodes’ inputs agree on some correct leader ℓ = ℓ𝑣 , allowing for an 𝑂 (1)-round solution that still meets the requirements if the nodes do not agree on the filtered clock values. Lemma 2.7 (implicit in [4]). King Consensus can be solved in 3 rounds, where each node sends an 𝑂 (log |V |)-sized message to each other node in each round. For the sake of completeness, explicit proofs of Lemmas 2.3, 2.5 and 2.7 are provided in Section A. The reader is invited to use them as a warm-up before the more involved procedures, but advised to do so after familiarizing themselves with the conventions stated in Section 4. 3
Technical Overview
In this section, we present the high-level ideas underlying our results. The focus is on the main obstacles and solutions. We follow the same order as in the subsequent sections, so this outline sketches the progression of the technical exposition in the remainder of the paper.
6
Christoph Lenzen and Julian Loss
The big picture. Essentially, solving counting boils down to solving consensus on the current values of the output counters or clocks: if they all agree, they should not be changed except for being incremented deterministically by one modulo 𝐶 each round; otherwise, any agreed-on value is fine. This corresponds to the validity and agreement properties of consensus, but runs into the issue that there is no (guaranteed) agreement as to when to run consensus. Comparatively simple solutions can be constructed by initializing a new instance to consensus every round. However, this is inherently inefficient in terms of communication, as it incurs the communication cost of a complete run of a consensus protocol per round. Other approaches rely on randomization to get “lucky” and achieve sufficient coordination, as e.g. done in [16]. However, any such approach has the structural properties subjecting it to the same trade-off between the probability of stabilization and the time to achieve it as the one between round complexity and probability of success for consensus [5]. The third type of method that has been used in the literature is to partition the node set into 𝑉0 and 𝑉1 , solve the task recursively on each of these sets, and then use the obtained counters to coordinate when consensus instances are initialized, cf. [17]. Using a balanced partition limits the recursion depth, number of instances each node participates in, and incurred overheads to 𝑂 (log 𝑛). We follow this strategy as the only one being compatible with our aims. While we have to swap out every component used in [17] to achieve our main result, it is instructive to start from their solution and evolve it step by step. Conveniently, it is trivial to solve counting when 𝑛 = 1, so the challenge is to (efficiently) solve counting on 𝑛 = 2𝑘 nodes given a working algorithm for 𝑛/2 = 2𝑘 −1 nodes. If in neither of the two sets 𝑉𝑏 a third of the nodes would be faulty, both sets would stabilize to produce counting outputs. The nodes of 𝑉𝑏 would send their current output value to all nodes, which would adopt the majority value as (perceived) “clock” 𝐶𝑏 for each 𝑏. We could use these clocks to initialize a consensus instance that terminates after 𝑅 rounds every 2𝑅 + 1 rounds, where the time to run the instance as well as the input given to it are given by the value taken by 𝐶𝑏 . We could then set the current output clock value to the output of any terminating instance plus 𝑅 mod 𝐶; otherwise, the output is simply incremented by 1 mod 𝐶. While the clocks and hence the instances might be arbitrarily aligned relative to each other, one of them is going to terminate while no “companion” instance controlled by the other clock is running. From then on, all clock values agree, so that future consensus instances do not affect the count, as they always end up outputting the already agreed-on input, which is then incremented by exactly 𝑅 mod 𝐶. The obstacle this strawman approach runs into is that there is no guarantee that 𝐶𝑏 counts correctly for both 𝑏 ∈ {0, 1}, or even that all correct nodes perceive the same majority value sent by nodes in 𝑉𝑏 . Abstractly speaking, we have two supernodes 𝑉0 and 𝑉1 each supplying a clock, but one of them may be Byzantine, sending arbitrary values. In essence, the authors of [17] address this by preventing equivocation via applying crusader broadcast (a.k.a. crusader agreement, see [7]). This means to ensure that there is a unique (clock) value 𝑐 ∈ [𝐶] such that each correct party either accepts 𝑐 as the value sent by 𝑉𝑏 or outputs ⊥ (indicating that 𝑉𝑏 is Byzantine or has not stabilized yet). However, “equivocation” here needs to be interpreted in a broader sense: if what 𝑉𝑏 sends is not counting modulo 𝐶, this is also showing that something is still amiss, and recipients will output ⊥ whenever the count was off within the last 𝑋 rounds. This is captured by the 𝑋 -round crusader agreement property of the clock filtering task. This does not yet fully overcome the above obstacle, as now some correct nodes may participate in a consensus instance triggered by 𝐶𝑏 and others do not. While it is possible to require that any already established agreement is not broken this way, the “bad” instance controlled by 𝐶𝑏 might be initialized before one controlled by 𝐶 1−𝑏 terminates. Hence, some nodes might change
Early-Stabilizing Counting
7
their output clocks as a result, breaking the agreement that has just been reached with the help of the instance controlled by 𝐶 1−𝑏 . To address this, the final tweak is to have the two clocks 𝐶𝑏 initialize instances at slightly different rates, e.g. every 2𝑅 and 3𝑅 rounds, respectively. Then, the above scenario implies that the next instance controlled by 𝐶 1−𝑏 runs without the same kind of interference and achieves stabilization of the output clock values. In summary, the strategy from [17] works as follows. ¤ 1. (1) Partition [𝑛] = 𝑉0 ∪𝑉 (2) Recursively let 𝑉𝑏 count modulo 𝐶 ∈ Θ(𝑛). (3) Use these outputs as inputs to (𝐶, Θ(𝑛), 𝑉𝑏 )-filtering. (4) Use the outputs of filtering to initialize consensus instances (where even if some nodes do not participate, validity holds). (5) Use any outputs of such a consensus instance to adjust the output clock; otherwise increment by one modulo 𝐶. We stress that naively replacing the consensus routine with an early-stopping one is insufficient for our purposes: we do not know at which frequency to initialize fresh instances to (i) achieve stabilization time 𝑂 (𝑓 + 1) yet (ii) avoid that instances remain well-separated. Reducing stabilization time. In light of the above, to make the stabilization time of a scheme like this 𝑂 (𝑓 + 1), we need to use (i) (𝐶, 𝑂 (1), 𝑉𝑏 )-filtering and (ii) a consensus subroutine that runs for 𝑂 (1) rounds only. Alas, achieving consensus deterministically takes at least 𝑡 + 1 rounds, so we need to relax the task somehow. Hence, the first crucial adaptation is to replace consensus by king consensus with varying “kings” or leaders ℓ, where 𝐹𝑏 tells us for each instance which leader to use. Note that king consensus relaxes the agreement property of consensus to hold only when the leader is correct. Fortunately, we only need the (king) agreement property once, to establish agreement on the count; afterwards, validity ensures that the output clocks are never modified again by a call to king consensus and hence count correctly, regardless of whether future leaders are correct. Each call to king consensus requires only 𝑂 (1) rounds, achieving (ii). At the same time, the output clocks stabilize at the latest when a correct leader is reached, i.e., within 𝑂 (𝑓 + 1) rounds—counting from the round in which the clock filtering subroutine stabilized. As already indicated, to achieve fast stabilization for clock filtering, we need to choose 𝑋 = 𝑂 (1), i.e., “forgive” an incorrect count within 𝑂 (1) rounds. This allows the adversary to make the value of 𝐹𝑏 “jump” throughout the course of the stabilization process if 𝑉𝑏 contains at least |𝑉𝑏 |/3 faulty nodes. To address this, we choose 𝑋 as a large enough constant such that the additional “collisions” that the adversary can induce between instances controlled by 𝐹𝑏 and 𝐹𝑏 −1 are limited to a small fraction, say 1/4, of the instances. While this may prevent some correct leaders from enforcing stabilization, among 2𝑓 instances there will be at least 𝑓 correct leaders, so that at least 2𝑓 − 𝑓 − 2𝑓 /4 > 0 succeed in stabilizing the output clock values. Note that this recursion scheme succeeds based on the first clock 𝐶𝑏 that stabilizes. Accordingly, we can determine a stabilization time bound based on the recurrence 𝑆 (𝑓 , 𝑛) ≤ 𝑂 (𝑓 ) + Í ⌈log 𝑛⌉ 𝑆 (⌊𝑓 /2⌋, ⌈𝑛/2⌉), leading to 𝑆 (𝑓 , 𝑛) ≤ 𝑂 𝑖=0 max{𝑓 /2𝑖 , 1} = 𝑂 (𝑓 + log 𝑛). One could remove the additive 𝑂 (log 𝑛) by alternating between partitioning evenly and splitting off a single node in the recursion, as then the summation would end once 𝑓 /2𝑖 < 1. We postpone this, as such an imbalanced split poses its own challenges when also trying to control bit complexity. Reducing amortized bit complexity. In order to achieve an amortized bit complexity of 𝑂˜ (𝑛(𝑓 + 1)) per round in our framework, we need to reduce the bit complexities of both the filtering procedure and king consensus. The first observation is that, so long as we have |𝑉0 | ≈ |𝑉1 | ≈ 𝑛/2, it is sufficient to do so only when 𝑉𝑏 contains fewer than |𝑉𝑏 |/3 faults for each 𝑏 ∈ {0, 1}, as otherwise
8
Christoph Lenzen and Julian Loss
𝑂˜ (𝑛(𝑓 + 1)) = 𝑂˜ (𝑛 2 ). Similarly, we do not need to worry about the communication cost during the stabilization phase, as the construction uses small messages. During 𝑂˜ (𝑓 + 1) rounds, correct nodes send 𝑂˜ (𝑛 2 (𝑓 + 1)) bits, contributing 𝑂˜ (𝑛(𝑓 + 1)) to the average over 𝑛 rounds, which is our target. This is excellent news, as it allows us to work with the assumption that the recursively constructed counters 𝐶𝑏 both already count and all correct nodes agree on their values. Thus, king consensus instances are initialized with all correct nodes in agreement on when they start and which party is the leader. In particular, there are only 𝑂 (𝑓 ) instances with faulty leaders within 𝑛 rounds, i.e., such instances also contribute 𝑂˜ ((𝑓 + 1)𝑛) bits amortized over 𝑛 rounds. Accordingly, we only need to control the communication cost of king consensus instances with agreed-on correct leaders and those without a leader.5 To do so, let us revisit the implementation of king consensus derived from the work introducing the Phase King algorithm [4] for the special case that all nodes agree on a leader ℓ, i.e., ℓ𝑣 = ℓ ≠ ⊥ for all 𝑣 ∈ [𝑛]. (1) Perform graded agreement on the input values 𝑥 𝑣 , resulting in outputs (𝑦 𝑣 , 𝑔𝑣 ). (2) The leader ℓ sends 𝑦ℓ to all nodes. (3) If 𝑔𝑣 = 1, 𝑣 outputs 𝑦 𝑣 . Otherwise, 𝑣 outputs 𝑦ℓ . The reader can readily verify that the guarantees of graded agreement ensure the validity and king agreement properties of king consensus.6 The leader’s transmission is uncritical from the perspective of communication cost, but graded agreement is costly, requiring Ω(𝑛 2 ) bits. To reduce the bit complexity of king consensus in this special case, we first have the king determine whether there is actual need to establish agreement, by having each node send their input to the king. If the system has stabilized, the king will receive the same input from 𝑛 − 𝑡 nodes and conclude that an expensive graded consensus is not necessary. However, the king might reach this conclusion also prior to stabilization, with up to 𝑡 correct nodes having a differing minority input value. To these nodes, the king points out that their input value differs from the majority. While the king cannot be trusted blindly, this is justification for these nodes to ask all others for their input and for them to respond: we already pointed out that we can bear a cost of 𝑂˜ (𝑛 2 ) bits if the king is faulty, and faulty nodes querying correct nodes for their input can cause no more than 𝑂˜ (𝑛𝑓 ) bits of communication. When a querying node receives at least 𝑛 − 2𝑡 ≥ 𝑡 + 1 values different from its own, it can safely adopt this value, as this is proof that its own input is not shared by all correct nodes. Thus, if the king concludes that no graded consensus is necessary, all correct nodes will adopt the majority value. On the other hand, if the king receives fewer than 𝑛 − 𝑡 times the same value, this is proof that stabilization has not yet occured. In this case it triggers graded agreement. Note that this step empowers a faulty king to invoke graded agreement with only a subset of the correct nodes taking part. We resolve this issue by defining a weaker version of graded agreement. Here, formally all nodes take part, but the graded agreement property only holds if all correct nodes have an additional input bit 𝑠 𝑣 equal to 1. A correct king uses the latter to create the behavior of a “regular” graded agreement when needed; the validity property remains unchanged, preventing a faulty king from disrupting existing agreement. This relaxation allows an implementation in which node 𝑣 stays silent, i.e., sends no messages, if 𝑠 𝑣 = 0, achieving the desired reduction in communication cost if all correct nodes share the same input to the king consensus instance. 5 As validity must hold even if nodes do not agree on who the leader is or even whether an instance is running, we formalize
this as an instance being initiated in every round, but nodes using input ⊥ to indicate that they have no leader for this instance. This permits correct nodes to “help” in achieving the properties if necessary even when they believe that no instance should be started. 6 Outputs of ⊥ and the default property handle the case that some or all nodes have input ℓ = ⊥, which we ruled out for 𝑣 the special case we consider here.
Early-Stabilizing Counting
9
To achieve filtering at amortized cost of 𝑂˜ (𝑛(𝑓 + 1)) bits, recall that we may assume that 𝑓 < |𝑉𝑏 |/3 and that the counting instance on 𝑉𝑏 has already stabilized. Hence, all but 𝑓 nodes in |𝑉𝑏 | are correct and agree on 𝐶𝑏 . Node 𝑣 maintains a “guess” of the current value of 𝐶𝑏 and memorizes what it believes this value to be at all other nodes. If the guess has been counting for 𝑋 rounds and no inconsistency was proven, it will output it, otherwise it will output ⊥. The algorithm now carefully implements several checks and queries to other nodes’ current guesses or 𝐶𝑏 values (for those in 𝑉𝑏 ) to ensure that (i) if the guess of 𝑣 is incorrect, it will correct it within 𝑂 (𝑓 + 1) rounds and (ii) after stabilization, only 𝑂˜ (𝑛(𝑓 + 1)) bits are sent on average. The principal ideas to achieve this are the following. (1) Node 𝑣 queries nodes 𝑤 ∈ 𝑉𝑏 for the 𝐶𝑏 value on a round-robin basis, one per round (𝑂˜ (𝑛) bits). If 𝑤 responds with a value different from 𝑣’s current guess, 𝑣 queries all nodes, causing an amortized cost of 𝑂˜ (𝑛𝑓 ) bits. (2) If 𝑣 believes that a majority of nodes in 𝑉𝑏 has a different value than its current guess, it adjusts its guess, sends its new guess to all nodes, and queries all nodes (for verification purposes). This happens at most twice after stabilization of 𝐶𝑏 , as after a query to all nodes 𝑣 updated all stale information. Hence, the amortized cost is 𝑂˜ (𝑛) bits. Together with the first rule, this guarantees that all nodes adopt the correct guess within 𝑓 + 𝑂 (1) rounds. (3) If a node has a guess that is different from the locally memorized guess of another node, it queries that node and updates its memory based on the response. Once all correct nodes adopted the correct guess and communicated about this, this costs only 𝑂˜ (𝑛𝑓 ) bits per round, since there are no queries between correct nodes anymore. This last rule enforces that correct nodes with different guesses notice the discrepancy. If a node believes that more than 𝑛/3, i.e., more than 𝑡, guesses deviate from its own, it can conclude that not all correct nodes agree on 𝐶𝑏 and will output ⊥ at least for the next 𝑋 rounds. This guarantees that there is only one non-⊥ value output by correct nodes within 𝑋 rounds, i.e., the 𝑋 -round crusader agreement property is satisfied. On the other hand, if 𝑉𝑏 contains fewer than |𝑉𝑏 |/3 faulty parties, all correct parties adopt the majority value in 𝑉𝑏 and will synchronize their views of each other’s guesses. Afterwards, the will not perceive any inconsistencies and start outputting the majority value within an additional 𝑋 ∈ 𝑂 (1) rounds, showing the validity property of clock filtering. Achieving asymptotically optimal stabilization time. As mentioned earlier, removing the additive 𝑂 (log 𝑛) from the stabilization time is challenging when seeking to simultaneously keep the amortized bit complexity small. Our approach is to use a recursion template where one branch has only a single node ℓ, which can easily generate and distribute a count (if correct), while the other branch generates its clock 𝐶 by recursing on the entire node set. By alternating between the two templates we ensure stabilization in 𝑂 (1) rounds once the current node set contains no faults, yet cut the number of faults in the branch with fewest faults in half with every other level of recursion, maintaining the geometric decay in stabilization time on the “fastest” branch. The primary obstacle to keeping a small communication footprint with this approach is that if ℓ is faulty, we cannot prevent it from manipulating the clock it generates to make itself leader every 𝑋 + 1 rounds. However, we need that 𝑋 ∈ 𝑂 (1) to ensure fast stabilization if 𝑓 = 0. Hence, our previous strategy of amortizing the cost incurred by instances with faulty leaders is not going to work here. In fact, we can give up on filtering altogether and accept that ℓ is the leader in every instance, letting it choose when to initiate king consensus on its own. If correct, ℓ will choose a time that prevents an overlap with an instance controlled by 𝐶, and we let nodes ignore ℓ if it attempts to initiate an instance that would collide with one controlled by 𝐶.
10
Christoph Lenzen and Julian Loss
To avoid paying too much for the king consensus instances lead by ℓ, we relax the king agreement property to what we term weak king agreement: only if there are no faults whatsoever, ℓ needs to be able to get correct nodes to adopt the same value if their inputs differ. This relaxation to the weak king consensus task is irrelevant for our stabilization mechanism, as (weak) king agreement is only needed to stabilize the output clocks, and for this recursive pattern, the single-node branch of ℓ needs to ensure stabilization only if there are no faults. On the other hand, this provides us with just enough leeway to ensure that weak king consensus can be implemented at bit complexity 𝑂˜ (𝑛(𝑓 + 1)) even if ℓ is faulty. Our strategy here is to not rely on ℓ for “justifying” communication by correct nodes. Instead, we employ the following strategy, where we describe the special case that no node ignores the leader. (1) Nodes compare their current clock value to their neighbors in a constant-degree expander. If stabilization has been achieved, i.e., all correct nodes have the same clock value, no more than 𝑂 (𝑓 ) nodes, those with a faulty neighbor in the expander, can observe a discrepancy. On the other hand, if 𝑓 = 0 and 𝑘 > 0 nodes have a clock value different from the majority value, at least 𝜀𝑘 nodes, where the constant 𝜀 depends on the expander, observe a discrepancy. (2) All nodes observing a discrepancy alert all nodes of this. If 𝑣 receives 𝑘 𝑣 such alert messages, it queries each node 𝑤 ∈ {𝑣, . . . , 𝑣 + ⌈2𝑘 𝑣 /𝜀⌉ mod 𝑛} for its clock value; these nodes respond with their clock values. If the system has already stabilized, all of this incurs only 𝑂˜ (𝑛𝑓 ) bits of communication: by the previous point, then 𝑘 ∈ 𝑂 (𝑓 ) at each node 𝑣, so there are 𝑂 (𝑛𝑓 ) notification, query, and response messages in total. (3) All nodes for which half of their queries resulted in responses with clock values different from their own now query all nodes for their clock values, which respond. Again, by the choice of the communication pattern in the previous step, if all correct nodes agree, this does not cause more than 𝑂 (𝑓 ) nodes to perform such queries, resulting in 𝑂 (𝑛𝑓 ) messages in total. On the other hand, if 𝑓 = 0, each node that does not have the majority clock value will be among the querying nodes in this step and learn that at least half of the nodes (claim to) have a different clock value. In particular, more than 𝑡 nodes have a different clock value, proving to them that it is safe, i.e., will not violate validity, to adopt a clock value proposed by ℓ. (4) This is, finally, the point where ℓ steps in and proposes the majority value it perceives to all nodes. If 𝑓 = 0, this is the actual majority value. All nodes that learned in the previous step that it is safe to change value adopt the proposal by ℓ, which in case of 𝑓 = 0 establishes agreement, i.e., weak king agreement is satisfied. All other nodes simply output their input value, guaranteeing validity. 4
Conventions for Pseudocode
We will employ subroutines that are not self-stabilizing, but run only for a fixed number of rounds 𝑅 ∈ N. We refer to such a subroutine as an 𝑅-round algorithm. Note that it is trivial to obtain an 𝑅-round algorithm from any algorithm of round complexity at most 𝑅, by instructing nodes to wait until round 𝑅 before terminating and producing their output. There is also a fixed bound on the number of subroutine calls that are initialized per round. Each such instance has its own dedicated memory for each of its rounds, where we tacitly assume that there is a known bound on the amount of memory the subroutine requires. This approach can be seen as a implementing “self-stabilizing pipeline” for 𝑅-round algorithms: within 𝑅 rounds, all inconsistent state from a period of transient faults is erased. Note, however, that we cannot enforce a globally consistent initialization without a common round counter, which is the key challenge of this work.
Early-Stabilizing Counting
11
Moreover, we will run self-stabilizing algorithms as subroutines on a subset of the nodes as part of our recursive solutions. Again, there is a fixed number of such routines. We emphasize this, because it requires care when seeking to reduce the amortized bit complexity to 𝑜 (𝑛 2 ): this requires that in many rounds, most pairs of nodes do not exchange any messages. To make this possible while freely combining subroutines, the main routine gathers all messages to be sent to a given destination and concatenates them as a list of pairs consisting of a bit string identifying a subroutine and the corresponding message. If no message is sent by a given subroutine in a given round, we can safely omit the respective pair from the list. Whenever a subroutine sends a message, we will assume that it has size Ω(log 𝑛) for analysis purposes (even if it is smaller). Since in our recursive algorithms each node participates in 𝑂 (log 𝑛) different subroutines, this approach bears no asymptotic cost on communication bounds, but greatly simplifies the description of our routines. With this convention, we can leave the association of subroutine messages to the compiler. In fact, we will allow a constant number of send instructions to be executed by the same (sub)routine in a single round, tacitly assuming that they are treated in the same way. Moreover, we will occasionally send “special” messages that have a unique name, e.g. “req,” but no content. Again, we leave it to the compiler to choose an encoding such that these cannot be misinterpreted as, e.g., a clock value being sent. For convenience, we also assume that the compiler will choose an encoding that is not too wasteful, i.e., we can assume that if 𝑘 different messages can possibly be sent by a (sub)routine, the encoding usese 𝑂 (log 𝑘) bits. Faulty nodes may of course deviate from these rules. However, the compiler will instruct nodes to drop any received bit string that is not encoding a valid message. Note that it may still happen that due to an inconsistent (global) state or more than 𝑡 faults,7 code might produce out-of-spec results or not be able to execute at all. To address this, we make the following assumptions: • The compiler will insert checks for all state variables to make sure that the stored value encodes a valid value. If this is not the case, it resets the variable to an arbitrary in-spec default before executing the code. • 𝑅-round algorithms that are used as subroutines are given by a state machine. This state machine takes the round number, input (for round 1) or state at the end of the previous round (for rounds 2, . . . , 𝑅) to compute the messages it sends in that round, and with the additional input given by messages received from other nodes computes the state at the end of the round (for rounds 1, . . . , 𝑅 − 1) or output (for round 𝑅). For all our non-stabilizing subroutines, it will be obvious from the description that they can be realized this way with bounded memory. The number of required rounds 𝑅 will also be readily visible. • Pseudocode for self-stabilizing (sub)routines executes successully for any valid state and received messages. Again, this will be obvious from the description of our self-stabilizing (sub)routines. A more subtle point in this regard is that the code must also execute in a single round, as we cannot rely on the node knowing “which round it is,” i.e., any notion of round progression must be explicitly captured by local variables that can be affected by transient faults. To address this, we require that once a variable has been changed by an instruction that is conditioned on message reception, it cannot be used in any subsequent send instruction. Equivalently, when executing the code for a self-stabilizing routine in round 𝑟 , the content of each message sent is a function of the local variables’ states 𝑋 𝑣,𝑟 −1 at the end of round 𝑟 − 1.
7While we assume that 𝑓
𝑓 ′ > 𝑛 ′ /3 faults.
≤ 𝑡 during our analysis, note that subroutine calls on 𝑛 ′ < 𝑛 nodes may have to contend with
12
Christoph Lenzen and Julian Loss
• Bounds on message size are maintained even if 𝑓 > 𝑡. This is the only property we use in subroutine calls on node sets with too many faults, and it will be clear from our descriptions of algorithms as well. Moreover, we will frequently use statements of the form “if received 𝑘 times value 𝑥.” In such statements we tacitly assume that the respective messages are sent by distinct senders. In particular, if a faulty node sends more than one message in a given round, the compiler ensures that a correct receiver will process only the first one that arrives. Moreover, for notational convenience, nodes may send messages “to themselves;” in particular, a statement like “send 𝑥 to all nodes” executed by 𝑣 will trigger a subsequent “if received 𝑥 from 𝑤” condition at 𝑣 with 𝑤 = 𝑣 at node 𝑣. 5
Early-Stabilizing Counting
In this section, we develop the main approach for achieving stabilization time of 𝑂 (𝑓 + 1), leaving the issue of small amortized bit complexity for later. Observe that for a single node, 𝐶-counting is trivial to solve with 𝑆 = 1: the solitary node increments a counter modulo 𝐶 in each round and outputs its value. We will now solve 𝐶-counting recursively. To this end, we establish a general template for recursive 𝐶-counting, whose pseudocode is given in Algorithm 1. As outlined in Section 3, we partition the node set into 𝑉0 and 𝑉1 , execute a counting algorithm on each of them, and pass the outputs through filtering subroutines. We use their output to initiate instances of king consensus, cycling through leaders, but at slightly different frequencies determined by constants 𝑘𝑏 , where 𝑏 ∈ {0, 1}. In the following, for 𝑏 ∈ {0, 1} denote by 𝑆𝐶𝑏 the stabilization time of the instance of (𝑘𝑏 𝑛)counting on node set 𝑉𝑏 . Similarly, 𝑆 𝐹𝑏 is the stabilization time of the instance of (𝑘𝑏 𝑛, 𝑋, 𝑉𝑏 )-filtering.
Algorithm 1: A recursion template for 𝐶-counting on node set 𝑉 . We provide the code 𝑣 ∈ 𝑉 executes in each round. The positive integers 𝑋, 𝑅, 𝑘 0, 𝑘 1 ∈ 𝑂 (1) will be fixed later. The template is parametrized a partition 𝑉 = 𝑉0 ∪¤ 𝑉1 , solutions to counting on these sets, to filtering with them as clock sets, and to 𝑅-round king consensus on node set 𝑉 . Variables: for 𝑏 ∈ {0, 1}, outputs 𝐶 𝑏𝑣 and 𝐹 𝑣𝑏 of counting on 𝑉𝑏 and filtering with clock set 𝑉𝑏 Output: 𝐶 𝑣 ∈ [𝐶] 1 foreach 𝑏 ∈ {0, 1} do 2 if 𝐹 𝑣𝑏 mod 𝑘𝑏 𝑛 = 𝑘𝑏 𝑤 then ℓ𝑣𝑏 := 𝑤 else ℓ𝑣𝑏 := ⊥ 3 initialize king consensus on universe [𝐶] ∪ {⊥} with input (𝐶 𝑣 + 𝑅 mod 𝐶, ℓ𝑣𝑏 ) 4 for 𝑟 ∈ {𝑅, . . . , 1} do 5 execute the code of round 𝑟 of king consensus on the state stored for round 𝑟 and 𝑏 6 if 𝑟 = 𝑅 and the output of the instance is 𝑐 ∈ [𝐶] then 7 𝐶 𝑣 := 𝑐 8 else 9 store the new state in the memory block allocated for round 𝑟 + 1 and 𝑏 10 if 𝑣 ∈ 𝑉𝑏 then 11 execute the code of an instance of (𝑘𝑏 𝑛, 𝑋, 𝑉𝑏 )-filtering with input 𝐶 𝑏𝑣 and output 𝐹 𝑣𝑏 12 execute the code of an instance of (𝑘𝑏 𝑛)-counting on node set 𝑉𝑏 with output 𝐶 𝑏𝑣 13 else 14 execute the code of an instance of (𝑘𝑏 𝑛, 𝑋, 𝑉𝑏 )-filtering with output 𝐹 𝑣𝑏 15 𝐶 𝑣 := 𝐶 𝑣 + 1 mod 𝐶
Early-Stabilizing Counting
13
First, let us note that if there are not too many faults within 𝑉𝑏 , then the variables 𝐹 𝑣𝑏 stabilize and begin to count. Lemma 5.1. Suppose that for 𝑏 ∈ {0, 1}, it holds that 𝑓 < |𝑉𝑏 |/3. Then the variables 𝐹 𝑣𝑏 (𝑘𝑏 𝑛)-count from round 𝑟 ≥ 𝑆𝐶𝑏 + 𝑆 𝐹𝑏 . Proof. Within 𝑆𝐶𝑏 rounds, the variables 𝐶 𝑏𝑣 begin to count. By validity of clock filtering, the variables 𝐹 𝑣𝑏 thus count from round 𝑆𝐶𝑏 + 𝑆 𝐹𝑏 . □ On the other hand, even if there are too many faults in 𝑉𝑏 , the filtering subroutine ensures that there is a “virtual clock” 𝐹ˆ𝑟𝑏 ∈ [𝑘𝑏 𝑛] that counts for during each 𝑋 consecutive rounds, such that 𝑏 = 𝐹ˆ𝑏 or 𝐹 𝑏 = ⊥ in round 𝑟 . correct node 𝑣 either outputs 𝐹 𝑣,𝑟 𝑟 𝑣,𝑟 Lemma 5.2. For 𝑏 ∈ {0, 1} and rounds 𝑟 ≥ 𝑆 𝐹𝑏 , there is a virtual clock 𝐹ˆ𝑟𝑏 ∈ [𝑘𝑏 𝑛] such that (i) for all 𝑏 ∈ { 𝐹ˆ𝑏 , ⊥} and (ii) unless 𝑟 − 𝑟 = 0 mod 𝑋 , 𝐹ˆ𝑏 = 𝐹ˆ𝑏 + 1 mod 𝑘 𝑛. correct nodes 𝑣, it holds that 𝐹 𝑣,𝑟 0 𝑏 𝑟 𝑟 𝑟 −1 Proof. To define 𝐹ˆ𝑏 , consider in each interval 𝐼𝑖 := [𝑟 0 + 𝑖𝑋, 𝑟 0 + 𝑖 (𝑋 + 1) − 1] the minimal round 𝑏 ≠ ⊥ for some correct 𝑣 and set 𝐹ˆ𝑏 := 𝐹 𝑏 + 𝑟 − 𝑟 ′ for all 𝑟 ′ ∈ 𝐼 (if no such 𝑟 𝑟 ∈ 𝐼𝑖 such that 𝐹 𝑣,𝑟 𝑖 𝑣,𝑟 𝑟′ 𝑏 ). By the 𝑋 -round crusader agreement property of clock exists, use an arbitrary value instead of 𝐹 𝑣,𝑟 filtering, this results in a well-defined 𝐹ˆ𝑏 meeting the requirements. □ The main pillar of the proof of stabilization of Algorithm 1 is showing that eventually, there will be a “good” instance of king consensus, in the sense that all nodes agree on a correct leader and there is no “competing” instance that is initialized during its execution. Definition 5.3 (Unimpeded Instances). For 𝑏 ∈ {0, 1}, we say that the 𝑏-th instance of king consensus initialized in round 𝑟 runs with leader ℓ ∈ 𝑉 if (i) the variables 𝐹 𝑣𝑏 count from round 𝑟 and (ii) each correct node 𝑣 inputs (𝑥 𝑣 , ℓ) for some 𝑥 𝑣 ∈ [𝐶]. Furthermore, such an instance is unimpeded if in addition (i) ℓ is correct and (ii) correct nodes 𝑣 initialize all other instances of king consensus in rounds 𝑟 ′ ∈ {𝑟, 𝑟 + 1, . . . , 𝑟 + 𝑅} with ℓ𝑣 = ⊥. Before proving that such an instance will occur in a timely fashion, let us formalize that an unimpeded instance translates to stabilization. Lemma 5.4. Assume that in round 𝑟 ∈ N an unimpeded instance of king consensus is initialized. Then the variables 𝐶 𝑣 count from round 𝑟 + 𝑅. Proof. By the king agreement property of 𝑅-round king consensus, there is some 𝑦 ∈ [𝐶] such that all correct nodes 𝑣 output 𝑦 𝑣 = 𝑦 from the unimpeded instance. Observe that, granted that no king consensus instance outputs a value different from 𝑦 + 𝑟 ′ − 𝑟 mod 𝐶 or ⊥ in a round 𝑟 ′ ≥ 𝑟 at some correct 𝑣, correct nodes will set 𝐶 𝑣,𝑟 := 𝑦 and, by induction, the variables 𝐶 𝑣 will count from round 𝑟 . To show this, recall that the definition of an unimpeded instance requires that correct nodes 𝑣 have ℓ𝑣 = ⊥ in all other king consensus instances initialized in rounds 𝑟 ′ ∈ {𝑟, 𝑟 + 1, . . . , 𝑟 + 𝑅}, i.e., from the initiliazation of the unimpeded instance until it outputs in round 𝑟 + 𝑅. By the default property of king consensus, this entails that all other instances initiated in these rounds output ⊥ at correct nodes. Accordingly, it remains to consider instances that are initiated in rounds 𝑟 ′ > 𝑟 . Assume for contradiction that there is a minimal round 𝑟 ′ > 𝑟 such that an instance initiated in round 𝑟 ′ outputs 𝑦 𝑣 ∉ {𝑦 + 𝑟 ′ − 𝑟 + 𝑅 mod 𝐶, ⊥} at some correct 𝑣 (which it does in round 𝑟 ′ + 𝑅). As this instance is initialized after round 𝑟 , but is the first instance that outputs 𝑦 𝑣 ∉ {𝑦 + 𝑟 ′ − 𝑟 + 𝑅 mod 𝐶, ⊥}, correct nodes used inputs 𝑥 𝑣 ∈ {𝑦 + 𝑟 ′ − 𝑟 + 𝑅 mod 𝐶, ⊥} to the instance. By the validity property
14
Christoph Lenzen and Julian Loss
of king consenus, they must output 𝑦 𝑣 ∈ {𝑦 + 𝑟 ′ − 𝑟 + 𝑅 mod 𝐶, ⊥}, reaching a contradiction and concluding the proof. □ In order to show that suitable parameter choices result in quick emergence of an unimpeded instance, we first state a straightforward, but technical helper lemma for said choices. Lemma 5.5. Suppose that a constant 0 < 𝜀 < 1 and natural 𝑅 ∈ 𝑂 (1) are given. Then there are natural 𝑅 < 𝑘 0, 𝑘 1 ∈ 𝑂 (1) with the following property. For any choices of 𝑜 ∈ Z, 𝑏 ∈ {0, 1}, and 𝐿max ∈ Z>0 , it holds that |{𝐿 ∈ N, 𝐿 ≤ 𝐿max | [𝑘𝑏 · 𝐿, 𝑘𝑏 · 𝐿 + 𝑅] ∩ {𝑘 1−𝑏 · 𝐿 ′ + 𝑜 } | 𝐿 ′ ∈ Z} ≠ ∅}| ≤ 𝜀𝐿max + 1. Proof. Let 𝑘 0 := ⌈(𝑅 + 1)/𝜀⌉ and 𝑘 1 := 𝑘 0 + 𝑅 + 1. Let 𝐿 ∈ N be minimal with the property that [𝑘𝑏 · 𝐿, 𝑘𝑏 · 𝐿 + 𝑅] ∩ {𝑘 1−𝑏 · 𝐿 ′ + 𝑜 | 𝐿 ′ ∈ Z} ≠ ∅. By the choices of 𝑘𝑏 , 𝑏 ∈ {0, 1}, it follows that for 𝐿 + 1, 𝐿 + 2, . . . , 𝐿 + ⌈1/𝜀⌉ − 1 the intersection is empty. Repeating this argument inductively, the claim follows. □ We are now ready to resolve the choices of constants that guarantee an unimpeded instance 𝑂 (𝑓 + 1) rounds after one of the recursive counting instances and both filtering subroutines have stabilized. Lemma 5.6. If 𝑅 ∈ 𝑂 (1), there are constants 𝑋, 𝑘 0, 𝑘 1 with the following property. If for 𝑏 ∈ {0, 1} it holds that 𝑓 < |𝑉𝑏 |/3, there is an unimpeded instance within max{𝑆𝐶𝑏 + 𝑆 𝐹𝑏 , 𝑆 𝐹1−𝑏 } + 𝑂 (𝑓 + 1) rounds. Proof. By Lemma 5.1, the variables 𝐹 𝑣𝑏 count from round 𝑆𝐶𝑏 + 𝑆 𝐹𝑏 . By Lemma 5.2, there is a virtual clock 𝐹ˆ1−𝑏 such that for each 𝑖 ∈ N and 𝑟 ∈ 𝐼𝑖 := [𝑆 𝐹1−𝑏 + 𝑖𝑋 + 1, 𝑆 𝐹1−𝑏 + (𝑖 + 1)𝑋 − 1], it holds 1−𝑏 ˆ1−𝑏 , ⊥} for all that 𝐹ˆ𝑟1−𝑏 = 𝐹ˆ𝑟1−𝑏 −1 + 1 mod 𝑘𝑏 𝑛 and for each correct node 𝑣, we have that 𝐹𝑟,𝑣 ∈ { 𝐹𝑟 1−𝑏 𝑟 ≥ 𝑆 𝐹 . We apply Lemma 5.5 as follows: • Fix 𝑘 0, 𝑘 1 as given by the lemma for 𝜀 = 1/4 and the given value of 𝑅. • Fix 𝑋 = 5 max{𝑘 0, 𝑘 1 } + 𝑅 and 𝐿max := ⌊(𝑋 − 𝑅)/𝑘𝑏 ⌋ − 1 > 4. • Fix 𝑖 ∈ N such that 𝑆 𝐹1−𝑏 + 𝑖𝑋 ≥ 𝑆𝐶𝑏 + 𝑆 𝐹𝑏 . Let 𝑟𝑏 ∈ 𝐼𝑖 be minimal such that there is ℓ𝑏 ∈ 𝑉 𝑏 with 𝐹 𝑣,𝑟 = 𝑘𝑏 ℓ𝑏 mod 𝑘𝑏 𝑛 for some correct node 𝑣. 𝑏 • Let 𝑟 1−𝑏 ∈ 𝐼𝑖 be minimal such that there is ℓ1−𝑏 ∈ 𝑉 with 𝐹ˆ𝑟1−𝑏 = 𝑘 1−𝑏 ℓ1−𝑏 mod 𝑘 1−𝑏 𝑛 for 1−𝑏 some correct node 𝑣. Choose 𝑜 := 𝑟 1−𝑏 − 𝑟𝑏 . Now consider a leader ℓ ∈ {ℓ𝑏 , ℓ𝑏 + 1, . . . , ℓ𝑏 + 𝐿max }, where for convenience we identify values ℓ > 𝑛 with the node 𝑣 such that 𝑣 = ℓ mod 𝑛. Observe that 𝑟𝑏 + (ℓ − ℓ𝑏 )𝑘𝑏 ≥ 𝑟𝑏 and 𝑟𝑏 + (ℓ − ℓ𝑏 )𝑘𝑏 + 𝑅 ≤ 𝑟𝑏 + 𝐿max𝑘𝑏 + 𝑅 ≤ 𝑟𝑏 + 𝑋 − 𝑘𝑏 ≤ 𝑆 𝐹1−𝑏 + (𝑖 + 1)𝑋 − 1, where the last step uses that 𝑟𝑏 is one of the first 𝑘𝑏 rounds of 𝐼𝑖 . That is, we have that 𝐽ℓ := {𝑟𝑏 + (ℓ − ℓ𝑏 )𝑘𝑏 , 𝑟𝑏 + (ℓ − ℓ𝑏 )𝑘𝑏 + 1, . . . , 𝑟𝑏 + (ℓ − ℓ𝑏 )𝑘𝑏 + 𝑅 − 1} ⊂ 𝐼𝑖 . Recall that the variables 𝐹 𝑣𝑏 count from round 𝑆𝐶𝑏 + 𝑆 𝐹𝑏 , which due to our choice of 𝑖 is no later than the last round before 𝐼𝑖 . Hence, the 𝑏-th instance of king consensus initialized in round 𝑟𝑏 + (ℓ − ℓ𝑏 )𝑘𝑏 − 1 runs with leader ℓ, where the substraction of 1 takes into account that ℓ𝑣𝑏 is 𝑏 𝑏 determined based on 𝐹 𝑣,𝑟 −1 in round 𝑟 , i.e., before 𝐹 𝑣 is updated by the filtering subroutine. Because 𝑘𝑏 > 𝑅, each correct node 𝑣 initializes its 𝑏-th instance in rounds 𝑟 ∈ 𝐽ℓ \ {𝑟𝑏 + (ℓ − ℓ𝑏 )𝑘𝑏 } with ℓ𝑣 = ⊥. We conclude that the instance is unimpeded if and only if (i) ℓ is correct and (ii) no correct node 𝑣 uses input ℓ𝑣 ≠ ⊥ on its (1 − 𝑏)-th instance in some round 𝑟 ∈ 𝐽ℓ . Let 𝑖 0 ∈ N be minimal such that (i) 𝑆 𝐹1−𝑏 + 𝑖 0𝑋 + 1 ≥ 𝑆𝐶𝑏 + 𝑆 𝐹𝑏 , (ii) the variables 𝐹 𝑣𝑏 do not 𝑏 = 𝐹𝑏 “overflow” during 𝐼𝑖 0 , i.e., 𝐹 𝑣,𝑟 𝑣,𝑟 −1 + 1 for all 𝑟 ∈ 𝐼𝑖 0 , and (iii) fewer than half of the leaders {ℓ𝑏 , ℓ𝑏 + 1, . . . , ℓ𝑏 + 𝐿max } for the interval 𝐼𝑖 are faulty. Since there are at most 𝑓 faulty nodes and
Early-Stabilizing Counting
15
𝑛 > 3𝑓 (i.e., we do not run out of “fresh” leaders before exhausting the fault budget),8 we have that 𝑖 0 ∈ max{(𝑆𝐶𝑏 + 𝑆 𝐹𝑏 − 𝑆 𝐹1−𝑏 )/𝑋, 0} + 𝑂 (𝑓 + 1). By our choices of 𝜀, 𝑘 0 , 𝑘 1 , and 𝑜, Lemma 5.5 guarantees that out of the remaining at least 𝐿max /2 correct leaders ℓ, all but 𝐿max /4 + 1 satisfy that [𝑘𝑏 (ℓ − ℓ𝑏 ), 𝑘𝑏 (ℓ − ℓ𝑏 ) + 𝑅] ∩ {𝑘 1−𝑏 · 𝐿 + 𝑟 1−𝑏 − 𝑟𝑏 | 𝐿 ∈ Z} = ∅. By our choice of 𝐿max , 𝐿max /2 − 𝐿max /4 − 1 > 0, i.e., some correct ℓ satisfying the above constraint exists. We claim that the corresponding 𝑏-th instance initiliazed in round 𝑟𝑏 + (ℓ − ℓ𝑏 )𝑘𝑏 is unimpeded. Given that ℓ is correct, it remains to show that no correct node 𝑣 initilializes a (1−𝑏)-th instance with 1−𝑏 ∈ { 𝐹ˆ1−𝑏 , ⊥}, this is only possible if 𝐹ˆ1−𝑏 mod 𝑘 ℓ𝑣 ≠ ⊥ in some round 𝑟 ∈ 𝐽ℓ . Because 𝐹 𝑣,𝑟 1−𝑏 = 0. 𝑟 𝑟 Accordingly, assume for contradiction that 𝐹ˆ𝑟1−𝑏 mod 𝑘 1−𝑏 = 0 for some 𝑟 ∈ 𝐽ℓ . Recall that 𝐹ˆ𝑟1−𝑏 = 𝐹ˆ𝑟1−𝑏 + 𝑟 ′ − 𝑟 mod 𝑘 1−𝑏 𝑛 for all 𝑟, 𝑟 ′ ∈ 𝐼𝑖 and that 𝐹ˆ𝑟1−𝑏 = 0 mod 𝑘 1−𝑏 . Therefore, ′ 1−𝑏 0 = 𝐹ˆ𝑟1−𝑏 mod 𝑘 1−𝑏 = 𝐹ˆ𝑟1−𝑏 + 𝑟 − 𝑟 1−𝑏 mod 𝑘 1−𝑏 = 𝑟 − 𝑟 1−𝑏 mod 𝑘 1−𝑏 , 1−𝑏 i.e., 𝑟 − 𝑟𝑏 ∈ {𝑘 1−𝑏 · 𝐿 + 𝑟 1−𝑏 − 𝑟𝑏 | 𝐿 ∈ Z}. On the other hand, by our choice of 𝑖 0 , 𝑏 𝑏 𝐹 𝑣,𝑟 − 𝐹 𝑣,𝑟 = 𝑟 − 𝑟𝑏 ∈ [𝑘𝑏 (ℓ − ℓ𝑏 ), 𝑘𝑏 (ℓ − ℓ𝑏 ) + 𝑅]. 𝑏
We reach the contradiction that 𝑟 − 𝑟𝑏 is in the intersection of these two sets, which by Lemma 5.5 is empty. We conclude that the instance is unimpeded, as claimed. Since 𝑖 0 ∈ max{(𝑆𝐶𝑏 + 𝑆 𝐹𝑏 − 𝑆 𝐹1−𝑏 )/𝑋, 0} + 𝑂 (𝑓 + 1), this instance occurs by round max{𝑆𝐶𝑏 + 𝑆 𝐹𝑏 , 𝑆 𝐹1−𝑏 } + 𝑂 (𝑓 + 1). □ Putting the above results together, we arrive at the following theorem. Theorem 5.7. If 𝑅 ∈ 𝑂 (1), there are constants 𝑘 0 , 𝑘 1 , and 𝑋 such that Algorithm 1 solves 𝐶-counting with stabilization time max𝑏 ∈ {0,1} {𝑆𝐶𝑏 + 𝑆 𝐹𝑏 } + 𝑂 (𝑓 + 1). If 𝑓 < |𝑉𝑏 |/3 for some 𝑏 ∈ {0, 1}, then the stabilization time is max{𝑆𝐶𝑏 + 𝑆 𝐹𝑏 , 𝑆 𝐹1−𝑏 } + 𝑂 (𝑓 + 1). Proof. We show the second statement first. By Lemma 5.6 and the assumptions of the theorem, there is an unimpeded instance of king consensus within max{𝑆𝐶𝑏 + 𝑆 𝐹𝑏 , 𝑆 𝐹1−𝑏 } + 𝑂 (𝑓 + 1) rounds. By Lemma 5.4, the output variables then start to count from some round 𝑟 ∈ max{𝑆𝐶𝑏 + 𝑆 𝐹𝑏 , 𝑆 𝐹1−𝑏 } + 𝑂 (𝑓 + 1). Regarding the first statement, recall that 𝑓 < 𝑛/3 and 𝑉0 and 𝑉1 partition 𝑉 = {1, . . . , 𝑛}, so there must be some 𝑏 ∈ {0, 1} so that 𝑓 < |𝑉𝑏 |/3. Since max{𝑆𝐶𝑏 + 𝑆 𝐹𝑏 , 𝑆 𝐹1−𝑏 } ≤ max𝑏 ∈ {0,1} {𝑆𝐶𝑏 + 𝑆 𝐹𝑏 }, the claim readily follows from the second statement. □ In the following, we will tacitly assume that the constants in Algorithm 1 are chosen in accordance with Theorem 5.7 for the 𝑅 ∈ 𝑂 (1) given by the choice of the king consensus algorithm employed. Applying the recursive scheme with the trivial solution on single nodes, we arrive at the following result. Corollary 5.8. 𝐶-counting can be solved with stabilization time 𝑂 (𝑓 + 1 + log 𝑛), where each correct node sends 𝑂 (log 𝐶 + log2 𝑛) bits to each other node in each round. Proof. By Lemmas 2.3 and 2.7, there are filtering and king consensus protocols that run in a constant number of rounds and use messages of size 𝑂 (log 𝐶) and 𝑂 (log |V |), respectively. We recursively apply Algorithm 1, where we partition the node set as evenly as possible in each recursion step and the base case of 𝑛 = 1 is trivial. In each step of the recursion, either 𝑉0 or 𝑉1 8 Due to condition (ii), this applies as-is only if 𝑛 is a sufficiently large constant. However, if 𝑛 = 𝑂 (1), we may work with
clocks that count modulo 𝑚𝑘𝑏 𝑛 for a sufficiently large constant 𝑚 instead.
16
Christoph Lenzen and Julian Loss
contains at most half of the faulty nodes. Hence, summing over the at most ⌈log 𝑛⌉ steps along the respective root-leaf path in the recursion tree, the stabilization time is bounded by ⌈log 𝑛⌉ −1 ∑︁
𝑂 (2−𝑖 𝑓 + 1) = 𝑂 (𝑓 + 1 + log 𝑛).
𝑖=0
The message size bound follows by observing that (i) each node participates in 𝑂 (log 𝑛) recursive instances, each running a constant number of concurrent instances of filtering and king consensus, and (ii) all of these instances but the top-level king consensus instances, which have message size 𝑂 (log 𝐶), use messages of size 𝑂 (log 𝑛). □ We remark that it is straightforward to remove the additive 𝑂 (log 𝑛) by alternating between splitting off a single node and using a balanced partition (as in Corollary 5.8). However, this will become more challenging when also taking into account amortized bit complexity. We hence defer this to Section 7. 6
Reducing Communication Complexity
We need to reduce the communication cost of both the filtering and king consensus routines to realize our 𝑂˜ (𝑛(𝑓 + 1)) target. We address each of them separately, starting with king consensus. 6.1
King Consensus with less Communication
As discussed in Section 3, it is sufficient to consider the case of a correct king after stabilization only, as all other cases combined do not bust our communication budget. We construct our improved solution to king consensus from relaxed versions of graded agreement. The first relaxes the graded agreement property to hold only if an additional input bit is 1 at all correct nodes. Definition 6.1 (Weak Graded Agreement). The Weak Graded Agreement problem is specified as follows. Each node 𝑣 has input (𝑥 𝑣 , 𝑠 𝑣 ) ∈ V × {0, 1}. Each node 𝑣 computes an output (𝑦 𝑣 , 𝑔𝑣 ) ∈ V × {0, 1} with the following guarantees: • Validity: If there is 𝑥 ∈ V so that 𝑥 𝑣 = 𝑥 for all correct 𝑣, then (𝑦 𝑣 , 𝑔𝑣 ) = (𝑥, 1) for all correct 𝑣. • Weak Graded Agreement: If 𝑠 𝑣 = 1 for all 𝑣 and 𝑔𝑤 = 1 for some correct 𝑤, then 𝑦 𝑣 = 𝑦 𝑤 for all correct 𝑣. If 𝑠 𝑣 = 0, for this relaxed task we can get away with 𝑣 sending no message. Lemma 6.2. Weak graded agreement can be solved in 2 rounds, where each node sends an 𝑂 (log |V |)sized message to each other node in each round. If node 𝑣 has input 𝑠 𝑣 = 0, 𝑣 sends no messages. Proof. We claim that the following algorithm achieves the stated guarantees. Algorithm 2: Weak graded agreement. Input: (𝑥 𝑣 , 𝑠 𝑣 ) ∈ V × {0, 1} Output: (𝑦 𝑣 , 𝑔𝑣 ) ∈ V × {0, 1} 1 if 𝑠 𝑣 = 1 then send 𝑥 𝑣 to all nodes // first communication round 2 if 𝑠 𝑣 = 1 and received at most 𝑡 messages different from 𝑥 𝑣 then send 𝑥 𝑣 to all nodes 3 else if 𝑠 𝑣 = 1 then send “NACK” to all nodes // second communication round 4 if received at most 𝑡 messages different from 𝑥 𝑣 then (𝑦 𝑣 , 𝑔𝑣 ) := (𝑥 𝑣 , 1) 5 else if received 𝑡 + 1 times 𝑥 ∈ V then (𝑦 𝑣 , 𝑔𝑣 ) := (𝑥, 0) // break ties arbitrarily 6 else (𝑦 𝑣 , 𝑔𝑣 ) := (𝑥 𝑣 , 0) The running time and bounds on communication can be readily verified from this description.
Early-Stabilizing Counting
17
Validity: If there is 𝑥 ∈ V so that 𝑥 𝑣 = 𝑥 for all correct 𝑣, then each 𝑣 receives values other than 𝑥 = 𝑥 𝑣 from the at most 𝑡 faulty nodes only. Hence, (𝑦 𝑣 , 𝑔𝑣 ) = (𝑥, 1) for all correct 𝑣. Weak Graded Agreement: Suppose that 𝑠 𝑣 = 1 for all 𝑣 and 𝑔𝑤 = 1 for some correct 𝑤. Since 𝑠 𝑣 = 1 for all 𝑣, correct nodes always send messages. Hence, 𝑤 received at least 𝑛 − 2𝑡 > 𝑡 messages with 𝑥 𝑤 in the second round from correct nodes. Their senders must have received at least 𝑛 − 2𝑡 > 𝑡 messages with 𝑥 𝑤 from correct nodes in the first round, or they would have sent “NACK” messages. It follows that each correct 𝑣 with 𝑥 𝑣 ≠ 𝑥 𝑤 receives more than 𝑡 values different from 𝑥 𝑣 in the first round, implying that it will not send 𝑥 𝑣 again in the second round. Therefore, in the second round each node receives more than 𝑡 times 𝑥 𝑤 and at most 𝑡 times 𝑥 for any 𝑥 ≠ 𝑥 𝑤 . We conclude that each correct 𝑣 outputs 𝑦 𝑣 = 𝑥 𝑤 . □
The second relaxed variant of graded agreement is leader-based. The second output bit, the “grade,” is intended for use by the leader only. Accordingly, the validity property does not require grade 1, and the graded agreement property is relaxed to requiring that if a correct agreed-on leader ℓ outputs 𝑔ℓ = 1, then all nodes should output the same value as the leader (regardless of grade). An additional property we refer to as king validity is what will enable the leader to leverage the reduced cost of weak graded agreement if 𝑠 𝑣 = 0: if all nodes agree on the input value and a correct leader, the leader is guaranteed to output 𝑔ℓ = 1. As graded king agreement implies that 𝑔ℓ = 1 guarantees that all nodes already agree, the leader then can decide whether to invoke weak graded agreement with inputs 𝑠 𝑣 = 1 or 𝑠 𝑣 = 0 based on 𝑔ℓ . Definition 6.3 (Graded King Consensus). The Graded King Consensus problem is specified as follows. Each node 𝑣 has inputs 𝑥 𝑣 ∈ V and ℓ𝑣 ∈ 𝑉 ∪¤ {⊥}. Each node 𝑣 computes an output (𝑦 𝑣 , 𝑔𝑣 ) ∈ V × {0, 1} with the following guarantees: • Validity: If there is 𝑥 ∈ V so that 𝑥 𝑣 = 𝑥 for all correct 𝑣, then 𝑦 𝑣 = 𝑥 for all correct 𝑣. • King Validity: If there are (𝑥, ℓ) ∈ V × 𝑉 so that (𝑥 𝑣 , ℓ𝑣 ) = (𝑥, ℓ) for all correct 𝑣 and ℓ is correct, then 𝑔ℓ = 1. • Graded King Agreement: If ℓ𝑣 = ℓ for all correct 𝑣 and some correct ℓ and 𝑔ℓ = 1, then 𝑦 𝑣 = 𝑦ℓ for all correct 𝑣. The requirements of graded king consensus are sufficiently flexible that it suffices for the leader to check everyone’s values and advise a change if it looks like they might agree, i.e., it receives 𝑛 − 𝑡 times the same value. In this case, it can advise the nodes with different values to change it, which they can verify to be safe (i.e., not violate validity), by confirming that there are at least 𝑡 + 1 ≤ 𝑛 − 2𝑡 nodes claiming to have this value. If the everybody agrees on the input values and a correct leader, this causes no communication between correct non-leader nodes. Lemma 6.4. Graded king consensus can be solved within 4 rounds with message size 𝑂 (log |V |) and the following property. If there is (𝑥, ℓ) ∈ V × (𝑉 ∪ {⊥}) so that (𝑥 𝑣 , ℓ𝑣 ) = (𝑥, ℓ) for all correct 𝑣, correct nodes 𝑣 ≠ ℓ send messages to ℓ (if ℓ ≠ ⊥) or faulty nodes only, i.e., 𝑂 (𝑛(𝑓 + 1) log |V |) bits are sent by correct nodes. Proof. We claim that the following algorithm achieves the stated guarantees.
18
Christoph Lenzen and Julian Loss
Algorithm 3: Graded king consensus. Input: (𝑥 𝑣 , ℓ𝑣 ) ∈ V × (𝑉 ∪¤ {⊥}) Output: (𝑦 𝑣 , 𝑔𝑣 ) ∈ V × {0, 1} 1 if ℓ𝑣 ≠ ⊥ then send 𝑥 𝑣 to ℓ𝑣 // first round 2 if ℓ𝑣 = 𝑣 and received 𝑛 − 𝑡 times 𝑥 𝑣 then 3 send 𝑥 𝑣 to all nodes // second round 4 𝑔𝑣 := 1 5 else 𝑔𝑣 := 0 6 if received 𝑥 ℓ𝑣 ≠ 𝑥 𝑣 from ℓ𝑣 ≠ ⊥ then send 𝑥 ℓ𝑣 to all nodes // third round 7 if received 𝑥 𝑤 = 𝑥 𝑣 from 𝑤 then send 𝑥 𝑣 to 𝑤 // fourth round 8 if received more than 𝑡 times 𝑥 then 𝑦 𝑣 := 𝑥 else 𝑦 𝑣 := 𝑥 𝑣 // break ties arbitrarily The running time and message size bound can be readily verified from this description. Moreover, if there is (𝑥, ℓ) ∈ V × (𝑉 ∪ {⊥}) so that (𝑥 𝑣 , ℓ𝑣 ) = (𝑥, ℓ) for all correct 𝑣, then ℓ receives 𝑥 = 𝑥 ℓ at least 𝑛 − 𝑡 times in the first round. Hence, it sends 𝑥 = 𝑥 𝑣 to each node 𝑣 in the second, so that correct nodes 𝑣 do not send messages in the third round. The same applies if ℓ = ⊥, as then no node 𝑣 receives a message from ℓ𝑣 ≠ ⊥ in the second round. Thus, correct nodes send no messages to correct nodes in the last round. Accordingly, in the final round no messages are sent to correct nodes. Overall, any message is either sent or received by ℓ or a faulty node, implying the second bound on communication. Validity: If there is 𝑥 ∈ V so that 𝑥 𝑣 = 𝑥 for all correct 𝑣, then no node 𝑣 can receive more than 𝑡 times a value 𝑥 ′ ≠ 𝑥 in the final round. Hence, each correct node 𝑣 outputs 𝑦 𝑣 = 𝑥 𝑣 = 𝑥. King Validity: If in addition ℓ𝑣 = ℓ for all 𝑣 and correct ℓ ∈ 𝑉 , then ℓ receives 𝑥 ℓ = 𝑥 from all correct nodes in the first step. Hence, it sets 𝑔ℓ := 1 and eventually outputs this value. Graded King Agreement: Suppose that ℓ𝑣 = ℓ for all correct 𝑣 and some correct ℓ, and also that 𝑔ℓ = 1. Thus, ℓ receives 𝑛 − 𝑡 times 𝑥 ℓ in the first round, meaning that at least 𝑛 − 2𝑡 > 𝑡 correct nodes have input 𝑥 𝑣 = 𝑥 ℓ . Node ℓ sends 𝑥 ℓ to all nodes in the second round, prompting each 𝑣 with 𝑥 𝑣 ≠ 𝑥 ℓ to send 𝑥 ℓ to all nodes in the third round. Each correct node 𝑤 with 𝑥 𝑤 = 𝑥 ℓ responds with 𝑥 ℓ in the last round, while correct nodes send no messages different from 𝑥 ℓ . Hence, in the final round each 𝑣 with 𝑥 𝑣 ≠ 𝑥 ℓ will receive more than 𝑡 times 𝑥 ℓ , while no node receives more than 𝑡 times any other value. We conclude that all correct nodes 𝑣 output 𝑦 𝑣 = 𝑥 ℓ . □
We can now plug these two subroutines together as follows. First, graded king consensus either ensures that all nodes agree (output 𝑔ℓ = 1) or the king tells all nodes to use input 𝑠 𝑣 = 1 for weak graded agreement, making it behave like a “regular” graded agreement subroutine. This establishes the requirements of king consensus while preventing high communication cost if all nodes agree on a correct leader and the same input value: in this case, graded king consensus is cheap with output 𝑔ℓ = 1, which will result in cheap weak graded agreement (input 𝑠 𝑣 = 0 at all nodes 𝑣). Theorem 6.5. King Consensus can be solved in 8 rounds with message size 𝑂 (log |V |). In addition, correct nodes send only 𝑂 (𝑛(𝑓 + 1) log |V |) bits in total if there is (𝑥, ℓ) ∈ V × (𝑉 ∪ {⊥}) such that (𝑥 𝑣 , ℓ𝑣 ) = (𝑥, ℓ) for each 𝑣 and ℓ is not faulty. Proof. We claim that the following algorithm achieves the stated guarantees.
Early-Stabilizing Counting
19
Algorithm 4: King consensus algorithm with improved bit complexity. Input: (𝑥 𝑣 , ℓ𝑣 ) ∈ V × (𝑉 ∪¤ {⊥}) Output: 𝑦 𝑣 ∈ V ∪¤ {⊥} 1 run the protocol from Lemma 6.4 with input (𝑥 𝑣 , ℓ𝑣 ) and output (𝑘 𝑣 , ℎ 𝑣 ) // four rounds 2 if ℓ𝑣 = 𝑣 and ℎ 𝑣 = 0 then send “runGC” to all nodes // fifth round 3 if received “runGC” from ℓ𝑣 ≠ ⊥ then 4 run the protocol from Lemma 6.2 with input (𝑘 𝑣 , 1) and output (𝑧 𝑣 , 𝑔𝑣 ) 5 else run the protocol from Lemma 6.2 with input (𝑘 𝑣 , 0) and output (𝑧 𝑣 , 𝑔𝑣 )// two rounds 6 if ℓ𝑣 = 𝑣 then send 𝑧 𝑣 to all nodes // eighth round 7 if ℓ𝑣 = ⊥ then 𝑦 𝑣 := ⊥ 8 else if 𝑔𝑣 = 0 and received 𝑧 ℓ𝑣 from ℓ𝑣 then 𝑦 𝑣 := 𝑧 ℓ𝑣 9 else 𝑦 𝑣 := 𝑧 𝑣 The round complexity and bound on the message size are immediate from the description and Lemmas 6.2 and 6.4. If there is (𝑥, ℓ) ∈ V × (𝑉 ∪ {⊥}) such that (𝑥 𝑣 , ℓ𝑣 ) = (𝑥, ℓ) for each 𝑣 and ℓ is not faulty, Lemma 6.4 states that correct nodes send 𝑂 (𝑛(𝑓 + 1) log |V |) in the first step. Moreover, if ℓ ≠ ⊥, in this case the king validity property of king consensus entails that 𝑔ℓ = 1. Hence, no node 𝑣 receives a message from ℓ𝑣 ≠ ⊥ in the fifth round. Hence, all nodes 𝑣 use input 𝑠 𝑣 = 0 in the call to weak graded agreement. By Lemma 6.2, then no messages are sent by correct nodes in the third step. In the final round, the only correct node sending messages is ℓ. Summing up, this establishes the claimed bound on communication. Validity: If there is 𝑥 ∈ V so that 𝑥 𝑣 = 𝑥 for all correct 𝑣, then correct nodes output 𝑦 𝑣 = 𝑥 from the call to graded king consensus by its validity condition. By the validity condition of weak graded agreement, each correct node then outputs (𝑥, 1) from the call to weak graded agreement. Hence, each node 𝑣 outputs 𝑦 𝑣 ∈ {𝑥, ⊥}. Default: Immediately follows from the output instruction. King Agreement: If there is correct ℓ ∈ 𝑉 so that ℓ𝑣 = ℓ for all correct 𝑣, we distinguish two cases. If ℓ outputs (𝑘 ℓ , 1) from the call to graded king consensus, then by graded king agreement each correct 𝑣 outputs (𝑘 ℓ , ℎ 𝑣 ) for some ℎ 𝑣 ∈ {0, 1} from the call. By the validity condition of weak graded agreement, each correct node then outputs (𝑘 ℓ , 1) from the call to weak graded agreement. As ℓ𝑣 = ℓ ≠ ⊥ for each correct 𝑣, each 𝑣 then outputs 𝑘 ℓ . On the other hand, if ℓ outputs (𝑘 ℓ , 0) from the call to graded king consensus, it sends “runGC” to all nodes, which then input 𝑠 𝑣 = 1 to the weak graded agreement instance. Again, we distinguish two cases. If some correct node 𝑤 outputs 𝑔𝑤 = 1, by weak graded agreement all nodes 𝑣 have 𝑧 𝑣 = 𝑧 𝑤 . In particular, ℓ sends 𝑧 ℓ = 𝑧 𝑤 in the final communication round, resulting in all nodes outputting 𝑧 𝑤 . Otherwise, all correct nodes 𝑣 have 𝑔𝑣 = 0 and therefore output the value 𝑧 ℓ sent by ℓ in the final communication round. □ 6.2
Filtering with less Communication
Filtering we approach by accepting to work with possibly stale information on other nodes’ view of the filtered clock. Only when inconsistencies are observed, more communication is applied. First, we can adopt a simple round-robin solution to checking whether nodes in 𝑇 claim a different clock value. If this value is different from its own, node 𝑣 will query all nodes for their values to “refresh” its view. Since at most 𝑓 nodes in 𝑇 do so after stabilization, this results in an amortized bit complexity of 𝑂˜ (𝑛 2 (𝑓 + 1)/|𝑇 |), which is within budget for |𝑇 | = Ω(𝑛). At the same time, within 𝑓 +𝑂 (1) rounds, 𝑣 will detect if its own clock value differs from the majority value in 𝑇 and adjust it.
20
Christoph Lenzen and Julian Loss
Algorithm 5: (𝐶, 𝑋,𝑇 )-filtering algorithm with reduced amortized bit complexity, code at node 𝑣 ∈ 𝑉 executed in each round. W.l.o.g., we assume that 𝑇 = {1, . . . , |𝑇 |}. Input: 𝐶 𝑣 ∈ [𝐶] iff 𝑣 ∈ 𝑇 Variables: 𝐹ˆ𝑣,𝑤 ∈ [𝐶] and 𝑠 𝑣,𝑤 ∈ {0, 1} for 𝑤 ∈ 𝑉 , 𝐹ˆ𝑣 ∈ [𝐶], 𝑋 𝑣 ∈ [𝑋 + 2], 𝑁 𝑣 ∈ [𝑛], 𝑇𝑣 ∈ [|𝑇 |], 𝑎 𝑣 ∈ {0, 1} Output: 𝐹 𝑣 ∈ [𝐶] ∪ {⊥} 1 𝑋 𝑣 := max{𝑋 𝑣 − 1, 0} 2 if ∃𝑐 ∈ [𝐶] \ 𝐹ˆ𝑣 : |{𝑤 ∈ 𝑇 | 𝐹ˆ𝑣,𝑤 = 𝑐}| > |𝑇 |/2 then 3 𝑋 𝑣 := 𝑋 + 1 4 𝑎 𝑣 := 1 5 𝐹ˆ𝑣 := 𝑐 6 if |{𝑤 ∈ 𝑉 | 𝐹ˆ𝑣,𝑤 ≠ 𝐹ˆ𝑣 }| > 𝑛/3 then 7 𝑋 𝑣 := 𝑋 + 1 8 𝑎 𝑣 := 1 9 if 𝑇 ∋ 𝑤 = 𝑇𝑣 − 2 mod |𝑇 | ∧ 𝐹ˆ𝑣,𝑤 ≠ 𝐹ˆ𝑣 then 𝑎 𝑣 := 1 10 if 𝑣 ∈ 𝑇 and 𝐶 𝑣 ≠ 𝐹ˆ𝑣 + 1 mod 𝐶 then 11 𝑋 𝑣 := 𝑋 + 1 12 𝑎 𝑣 := 1 13 𝐹ˆ𝑣 := 𝐶 𝑣 14 else 𝐹ˆ𝑣 := 𝐹ˆ𝑣 + 1 mod 𝐶 15 𝑁 𝑣 := 𝑁 𝑣 + 1 mod 𝑛 16 𝑇𝑣 := 𝑇𝑣 + 1 mod |𝑇 | 17 foreach 𝑤 ∈ 𝑉 do 18 𝐹ˆ𝑣,𝑤 := 𝐹ˆ𝑣,𝑤 + 1 mod 𝐶 19 if 𝑠 𝑣,𝑤 = 1 then 20 send 𝐹ˆ𝑣 to 𝑤 21 𝑠 𝑣,𝑤 := 0 22 if 𝑎 𝑣 = 1 ∨ 𝐹ˆ𝑣,𝑤 ≠ 𝐹ˆ𝑣 ∨ 𝑤 = 𝑁 𝑣 mod 𝑛 ∨ 𝑇 ∋ 𝑤 = 𝑇𝑣 mod |𝑇 | then 23 send “req” to 𝑤 // unique bit string different from all 𝑐 ∈ [𝐶] 24 send 𝐹ˆ𝑣 to 𝑤 25 if received 𝑐 ∈ [𝐶] from 𝑤 then 𝐹ˆ𝑣,𝑤 := 𝐶 26 if received “req” from 𝑤 then 𝑠 𝑣,𝑤 := 1 27 𝑎 𝑣 := 0 28 if 𝑋 𝑣 = 0 then 𝐹 𝑣 := 𝐹ˆ𝑣 else 𝐹 𝑣 := ⊥
To guarantee the 𝑋 -round crusader agreement property in case too many nodes in 𝑇 are faulty, 𝑣 also memorizes which values other nodes believe the majority in 𝑇 claims. Note that in this case, |𝑇 | ∈ Ω(𝑛) implies that we can afford to wait until 𝑣 has refreshed its memorized values for all nodes in a round-robin fashion, so it is sufficient to inform other nodes whenever changing the own clock value to maintain that all views are accurate once this has been established. Thus, resetting a cooldown counter (of maximum value 𝑋 + 1) if (i) the own clock value observed as majority in 𝑇 changes or (ii) 𝑡 + 1 or more memorized values differ from the own guarantees that it is safe to output the own memorized value when the cooldown counter reaches 0; otherwise, the output is ⊥. The resulting pseudocode is given in Algorithm 5.
Early-Stabilizing Counting
21
First, we prove that the memorized values will be accurate at the latest after 𝑛 rounds, but at most 𝑓 + 𝑂 (1) rounds after 𝑇 counts in case 𝑓 < |𝑇 |/2. Lemma 6.6. Algorithm 5 satisfies the invariant that 𝐹ˆ𝑤,𝑣,𝑟 = 𝐹ˆ𝑣,𝑟 for all correct 𝑣, 𝑤 ∈ 𝑉 and rounds 𝑟 ≥ 𝑛. If 𝑓 < |𝑇 |/2 and the variables 𝐶 𝑣 count, then the invariant holds from round 𝑓 + 4. Proof. We claim that once the invariant is established for correct 𝑣, 𝑤 ∈ 𝑉 , it is maintained. To see this, observe that the only lines which change 𝐹ˆ𝑣 are Lines 5, 13, and 14. If Line 5 or Line 13 are executed by 𝑣 in round 𝑟 , 𝑎 𝑣 is set to 1 and 𝐹ˆ𝑣,𝑟 is sent to 𝑤 later in round 𝑟 , i.e., once the variable 𝐹ˆ𝑣 equals 𝐹ˆ𝑣,𝑟 . On reception of this message, 𝑤 sets 𝐹ˆ𝑤,𝑣 to 𝐹ˆ𝑣,𝑟 and does not change this variable again in round 𝑟 , i.e., 𝐹ˆ𝑤,𝑣,𝑟 = 𝐹ˆ𝑣,𝑟 . On the other hand, if 𝑣 executes Line 14 in round 𝑟 , there are two possibilities. If 𝑣 sends a message with 𝐹ˆ𝑣,𝑟 to 𝑤 in round 𝑟 , we analogously get that 𝐹ˆ𝑤,𝑣,𝑟 = 𝐹ˆ𝑣,𝑟 . If 𝑣 does not send such a message, the change to 𝐹ˆ𝑤,𝑣 in round 𝑟 is caused by Line 18. Therefore, if 𝐹ˆ𝑤,𝑣,𝑟 −1 = 𝐹ˆ𝑣,𝑟 −1 , it follows that 𝐹ˆ𝑤,𝑣,𝑟 = 𝐹ˆ𝑤,𝑣,𝑟 −1 + 1 mod 𝐶 = 𝐹ˆ𝑣,𝑟 −1 + 1 mod 𝐶 = 𝐹ˆ𝑣,𝑟 . It remains to show that this equality is established sufficiently quickly. Note that 𝑁 𝑣 counts modulo 𝑛, because the only line affecting it is Line 15. Hence, there is a round 𝑟 ≤ 𝑛 such that 𝐷 𝑣,𝑟 = 𝑤, prompting 𝑣 to send a message with 𝐹ˆ𝑣,𝑟 to 𝑤. Finally, we show the stronger bound of 𝑟 0 ∈ 𝑂 (𝑓 + 1) provided that 𝑓 < |𝑇 |/2 and the variables 𝐶𝑢 , 𝑢 ∈ 𝑇 , count. We distinguish three cases. (1) If 𝐹ˆ𝑤,𝑣,1 ≠ 𝐹ˆ𝑤,1 , 𝑤 will send “req” to 𝑣 in round 1, causing it to set 𝑠 𝑣,𝑤 to 1 and send 𝐹ˆ𝑣,2 to 𝑤 in round 2. Hence, 𝑤 sets 𝐹ˆ𝑤,𝑣,2 to 𝐹ˆ𝑣,2 . (2) If 𝐹ˆ𝑣,1 = 𝐹ˆ𝑤,1 and the previous case does not apply, then 𝐹ˆ𝑤,𝑣,1 = 𝐹ˆ𝑤,1 = 𝐹ˆ𝑣,1 . (3) Suppose that the previous cases do not apply. We claim that 𝑣 or 𝑤 will set 𝑎 𝑣 or 𝑎 𝑤 , respectively, to 1 by round 𝑓 + 3. As we have seen, this will establish the invariant by round 𝑓 + 4. To show the claim, we fix a correct node 𝑢 ∈ 𝑇 . Because 𝐹ˆ𝑣,1 ≠ 𝐹ˆ𝑤,1 , one of them must be different from 𝐶𝑢,1 . W.l.o.g., suppose that 𝐹ˆ𝑣,1 ≠ 𝐶𝑢,1 . In particular, 𝑣 ∉ 𝑇 , as otherwise Line 13 would force 𝑣 to set 𝐹ˆ𝑣,1 to 𝐶 𝑣,1 = 𝐶𝑢,1 . Consider the minimal round 𝑟 ≥ 1 such that 𝑤 = 𝑇𝑣,𝑟 mod |𝑇 | is correct. As the only instruction affection 𝑇𝑣 is counting up by one module |𝑇 | in each round, we have that 𝑟 ≤ 𝑓 + 1. In this round, 𝑣 sends “req” to 𝑤, which responds with 𝐹ˆ𝑤,𝑟 +1 in round 𝑟 + 1. As 𝑤 ∈ 𝑇 is correct, it maintains that 𝐹ˆ𝑤,𝑟 +1 = 𝐶 𝑤,𝑟 +1 , and because the 𝐴 variables count, we have that 𝐶 𝑤,𝑟 +1 = 𝐶𝑢,𝑟 +1 = 𝐶𝑢,1 + 𝑟 . Thus, either 𝑣 executed Line 5 in some round 𝑟 ′ ≤ 𝑟 + 1 (and set 𝑎 𝑣 to 1 in this round), or it executed Line 14 in rounds 𝑟 ′ ≤ 𝑟 + 1, yielding that 𝐹ˆ𝑣,𝑟 +1 = 𝐹ˆ𝑣,1 + 𝑟 mod 𝐶 ≠ 𝐶𝑢,1 + 𝑟 mod 𝐶. We conclude that in round 𝑟 + 2, 𝑣 will execute Line 9 if it did not do so before, and set 𝑎 𝑣 to 1. □ With this invariant established, it is straightforward to prove the validity property of filtering. Lemma 6.7. Algorithm 5 satisfies the validity property of (𝐶, 𝑋,𝑇 )-filtering in rounds 𝑟 ≥ 𝑓 + 𝑂 (1). Proof. The validity property of (𝐶, 𝑋,𝑇 )-filtering is trivially satisfied if 𝑓 ≥ |𝑇 |/2 or the variables 𝐶 𝑣 , 𝑣 ∈ 𝑇 , do not count. Hence, assume that 𝑓 < |𝑇 |/2 and the variables 𝐶 𝑣 count. By Lemma 6.6, Algorithm 5 then satisfies the invariant that 𝐹ˆ𝑤,𝑣,𝑟 = 𝐹ˆ𝑣,𝑟 for all correct 𝑣, 𝑤 ∈ 𝑉 and rounds 𝑟 ≥ 𝑓 +4. Moreover, each node 𝑣 ∈ 𝑇 maintains that 𝐹ˆ𝑣,𝑟 = 𝐶 𝑣,𝑟 due to Lines 13 and 14. As we assume that the majority of nodes in 𝑇 is correct and the variables 𝐶 𝑣 count, this means that any 𝑣 ∉ 𝑇 executes
22
Christoph Lenzen and Julian Loss
Line 5 in round 𝑟 ≥ 𝑓 + 4 if and only if its variable 𝐹ˆ𝑣,𝑟 does not match the count of the 𝐶 𝑣 variables. As the only other possibility is that the count matches and 𝑣 executes Line 14, it follows that all correct nodes adopt and maintain the correct count in their variables 𝐹ˆ𝑣,𝑟 by round 𝑓 + 4. Once this took place, no variable 𝑋 𝑣 can be set to 𝑋 + 1 again, implying that all correct nodes output the correct count by round 𝑓 + 𝑋 + 5 ∈ 𝑓 + 𝑂 (1). □ If 𝑓 ≥ |𝑇 |/2 ∈ Ω(𝑛), it is sufficient to achieve 𝑋 -round crusader agreement within 𝑂 (𝑛) rounds. Otherwise, we can wait until the counting routine running on 𝑇 stabilizes, after which the invariant is established within 𝑂 (𝑓 + 1) rounds. In either case, it is easy to show that the 𝑋 -round crusader agreement property is quickly established once the invariant holds, i.e., all correct nodes have correct views of other correct nodes’ 𝐹ˆ variables. Lemma 6.8. Suppose that 𝑓 ≥ |𝑇 |/2 ∈ Ω(𝑛) or the variables 𝐶 𝑣 , 𝑣 ∈ 𝑇 , count. Then Algorithm 5 satisfies the 𝑋 -round crusader agreement property of (𝐶, 𝑋,𝑇 )-filtering in rounds 𝑟 ≥ 𝑂 (𝑓 + 1). Proof. By Lemma 6.6, Algorithm 5 satisfies the invariant that 𝐹ˆ𝑤,𝑣,𝑟 = 𝐹ˆ𝑣,𝑟 for all correct 𝑣, 𝑤 ∈ 𝑉 and rounds 𝑟 ≥ 𝑛. If 𝑓 ≥ |𝑇 |/2, by the assumptions of the lemma it holds that 𝑛 ∈ 𝑂 (𝑓 ). On the other hand, if 𝑓 < |𝑇 |/2, the variables 𝐶 𝑣 count and Lemma 6.6 states that the invariant holds from round 𝑓 + 4. Either way, there is 𝑟 0 ∈ 𝑂 (𝑓 + 1) such that the invariant holds in rounds 𝑟 ≥ 𝑟 0 . Now suppose that correct node 𝑣 outputs 𝐹 𝑣,𝑟 = 𝑐 ≠ ⊥ in round 𝑟 > 𝑟 0 . Thus, it did not set 𝑋 𝑣 to 𝑋 + 1 in round 𝑟 , entailing that9 |{𝑤 ∈ 𝑉 | 𝐹ˆ𝑣,𝑤,𝑟 −1 ≠ 𝐹ˆ𝑣,𝑟 −1 }| ≤ ⌈𝑛/3⌉ − 1 = 𝑡 due to the condition in Line 6. Thus, at least 𝑛 − 2𝑡 > 𝑡 correct nodes 𝑤 satisfy that 𝐹ˆ𝑤,𝑟 −1 = 𝐹ˆ𝑣,𝑟 −1 . Therefore, any node 𝑤 with 𝐹ˆ𝑤,𝑟 −1 ≠ 𝐹ˆ𝑣,𝑟 −1 will satisfy the condition in Line 6 and set 𝑋 𝑤 to 𝑋 + 1 in round 𝑟 . As it takes at least until round 𝑟 + 𝑋 + 1 for 𝐹 𝑤 to decrease to 0, the output instruction ensures that 𝐹 𝑤,𝑟 ′ = ⊥ for all correct 𝑤 with 𝐹ˆ𝑤,𝑟 −1 ≠ 𝐹 𝑣,𝑟 −1 and rounds 𝑟 ′ ∈ [𝑟, 𝑟 + 𝑋 ]. On the other hand, any correct 𝑤 with 𝐹ˆ𝑤,𝑟 −1 = 𝐹 𝑣,𝑟 −1 will increase 𝐹ˆ𝑤 by 1 modulo 𝐶 in each round 𝑟 ′ ∈ [𝑟, 𝑟 + 𝑋 ] or set 𝑋 𝑤 to 𝑋 + 1. Again, this will ensure that in the subsequent 𝑋 rounds, 𝑤 will output ⊥. Therefore, 𝐹 𝑤,𝑟 ′ ∈ {𝐹 𝑣,𝑟 + 𝑟 ′ − 𝑟 mod 𝐶, ⊥} for all correct 𝑤 with 𝐹ˆ𝑤,𝑟 −1 = 𝐹 𝑣,𝑟 −1 . □ It remains to show that the amortized bit complexity is indeed small. Lemma 6.9. When executing Algorithm 5, correct nodes send messages of size 𝑂 (log 𝐶). If 𝑓 < |𝑇 |/2 ∈ Ω(𝑛) and the variables 𝐶 𝑣 , 𝑣 ∈ 𝑇 , count, the bit complexity is 𝑂 (𝑛(𝑓 + 1) log 𝐶) amortized over 𝑛 rounds. Proof. The bound on the message size can be readily verified from the code. If 𝑓 < |𝑇 |/2 and the variables 𝐶 𝑣 count, by Lemma 6.8, the output variables 𝐹 𝑣 , 𝑣 ∈ 𝑉 , count from round 𝑟 0 ∈ 𝑂 (𝑓 + 1). Thus, the same holds for the variables 𝐹ˆ𝑣 , 𝑣 ∈ 𝑉 , and by Lemma 6.6, we have that 𝐹ˆ𝑣,𝑤,𝑟 = 𝐹ˆ𝑣,𝑟 for correct 𝑣, 𝑤 ∈ 𝑉 . Let us check the conditions under which node 𝑣 sets 𝑎 𝑣 to 1 in such a round 𝑟 : (1) ∃𝑐 ∈ [𝐶] \ 𝐹ˆ𝑣 : |{𝑤 ∈ 𝑇 | 𝐹ˆ𝑣,𝑤 = 𝑐}| > |𝑇 |/2. As 𝑓 < |𝑇 |/2 and all variables of correct nodes agree, this cannot happen. (2) |{𝑤 ∈ 𝑉 | 𝐹ˆ𝑣,𝑤 ≠ 𝐹ˆ𝑣 }| > 𝑛/3. As 𝑓 ≤ 𝑡 < 𝑛/3 and all variables of correct nodes agree, this cannot happen. (3) 𝑇 ∋ 𝑤 = 𝑇𝑣,𝑟 − 2 mod |𝑇 | and 𝐹ˆ𝑣,𝑤 ≠ 𝐹ˆ𝑣 . As correct nodes’ variables agree, this is possible only if 𝑤 is faulty. As 𝑓 < |𝑇 |/2 ∈ Ω(𝑛) and 𝑇𝑣 counts modulo |𝑇 |, this occurs at a rate of 𝑂 (𝑓 /𝑛) amortized over 𝑛 rounds. (4) 𝑣 ∈ 𝑇 and 𝐶 𝑣 ≠ 𝐹ˆ𝑣 + 1 mod 𝐶. As the variables 𝐶 𝑣 count and match 𝐹ˆ𝑣 for correct 𝑣 ∈ 𝑇 , this cannot happen. 9 Observe that the check in Line 6 is performed before the variables 𝐹ˆ and 𝐹ˆ 𝑣 𝑣,𝑤 are updated in round 𝑟 , so that state is
identical to that of the end of round 𝑟 − 1 ≥ 𝑟 0 .
Early-Stabilizing Counting
23
Now let us sum up all messages sent by correct nodes in rounds 𝑟 > 𝑟 0 . Consider the possible causes for a correct node 𝑣 to send a message to correct node 𝑤. • 𝑎 𝑣 = 1. As we have observed, the amortized rate over 𝑛 rounds at which this happens is 𝑂 (𝑓 ) when summing over all nodes. In a round in which 𝑎 𝑣 is 1, 𝑣 sends 𝑂 (𝑛 log 𝐶) bits of communication. Overall, this contributes an amortized bit complexity of 𝑂 (𝑛𝑓 log 𝐶). • 𝐹ˆ𝑣,𝑤 ≠ 𝐹ˆ𝑣 . Since correct nodes’ variables agree, this does not occur. • 𝑤 = 𝑁 𝑣 mod 𝑛 or 𝑇 ∋ 𝑤 = 𝑇𝑣 mod |𝑇 |. Since these are two nodes only, the corresponding messages contribute a total of 𝑂 (𝑛 log 𝐶) to the bit complexity. • 𝑠 𝑣,𝑤 = 1. As 𝑠 𝑣,𝑤 is set to 0 again after the triggered message is sent, it must have set to 1 in round 𝑟 − 1. Thus, any such message can be attributed to one of the preceding causes without affecting the asymptotic amortized bit complexity. Finally, note that, trivially, correct nodes send at most 𝑛𝑓 messages to faulty nodes in each round. Summing up all terms, we arrive at the stated bound of 𝑂 (𝑛(𝑓 + 1) log 𝐶) on the amortized bit complexity. □ It is worth noting that, if 𝑓 is small, Lemma 6.9 only controls the bit complexity once the variables 𝐶 𝑣 count. Hence, we need to take into account the stabilization time of the utilized counting algorithm when amortizing the bit complexity, resulting in the following corollary. Corollary 6.10. Assume that |𝑇 | ∈ Ω(𝑛). Then Algorithm 5 solves (𝐶, 𝑋,𝑇 )-filtering with stabilization time 𝑂 (𝑓 + 1) and messages of size 𝑂 (log 𝐶). If we assume that 𝑓 < |𝑇 |/2 implies that the variables 𝐶 𝑣 start counting within 𝑘 rounds, its bit complexity amortized over 𝑘𝑛/(𝑓 + 1) rounds is 𝑂 (𝑛(𝑓 + 1) log 𝐶). Proof. Follows from Lemmas 6.7 to 6.9, noting that if the variables 𝐶 𝑣 start counting only after 𝑘 rounds, we need to amortize the resulting 𝑂 (𝑘𝑛 2 log 𝐶) bits of communication over at least 𝑘𝑛/(𝑓 + 1) rounds to not affect the asymptotic amortized bit complexity. □ We reach the following intermediate result, which meets our goals up to the additive 𝑂 (log 𝑛) overhead in stabilization time. Theorem 6.11. 𝐶-counting can be solved with stabilization time 𝑂 (𝑓 + 1 + log 𝑛) and message size 𝑂 (log 𝐶 + log2 𝑛). Moreover, the bit complexity amortized over 𝑛 log 𝑛 rounds is 𝑂 (𝑛((log 𝑛 + log 𝐶) 𝑓 + log2 𝑛)). Proof. We recursively apply Algorithm 1 using Algorithm 5 for filtering and the king consensus algorithm from Theorem 6.5, where we partition the node set as evenly as possible in each recursion step and the base case of 𝑛 = 1 is trivial. Due to the even partition in each recursive step, we can apply Corollary 6.10 and reason analogously to Corollary 5.8 to infer that the resulting algorithm solves 𝐶-counting with stabilization time 𝑂 (𝑓 + 1 + log 𝑛). The bound on message size is immediate from the fact that the recursion has depth 𝑂 (log 𝑛) and the bounds on message size from Theorem 6.5 and Corollary 6.10. It remains to bound the amortized bit complexity. To this end, consider the recursion tree, where we label each recursive instance of Algorithm 1 by the node set on which it runs. We charge each node with (bounds on) the amortized communication complexity of its filtering and king consensus instances, but not its recursive calls. We will then sum over all nodes to bound the total amortized communication complexity. Note that the leaves of the tree correspond to trivial instances on single nodes, which do not contribute to communication costs. For an inner node of the tree corresponding to an instance of Algorithm 1 on node set 𝑉 ′ with 𝑓 ′ < |𝑉 ′ |/3 faulty nodes, by the already estabilished bound on the stabilization time we have the following.
24
Christoph Lenzen and Julian Loss
• We can apply Corollary 6.10 with 𝑘 = 𝑂 (𝑓 ′ + 1 + log |𝑉 ′ |) = 𝑂 (𝑓 ′ + 1 + log 𝑛) to bound the contribution of filtering to the amortized bit complexity over 𝑛 log 𝑛 rounds by 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log |𝑉 ′ |) = 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log 𝑛). • If 𝑓 ′ < ⌊|𝑉 ′ |⌋/9, by Lemma 5.1 the variables 𝐹 𝑣𝑏 of the instance of Algorithm 1 on 𝑉 ′ start to count within 𝑂 (𝑓 ′ + 1 + log 𝑛) rounds for both 𝑏 ∈ {0, 1}. From then on, over Θ(𝑛) rounds there are only 𝑂 (𝑓 ′ ) instances of king consensus to which correct nodes input a faulty leader ℓ. Therefore, Theorem 6.5 states that the total bit complexity of king consensus instances on node set 𝑉 ′ within Θ(𝑛) rounds is 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log |𝑉 ′ |) (except for the initial call on node set 𝑉 corresponding to the root of the tree, where message size is 𝑂 (log 𝐶)). Amortizing over 𝑛 log 𝑛 rounds, the initial cost of 𝑂 (𝑛 2 (𝑓 ′ + 1 + log 𝑛)) messages before the variables 𝐹 𝑣𝑏 start counting does not increase the amortized bit complexity beyond 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log |𝑉 ′ |) = 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log 𝑛) (or 𝑂 (𝑛(𝑓 + 1) log 𝐶) for the root of the tree). Observe that if 𝑓 ′ ≥ |𝑉 ′ |/3, no stabilization is guaranteed. However, in this case the bounds on message size still apply and 𝑓 ′ = Ω(|𝑉 ′ |). Therefore, in this case the contribution of the node to the amortized bit complexity is 𝑂 (|𝑉 ′ | 2 log 𝑛) = 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log 𝑛). In summary, this bound applies uniformly to all nodes of the recursion tree. Now consider all nodes in depth 𝑑 of the recursion tree. As Algorithm 1 is always applied with 𝑉0 and 𝑉1 partitioning the node set, the union of all nodes in calls in depth 𝑑 is a subset of 𝑉 . Moreover, because each recursive call partitions as evenly as possible, |𝑉 ′ | ≤ (2/3)𝑑 𝑛. Hence, summing over all nodes in depth 𝑑, we get a contribution of 𝑂 ((𝑓 (2/3)𝑑 𝑛 + 𝑛) log 𝑛). Summing over all 𝑂 (log 𝑛) values of 𝑑 for which the tree contains nodes in depth 𝑑, we arrive at a total bit complexity amortized over 𝑛 log 𝑛 rounds of 𝑂 (𝑛((log 𝑛 + log 𝐶) 𝑓 + log2 𝑛)). □ 7
Asymptotically Optimal Stabilization Time
The additive overhead of 𝑂 (log 𝑛) in the stabilization time is owed to the recursion depth of 𝑂 (log 𝑛). Even if there are no faults, the stabilization of the counts needs to propagate from a leaf of the recursion tree to the root, costing 𝑂 (1) rounds for each level of the recursion. Hence, to reach stabilization time 𝑂 (𝑓 + 1), we need a way to stabilize within 𝑂 (1) rounds if there are no faults. We achieve this by means of a different recursive template, which has one branch ensure this property, while the other simply “recurses” on the entire node set and applies Algorithm 1. The challenge is that we cannot amortize the cost incurred by faulty leaders as in Section 6, as the single node providing the “recursively” constructed clock would control which nodes act as leaders. This is problematic if 𝑓 is small, as we then do not have the budget to cover repeated calls to king consensus with Ω(𝑛 2 ) cost. 7.1
Weak King Consensus
As our way out, we relax the king consensus task such that king agreement is only required when all nodes are correct. For our use case of 𝑓 = 0, this relaxation is uncritical. Definition 7.1 (Weak King Consensus). The Weak King Consensus problem is specified as follows. Each node 𝑣 has inputs 𝑥 𝑣 ∈ V and ℓ𝑣 ∈ 𝑉 ∪¤ {⊥}. Each node 𝑣 computes an output 𝑦 𝑣 ∈ V ∪¤ {⊥} with the following guarantees: • Validity: If there is 𝑥 ∈ V so that 𝑥 𝑣 = 𝑥 for all correct 𝑣, then 𝑦 𝑣 ∈ {𝑥, ⊥} for all correct 𝑣. • Default: If ℓ𝑣 = ⊥ for all correct 𝑣, then 𝑦 𝑣 = ⊥ for all correct 𝑣. • Weak King Agreement: If 𝑓 = 0 and there is ℓ ∈ 𝑉 so that ℓ𝑣 = ℓ for all 𝑣, then 𝑦 𝑣 = 𝑦ℓ ≠ ⊥ for all 𝑣.
Early-Stabilizing Counting
25
To obtain a cheap implementation of weak king consensus, we make use of edge expanders. An edge expander guarantees that all node sets of size at most 𝑛/2 have an 𝜀-fraction of their incident edges leave the set. Definition 7.2 (Edge Expander). The edge expansion of a graph 𝐺 = (𝑉 , 𝐸) is defined as |𝐸 ∩ (𝑆 × 𝑉 \ 𝑆)| . ℎ(𝐺) := min |𝑆 | 0<|𝑆 | ≤𝑛/2,𝑆 ⊂𝑉 Theorem 7.3 ([14]). There is a family of constant-degree graphs 𝐺𝑛 = ({1, . . . , 𝑛}, 𝐸𝑛 ) of constant expansion, i.e., ℎ(𝐺𝑛 ) ≥ 𝜀 > 0 for 𝜀 ∈ Ω(1), such that the neighbors of any given node can be computed efficiently, i.e., with log𝑂 (1) 𝑛 computational steps. Using a constant-degree expander, checking whether expander neighbors have differing values will not cause more than 𝑂 (𝑓 ) nodes to observe a difference after stabilization. On the other hand, if there are no faults, the expander ensures that the number of nodes seeing a difference in case 𝑓 = 0 is proportional to the number of nodes with a minority value. This provides proof that more communication is justified—either, because stabilization has not occurred yet or because there are many faults. This is sufficient to convince all nodes with minority value to query all nodes for their values, which then proves to them that they can safely listen to the leader and adopt the majority value it proposes. Crucially, all of this only needs to work if 𝑓 = 0; only validity must be maintained under all circumstances. Theorem 7.4. Weak king consensus can be solved in 6 rounds with messages of size 𝑂 (log |V |). If there is 𝑥 ∈ V such that 𝑥 𝑣 = 𝑥 for all correct nodes 𝑣, then the bit complexity is 𝑂 (𝑛(𝑓 + 1) log |V |). Proof. We claim that the following algorithm achieves the stated guarantees. Algorithm 6: Weak king consensus. The parameter 0 < 𝜀 ∈ Ω(1) is chosen such that graphs of expansion 𝜀 can be constructed efficiently. Input: (𝑥 𝑣 , ℓ𝑣 ) ∈ V × (𝑉 ∪¤ {⊥}) Output: 𝑦 𝑣 ∈ V ∪¤ {⊥} 1 compute {𝑣, 𝑤 } ∈ 𝐸 for a constant-degree graph (𝑉 , 𝐸) of expansion 𝜀 > 0 2 send 𝑥 𝑣 to all 𝑤 with {𝑣, 𝑤 } ∈ 𝐸 and to ℓ𝑣 // first round 3 if received 𝑥 𝑤 ≠ 𝑥 𝑣 from 𝑤 and {𝑣, 𝑤 } ∈ 𝐸 then send “alert” to all nodes // second round 4 if received 𝑘 𝑣 ≠ 0 times “alert” and 𝑤 = 𝑣 + 𝑖 mod 𝑛 for 𝑖 ∈ [0, ⌈2𝑘 𝑣 /𝜀⌉] then send “req” to 𝑤 // third round 5 if received “req” from 𝑤 then send 𝑥 𝑣 to 𝑤 // fourth round 6 if received 𝑥 𝑤 ≠ 𝑥 𝑣 from half of the nodes 𝑤 = 𝑣 + 𝑖 mod 𝑛 with 𝑖 ∈ [0, ⌈2𝑘 𝑣 /𝜀⌉] then 7 send “req” to all nodes // fifth round 8 if ℓ𝑣 ≠ 𝑣 and 𝑣 received a “req” message from node 𝑤 then send 𝑥 𝑣 to 𝑤 9 else if ℓ𝑣 = 𝑣 and 𝑣 received messages from all nodes in the first round then 10 send a value 𝑧 𝑣 most frequently received in the first round to all nodes // sixth round 11 if ℓ𝑣 = ⊥ then 𝑦 𝑣 = ⊥ 12 else if received 𝑡 + 1 values different from 𝑥 𝑣 and 𝑧 ℓ𝑣 from ℓ𝑣 then 𝑦 𝑣 := 𝑧 ℓ𝑣 13 else 𝑦 𝑣 := 𝑥 𝑣 The bounds on the number of rounds and the message size are immediate from the description of the algorithm. To bound the bit complexity if there is 𝑥 ∈ V such that 𝑥 𝑣 = 𝑥 for all correct nodes 𝑣, we control the ammount of communication in reach round. (1) As (𝑉 , 𝐸) has constant degree, correct nodes send 𝑂 (𝑛) messages.
26
Christoph Lenzen and Julian Loss
(2) As (𝑉 , 𝐸) has constant degree and 𝑥 𝑣 = 𝑥 for all correct 𝑣, 𝑂 (𝑓 ) nodes send a total of 𝑂 (𝑛𝑓 ) “alert” messages. (3) As each node receives 𝑘 𝑣 ∈ 𝑂 (𝑓 ) “alert” messages, the total number of “req” messages in this round is 𝑂 (𝑛𝑓 ). (4) As nodes only respond to “req” messages from the preceding round, 𝑂 (𝑛𝑓 ) messages are sent. (5) Going over the nodes from 1 to 𝑛, we greedily select nodes 𝑣 with 𝑘 𝑣 > 0 that in the third round do not receive a “req” message from the preceding one that was selected, but send “req” messages in the fifth round. Excepting the last such node, by construction no faulty node receives a “req” message from more than one selected node. However, each selected node must have sent Í “req” messages to at least 𝑘 𝑣 /𝜀 faulty nodes, as 𝑥 𝑣 = 𝑥 for correct nodes. Hence, Ð 𝑓 ≥ 𝑣 selected 𝑘 𝑣 /(2𝜀). On the other hand, the greedy selection ensures that the union 𝑣 selected {𝑣, . . . , 𝑣 + ⌈2𝑘 𝑣 /𝜀⌉} contains Í all nodes that send “req” messages in the fifth round. As this union has size at most 𝑂 ( 𝑣 selected 𝑘 𝑣 ), at most 𝑂 (𝑛𝑓 ) “req” messages are sent in the fifth round. (6) The number of responses to “req” messages is 𝑂 (𝑛𝑓 ). Recall that in the first round correct nodes send only 𝑂 (1) messages each. Thus, there can only be 𝑂 (1) nodes that have received messages from all nodes. Hence, nodes 𝑣 with ℓ𝑣 = 𝑣 send 𝑂 (𝑛) messages. Overall, 𝑂 (𝑛(𝑓 +1)) messages are sent in this round. Summing up over all rounds and using that messages have size 𝑂 (log |V |), the bound on the bit complexity follows. Validity: In order for 𝑣 to output 𝑦 𝑣 ∉ {𝑥 𝑣 , ⊥}, it must have received at least 𝑡 + 1 messages carrying values different from 𝑥 𝑣 in the final round. If there is 𝑥 ∈ V so that 𝑥 𝑤 = 𝑥 for all correct nodes 𝑤, then correct nodes 𝑤 with ℓ𝑤 ≠ 𝑤 only ever send messages with value 𝑥 (or “req” or “alert” messages). Thus, a node 𝑤 with ℓ𝑤 = 𝑤 that receives messages from all nodes in round 1 will not send 𝑧 ℓ𝑤 ≠ 𝑥 in the final round either, since it received a strict majority of messages with value 𝑥 in round 1. Hence, in this case it must hold that 𝑦 𝑣 ∈ {𝑥 𝑣 , ⊥}. Default: This property is immediate from the output instruction. Weak King Agreement: Suppose that 𝑓 = 0 and that there is ℓ ∈ 𝑉 such that ℓ𝑣 = ℓ for all 𝑣 ∈ 𝑉 . Then ℓ receives messages from all nodes in the first round and sends a value 𝑧 := 𝑧 ℓ to all nodes in the final round. We claim that 𝑦 𝑣 = 𝑧 for all nodes 𝑣. To see this, assume towards a contradiction that 𝑣 ∈ 𝑉 is a node with 𝑦 𝑣 ≠ 𝑧. As 𝑣 received 𝑧 from 𝑦ℓ = ℓ in the final round, it must have received 𝑥 𝑤 ≠ 𝑥 𝑣 from at most 𝑡 nodes 𝑤 in the final round. If 𝑣 sent “req” to all nodes in the second to last round, this is impossible, as 𝑥 𝑣 is the input of at most 𝑛/2 < 𝑛 − 𝑡 nodes. Thus, 𝑣 did not do so, implying that it received 𝑥 𝑣 from at least half of the nodes 𝑣 + 𝑖 mod 𝑛 with 𝑖 ∈ [0, . . . , ⌈2𝑘 𝑣 /𝜀⌉]. Denoting 𝑉𝑥 𝑣 := {𝑤 ∈ 𝑉 | 𝑥 𝑤 = 𝑥 𝑣 }, it follows that |𝑉𝑥 𝑣 | > 𝑘 𝑣 /𝜀. However, because 𝑥 𝑣 ≠ 𝑧 is not more frequent than 𝑧, |𝑉𝑥 𝑣 | ≤ 𝑛/2. Hence, at least an 𝜀-fraction of all edges of (𝑉 , 𝐸) that are incident to nodes in 𝑉𝑥 𝑣 has their other endpoint outside of 𝑉𝑥 𝑦 . As (𝑉 , 𝐸) has uniform degree, it follows that at least an 𝜀-fraction of the nodes in 𝑉𝑥 𝑣 has a neighbor in 𝑉 \ 𝑉𝑥 𝑣 . Thus, we arrive at the contradiction that at least 𝜀 |𝑉𝑥 𝑣 | ≤ 𝑘 𝑣 < 𝜀 |𝑉𝑥 𝑣 | nodes send an “alert” message to all nodes in round 2. □ 7.2
Recursion Template Ensuring 𝑂 (1)-round Stabilization if 𝑓 = 0
As our solution to weak king consensus is guaranteed to incur a cost of only 𝑂˜ (𝑛𝑓 ) after stabilization, regardless of whether the leader is correct, it is safe to use in an imbalanced recursion, see Algorithm 7. This template exploits that if there is no fault, the leader will succeed on any attempt
Early-Stabilizing Counting
27
Algorithm 7: A second recursion template for 𝐶-counting. We give the code 𝑣 ∈ 𝑉 executes in each round, where 𝐶 𝑣 is the output variable. The template is parametrized by a solutions to counting, filtering with 𝑉 as clock set, 𝑅-round king consensus, and 𝑅-round weak king consensus, where 𝑅 ∈ 𝑂 (1), all on node set 𝑉 . To highlight the similarities to Algorithm 1, we use the shorthands 𝑘 := 3𝑅 and 𝑋 := 6𝑅. Variables: for 𝑏 ∈ {0, 1}, outputs 𝐴𝑣 and 𝐹 𝑣 of counting on 𝑉 and filtering with clock set 𝑉 , modulo-𝑅 counter 𝑃 𝑣 ∈ [𝑅], cooldown counter 𝐿𝑣 ∈ [𝑅 + 1] Output: 𝐶 𝑣 ∈ [𝐶] 1 if 𝐹 𝑣 = 𝑘𝑤 mod (𝑘𝑛) then ℓ𝑣 := 𝑤 else ℓ𝑣 := ⊥ 2 initialize king consensus on universe [𝐶] ∪ {⊥} with input (𝐶 𝑣 + 𝑅 mod 𝐶, ℓ𝑣 ) 3 for 𝑟 ∈ {𝑅, . . . , 1} do 4 execute the code of round 𝑟 of king consensus on the state stored for round 𝑟 5 if 𝑟 = 𝑅 and the output of the instance is 𝑐 ∈ [𝐶] then 6 𝐶 𝑣 := 𝑐 7 else 8 store the new state in the memory block allocated for round 𝑟 + 1 9 execute the code of an instance of (𝑘𝑛, 𝑋, 𝑉 )-filtering with input 𝐴 𝑣 and output 𝐹 𝑣 10 execute the code of an instance of (𝑘𝑛)-counting on node set 𝑉 with output 𝐴 𝑣 11 𝐶 𝑣 := 𝐶 𝑣 + 1 mod 𝐶 12 if 𝑣 = 0 then 13 𝑃 𝑣 := 𝑃 𝑣 + 1 mod 𝑅 14 send 𝑃 𝑣 to all nodes 15 else if received 𝑃 0 from node 0 then 16 𝑃 𝑣 := 𝑃0 17 if ℓ𝑣 ≠ ⊥ then 𝐿𝑣 := 𝑅 ′ ′ 18 if 𝑃 𝑣 = 0 mod 𝑅 and 𝐿𝑣 = 0 then ℓ𝑣 := 0 else ℓ𝑣 := ⊥ ′ 19 initialize weak king consensus on universe [𝐶] ∪ {⊥} with input (𝐶 𝑣 + 𝑅 − 1 mod 𝐶, ℓ𝑣 ) 20 𝐿𝑣 := 𝐿𝑣 − 1 21 for 𝑟 ∈ {𝑅, . . . , 1} do 22 execute the code of round 𝑟 of weak king consensus on the state stored for round 𝑟 23 if 𝑟 = 𝑅 and the output of the instance is 𝑐 ∈ [𝐶] then 24 𝐶 𝑣 := 𝑐 25 else 26 store the new state in the memory block allocated for round 𝑟 + 1
supported by all nodes, so we can let nodes ignore weak king consensus instances if the filtered clock from the recursively constructed counter on the whole node set asks them to execute a king consensus instance (with a non-⊥ leader). In the following, denote by 𝑆𝐶 the stabilization time of the instance of (𝑘𝑛)-counting on node set 𝑉 and by 𝑆 𝐹 the stabilization time of the instance of (𝑘𝑛, 𝑋, 𝑉 )-filtering. Moreover, we use Definition 5.3 in the sense that 𝑏 = 0 corresponds to instances of weak king consensus (whose only possible leader is node 0) and 𝑏 = 1 corresponds to instances of king consensus. To prove stabilization, as in Section 5 it suffices to show that an unimpeded instance occurs. Lemma 7.5. There is an unimpeded instance of king consensus within 𝑆𝐶 + 𝑆 𝐹 + 𝑂 (𝑓 + 1) rounds.
28
Christoph Lenzen and Julian Loss
Proof. As 𝑓 ≤ 𝑡 < |𝑉 |/3, within 𝑆𝐶 + 𝑆 𝐹 rounds the variables 𝐹 𝑣 start to count. Thus, there is some round 𝑟 such that a king consensus instance running with some correct leader is initialized, and no correct node uses input ℓ𝑣 ≠ ⊥ for king consensus instances in rounds 𝑟, 𝑟 + 1, . . . , 𝑟 + 𝑅. In round 𝑟 all correct nodes 𝑣 set 𝐿𝑣 to 𝑅 before determining ℓ𝑣′ . As 𝐿𝑣 needs to decrement 𝑅 times to reach 0, which happens after ℓ𝑣′ is determined, no correct node inputs ℓ𝑣′ ≠ ⊥ in rounds 𝑟, 𝑟 + 1, . . . , 𝑟 + 𝑅. □ The above lemma handles the case that 𝑓 > 0. If 𝑓 = 0, fast stabilization is facilitated by node 0. Lemma 7.6. If 𝑓 = 0, there is an unimpeded instance of weak king consensus by round 𝑆 𝐹 + 𝑂 (1). Proof. If 𝑓 = 0, the variables 𝑃 𝑣 𝑅-count from round 1. Analogously to Lemma 5.2, for rounds 𝑟 ≥ 𝑆 𝐹 there is a virtual clock 𝐹ˆ such that 𝐹 𝑣,𝑟 ∈ {𝐹ˆ𝑟 , ⊥} and, for any 𝑋 consecutive rounds, 𝐹ˆ𝑟 +1 = 𝐹ˆ𝑟 + 1 mod (𝑘𝑛). We distinguish two cases. (1) If 𝐹ˆ𝑟 mod 𝑘 ≠ 0 in rounds 𝑟, 𝑟 + 1, . . . , 𝑟 + 3𝑅 − 2, all nodes have ℓ𝑣 = ⊥ in these rounds. Thus, by round 𝑟 + 𝑅 − 1, the counters 𝐿𝑣 all become 0. By round 𝑟 + 2𝑅 − 1, an instance of weak king consensus is initialized, and it terminates by round 𝑟 + 3𝑅 − 2. Hence, it is unimpeded. (2) Otherwise, 𝐹ˆ𝑟 mod 𝑘 ≠ 0 in rounds 𝑟 + 3𝑅 − 1, 𝑟 + 3𝑅, . . . , 𝑟 + 6𝑅 − 3, where we use that 𝑘 = 3𝑅 and 𝑋 = 6𝑅. Analogously to the first case, we conclude that an unimpeded instance of weak king consensus is initialized by round 𝑟 + 5𝑅. As 𝑅 = 𝑂 (1), this concludes the proof. □ Lemma 7.7. Algorithm 7 solves 𝐶-counting with stabilization time 𝑆𝐶 + 𝑆 𝐹 + 𝑂 (𝑓 + 1). If 𝑓 = 0, the stabilization time is 𝑆 𝐹 + 𝑂 (1). Proof. Analogously to the proof of Lemma 5.4, we can show that if an unimpeded king consensus instance is initialized in round 𝑟 , the variables 𝐶 𝑣 count from round 𝑟 + 𝑅: the king agreement property of king consensus is only used to establish that the outputs of the unimpeded instance agree, so using weak king agreement on other instances is not an issue. On the other hand, if 𝑓 = 0, then the weak king agreement and king agreement properties coincide, i.e., for 𝑓 = 0 a solution to weak king agreement is a solution to king agreement. Hence, under the constraint that 𝑓 = 0, an unimpeded instance of weak king consensus being initialized in round 𝑟 implies that the variables 𝐶 𝑣 count from round 𝑟 + 𝑅 as well. The statement of the lemma now follows by applying Lemmas 7.5 and 7.6. □ 7.3
Combining the Techniques
It remains to merge the two recursive templates so that the length of the path in the recursion tree that guarantees stabilization is reduced from 𝑂 (log 𝑛) to 𝑂 (log 𝑓 ). Theorem 1.1. There is a 𝐶-counting algorithm with stabilization time 𝑂 (𝑓 + 1), message size 𝑂 (log2 𝑛 + log 𝐶), and bit complexity of 𝑂 (𝑛(𝑓 log 𝐶 + log2 𝑛)) amortized over 𝑛 rounds. Proof. We combine our two recursive templates as follows. We alternate between (i) applying the template from Algorithm 7, where the counting algorithm on 𝑉 is given by (ii) applying the template from Algorithm 1 with 𝑉0 = {1, . . . , ⌊|𝑉 |/2⌋} and 𝑉1 = 𝑉 \𝑉0 (choosing constants appropriately), with the counting algorithms given by (i) or being trivial if only one node remains. We use the 8-round solution to king consensus given by Theorem 6.5, the 6-round solution to weak king consensus given by Theorem 7.4 (padded to 𝑅 = 8 rounds), and the filtering algorithm given in Algorithm 5. Note that Algorithm 5 is always applied with |𝑇 | ∈ Ω(|𝑉 |).
Early-Stabilizing Counting
29
Consider the recursion tree, whose nodes are labeled by the node sets 𝑉 ′ on which the respective template is applied. Observe that on inner nodes on even levels, the template from Algorithm 7 is applied, while on inner nodes on odd levels, the template from Algorithm 1 is used. Thus, the depth of the tree is 𝑂 (log 𝑛) due to the balanced split on odd levels. As we partition the nodes on odd levels, this immediately yields the bound on the message size. Concerning the stabilization time, consider the root-leaf path constructed by (i) on even levels, going to the child that is a leaf if and only if 𝑉 ′ contains no faulty nodes, and (ii) on odd levels to the child whose node set contains fewer faults. Along this path, the number of faults 𝑓 ′ in the current set is reduced by at least half for every odd step, and once it reaches zero, the path reaches a leaf on the next hop. In particular, the path maintains the invariant 𝑓 ′ < |𝑉 ′ |/3. By Theorem 5.7, Corollary 6.10, and Lemma 7.7, we get at each node on the path that the stabilization time is 𝑆 next + 𝑂 (𝑓 ′ + 1), where 𝑆 next is the stabilization time of the next node on the path. We conclude that the stabilization time of the root node, i.e., the overall algorithm, is bounded by ! 𝑂 (log ∑︁𝑓 ) − ⌊𝑑/2⌋ 𝑂 2 𝑓 + 1 = 𝑂 (𝑓 + 1). 𝑑=0
With the bound on the stabilization time established, it remains to bound the amortized bit complexity. We annotate each node of the recursion tree with a bound on its contributions that are not caused by recursive calls (amortized over 𝑛 rounds), so that summing over all nodes of the tree results in the desired bound. Since leaves do not contribute, we need to consider inner nodes only. Denote by 𝑉 ′ and 𝑓 ′ the node set corresponding to the considered inner node and number of faults in this node set, and observe that on each level of the tree, the node sets of inner nodes are disjoint. • By Theorem 7.4, weak king consensus instances incur a cost of 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log |V |) if nodes agree on the inputs 𝑥 𝑣 . If 𝑓 ′ < |𝑉 ′ |/3, this occurs within 𝑂 (𝑓 ′ + 1) rounds, during which 𝑂 (|𝑉 ′ | 2 log |V |) bits are sent. Amortizing over 𝑛 ≥ |𝑉 ′ | rounds, the contribution becomes 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log |V |) on average. If 𝑓 ′ ≥ |𝑉 ′ |/3, the message size bound from the theorem yields a bound of 𝑂 (|𝑉 ′ | 2 log |V |) = 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log |V |). • By Theorem 6.5, king consensus instances incur a cost of 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log |V |) if nodes agree on the inputs 𝑥 𝑣 and non-faulty ℓ𝑣 ∈ 𝑉 ′ ∪ {⊥}. If 𝑓 < |𝑉 ′ |/9, even on odd levels both recursive instances have few enough faults to stabilize within 𝑂 (𝑓 ′ +1) rounds. By Lemma 5.1 and Corollary 6.10, the variables 𝐹 𝑣𝑏 (or 𝐹 𝑣 on even levels) thus start counting within 𝑂 (𝑓 ′ +1) rounds. Also, we already know that the output variables start counting within 𝑂 (𝑓 ′ + 1) rounds. Hence, barring an initial 𝑂 (𝑓 ′ + 1) rounds, all instances of king consensus except for 𝑂 (𝑓 ′ ) many every |𝑉 ′ | ≤ 𝑛 rounds incur only cost 𝑂 (|𝑉 ′ |(𝑓 ′ +1) log |V |). Using the message size bound of 𝑂 (log |V |) and amortizing over 𝑛 rounds, the amortized bit complexity is bounded by 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log |V |). • Unless 𝑓 ′ = Θ(|𝑉 ′ |), we can apply Corollary 6.10 with 𝑘 = 𝑂 (𝑓 ′ + 1) to bound the amortized bit complexity of the instances of Algorithm 5 by 𝑂 (|𝑉 ′ |(𝑓 ′ + 1) log 𝑛); if 𝑓 ′ = Θ(|𝑉 ′ |), the same bound trivially follows from the message size bound. • Algorithm 7 causes additional communication of 𝑂 (|𝑉 ′ |) bits per round due to node 0 sending the modulo 𝑅 ∈ 𝑂 (1) counter 𝑃1 to all nodes in 𝑉 ′ . Summing over all inner nodes in a given depth 𝑑, using that |𝑉 ′ | falls by factor at least 3 for every 2 levels, and taking into account that the considered node sets are disjoint, we get a total contribution of 𝑂 (𝑛((2/3)𝑑/2 𝑓 + 1) (log |V | + log 𝑛) from nodes in depth 𝑑, where log |V | = 𝑂 (log 𝑛) in all cases but the consensus instances for 𝑑 = 0, where log |V | = 𝑂 (log 𝐶). Summing over all 𝑂 (log 𝑛) values of 𝑑, we arrive at an overall bit complexity of 𝑂 (𝑛(𝑓 log 𝐶 + log2 𝑛)) amortized over 𝑛 rounds. □
30
8
Christoph Lenzen and Julian Loss
Open Questions
We conclude the paper by listing a number of open questions we consider to be of interest. (1) Is the achieved bit complexity (nearly) optimal? (2) Is it possible to interleave our approach with randomized techniques to get both stabilization time 𝑂 (𝑓 + 1) deterministically and 𝑂 (1) in expectation? (3) Can the proposed or similar techniques be applied to the pulse synchronization problem to achieve early stabilization also there? (4) Cryptographic tools can enable to increase 𝑡 to ⌊(𝑛 − 1)/2⌋ and circumvent the DolevReischuk bound, e.g. by means of threshold signatures [6]. Can higher resilience or lower communication cost be achieved while maintaining early stabilization? (5) Addressing the previous question requires to reconcile the total loss of volatile state and arbitrary transient violation of the protocol assumed in the context of self-stabilization with the need to hide secret keys and signatures from the adversary. Can this be achieved under reasonable assumptions? And if yes, how should this be modeled? References [1] Ittai Abraham, T.-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication Complexity of Byzantine Agreement, Revisited. In Peter Robinson and Faith Ellen, editors, Symposium on Principles of Distributed Computing (PODC), pages 317–326. ACM, 2019. [2] B. Awerbuch and G. Varghese. Distributed Program Checking: a Paradigm for Building Self-stabilizing Distributed Protocols. In Symposium of Foundations of Computer Science (FOCS), pages 258–267, 1991. [3] Michael Ben-Or, Danny Dolev, and Ezra N. Hoch. Fast self-stabilizing byzantine tolerant digital clock synchronization. In Rida A. Bazzi and Boaz Patt-Shamir, editors, Symposium on Principles of Distributed Computing (PODC), pages 385–394. ACM, 2008. [4] P. Berman, J.A. Garay, and K.J. Perry. Towards Optimal Distributed Consensus. In Symposium on Foundations of Computer Science (FOCS), pages 410–415, 1989. [5] Benny Chor, Michael Merritt, and David B. Shmoys. Simple constant-time consensus protocols in realistic failure models. J. ACM, 36(3):591–614, July 1989. [6] Yvo Desmedt and Yair Frankel. Threshold Cryptosystems. In Gilles Brassard, editor, Advances in Cryptology (CRYPTO), volume 435, pages 307–315. Springer, 1989. [7] Danny Dolev. The Byzantine Generals Strike Again. Journal of Algorithms, 3(1):14–30, 1982. [8] Danny Dolev and Rüdiger Reischuk. Bounds on Information Exchange for Byzantine Agreement. J. ACM, 32(1):191–204, January 1985. [9] Danny Dolev, Ruediger Reischuk, and H. Raymond Strong. ’Eventual’ is Earlier than ’Immediate’. In Symposium on Foundations of Computer Science (SFCS), pages 196–203, 1982. [10] Danny Dolev, Ruediger Reischuk, and H. Raymond Strong. Early stopping in Byzantine agreement. J. ACM, 37(4):720– 741, 1990. [11] Shlomi Dolev and Jennifer L. Welch. Self-stabilizing clock synchronization in the presence of Byzantine faults. J. ACM, 51(5):780–799, September 2004. [12] Pesech Feldman and Silvio Micali. An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement. SIAM Journal on Computing, 26(4):873–933, 1997. [13] Michael J. Fischer and Nancy A. Lynch. A Lower Bound for the Time to Assure Interactive Consistency. Information Processing Letters, 14(4):183–186, 1982. [14] Ofer Gabber and Zvi Galil. Explicit Constructions of Linear Size Superconcentrators. In Symposium on Foundations of Computer Science (FOCS), pages 364–370. IEEE Computer Society, 1979. [15] Pankaj Khanchandani and Christoph Lenzen. Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision. Theory Comput. Syst., 63(2):261–305, 2019. [16] Christoph Lenzen, Matthias Függer, Markus Hofstatter, and Ulrich Schmid. Efficient Construction of Global Time in SoCs Despite Arbitrary Faults. In Euromicro Conference on Digital System Design (DSD), pages 142–151. IEEE Computer Society, 2013. [17] Christoph Lenzen and Joel Rybicki. Near-optimal self-stabilising counting and firing squads. Distributed Comput., 32(4):339–360, 2019.
Early-Stabilizing Counting
31
[18] Christoph Lenzen and Joel Rybicki. Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus. J. ACM, 66(5), August 2019. [19] Christoph Lenzen, Joel Rybicki, and Jukka Suomela. Efficient Counting with Optimal Resilience. SIAM J. Comput., 46(4):1473–1500, 2017. [20] M. Pease, R. Shostak, and L. Lamport. Reaching Agreement in the Presence of Faults. J. ACM, 27(2):228–234, April 1980.
A
Results Implicit in Prior Work
Lemma 2.3 (implicit in [17, 19]). (𝐶, 𝑋,𝑇 )-Clock Filtering can be solved with stabilization time 𝑆 = 𝑋 + 2, where each node sends an 𝑂 (log |𝐶 |)-sized message to each other node in each round. Proof. The claim that the following algorithm solves the task. Algorithm 8: (𝐶, 𝑋,𝑇 )-filtering algorithm implicit in [17, 19]. Input: 𝐶 𝑣 ∈ [𝐶] iff 𝑣 ∈ 𝑇 Variables: 𝑚 𝑣 , 𝑀𝑣 ∈ [𝐶] ∪ {⊥}, 𝑋 𝑣 ∈ [𝑋 + 1] Output: 𝐹 𝑣 ∈ [𝐶] ∪ {⊥} 1 send (𝐶 𝑣 , 𝑚 𝑣 ) to all nodes 2 if received (𝐶, ·) from the majority of nodes 𝑤 ∈ 𝑇 then 𝑚 𝑣 := 𝐶 else 𝑚 𝑣 := ⊥ 3 if received (·, 𝑚) from at least 𝑛 − 𝑡 nodes 𝑤 ∈ 𝑉 then 4 if 𝑚 = 𝑀𝑣 + 1 mod 𝐶 then 𝑋 𝑣 := max{𝑋 𝑣 − 1, 0} else 𝑋 𝑣 := 𝑋 5 𝑀𝑣 := 𝑚 6 else 𝑋 𝑣 := 𝑋 7 if 𝑋 𝑣 = 0 then 𝐹 𝑣 := 𝑀𝑣 else 𝐹 𝑣 := ⊥ The bound on message size can be readily verified from this description. Validity: If fewer than |𝑇 |/2 nodes in 𝑇 are faulty and the variables 𝐶 𝑣 𝐶-count, the variables 𝑚 𝑣 and 𝑀𝑣 count from rounds 1 and 2, respectively. Then all counters 𝑋 𝑣 count down to 0 by the end of round 𝑋 + 2, so that the outputs count from round 𝑋 + 2. 𝑋 -round Crusader Agreement: If in round 𝑟 ≥ 𝑋 + 2 correct 𝑣 outputs 𝐶 𝑣,𝑟 ∈ [𝐶], it follows that it received 𝑀𝑣,𝑟 ′ = 𝑚 𝑤,𝑟 ′ −1 = 𝐶 𝑣,𝑟 + 𝑟 ′ − 𝑟 mod 𝐶 from at least 𝑛 − 𝑡 nodes 𝑤 ∈ 𝑉 each in rounds 𝑟 ′ ∈ {𝑟 − 𝑋, 𝑟 − 𝑋 − 1, . . . , 𝑟 }. At least 𝑛 − 2𝑡 > 𝑡 of these are correct, implying that no 𝑤 receives 𝑛 − 𝑡 times another value in round 𝑟 ′ . Hence, 𝑀𝑤,𝑟 ′ ∈ {𝑀𝑣,𝑟 ′ , ⊥} for each correct 𝑤 and such 𝑟 ′ , implying that also 𝐹 𝑤,𝑟 ′ ∈ {𝑀𝑣,𝑟 ′ , ⊥} = {𝐶 𝑣,𝑟 + 𝑟 ′ − 𝑟 mod 𝐶, ⊥}, as required. □ Lemma 2.5 (implicit in [4], see also [12]). Graded agreement can be solved in 2 rounds, with each node sending an 𝑂 (log |V |)-sized message to each other node in each round. Proof. We claim that the following algorithm achieves the stated guarantees. Algorithm 9: Graded agreement algorithm implicit in [4]. Input: 𝑥 𝑣 ∈ V Output: (𝑦 𝑣 , 𝑔𝑣 ) ∈ V × {0, 1} 1 send 𝑥 𝑣 to all nodes // first communication round 2 if received 𝑥 𝑣 𝑛 − 𝑡 times then send 𝑥 𝑣 to all nodes // second communication round 3 if received 𝑥 𝑣 𝑛 − 𝑡 times then (𝑦 𝑣 , 𝑔𝑣 ) := (𝑥 𝑣 , 1) 4 else if received 𝑡 + 1 times 𝑥 ∈ V then (𝑦 𝑣 , 𝑔𝑣 ) := (𝑥, 0) // break ties arbitrarily 5 else (𝑦 𝑣 , 𝑔𝑣 ) := (𝑥 𝑣 , 0) The running time and bound on message size can be readily verified from this description. Validity: If there is 𝑥 ∈ V so that 𝑥 𝑣 = 𝑥 for all correct 𝑣, then each 𝑣 receives 𝑛 − 𝑡 times 𝑥 twice and outputs (𝑥, 1).
32
Christoph Lenzen and Julian Loss
Graded Agreement: Suppose that 𝑔𝑤 = 1 for some correct 𝑤. Hence, 𝑤 received at least 𝑛 − 2𝑡 > 𝑡 messages with 𝑦 𝑤 in the second round from correct nodes. These must have received at least 𝑛 − 2𝑡 > 𝑡 messages with 𝑦 𝑤 from correct nodes in the first round. It follows that each correct 𝑣 with 𝑥 𝑣 ≠ 𝑦 𝑤 receives more than 𝑡 values different from 𝑥 𝑣 in the first round, implying that it will not send 𝑥 𝑣 again in the second round. Therefore, each node receives more than 𝑡 times 𝑥 𝑤 and at most 𝑡 times 𝑥 for any 𝑥 ≠ 𝑥 𝑤 in the second round. We conclude that each correct 𝑣 outputs 𝑦𝑣 = 𝑦𝑤 . □ Lemma 2.7 (implicit in [4]). King Consensus can be solved in 3 rounds, where each node sends an 𝑂 (log |V |)-sized message to each other node in each round. Proof. We claim that the following algorithm achieves the stated guarantees. Algorithm 10: King consensus algorithm implicit in [4]. Input: (𝑥 𝑣 , ℓ𝑣 ) ∈ V × (𝑉 ∪¤ {⊥}) Output: 𝑦 𝑣 ∈ V ∪¤ {⊥} 1 run the protocol of Lemma 2.5 with input 𝑥 𝑣 ; denote output by (𝑧 𝑣 , 𝑔𝑣 ) 2 if ℓ𝑣 = ⊥ then 𝑦 𝑣 := ⊥ 3 else if 𝑔𝑣 = 0 and received 𝑧 ℓ𝑣 from ℓ𝑣 then 𝑦 𝑣 := 𝑧 ℓ𝑣 4 else 𝑦 𝑣 := 𝑧 𝑣
// two rounds
The running time and bound on message size can be readily verified from this description. Validity: If there is 𝑥 ∈ V so that 𝑥 𝑣 = 𝑥 for all correct 𝑣, by validity of graded agreement all correct nodes output (𝑧 𝑣 , 𝑔𝑣 ) = (𝑥, 1) from their call to graded agreement. Hence, they all output 𝑥 or ⊥, as required. Default: Immediately follows from the output instruction. King agreement: If there is correct ℓ ∈ 𝑉 so that ℓ𝑣 = ℓ for all correct 𝑣, distinguish two cases. If some correct node 𝑤 outputs (𝑧 𝑤 , 1) from the call to graded agreement, the graded agreement property ensures that each correct 𝑣 outputs (𝑧 𝑤 , 𝑔𝑣 ) from this call for some 𝑔𝑣 ∈ {0, 1}. In particular, ℓ = ℓℓ sends 𝑧 ℓ = 𝑧 𝑤 in the third round, so that each correct node outputs 𝑦 𝑣 = 𝑧 ℓ = 𝑧 𝑤 . The other case is that no correct node outputs (𝑧 𝑤 , 1) for some 𝑧 𝑤 from the call to graded agreement. In this case all nodes output 𝑧 ℓ . □