A Simple Phase-King Protocol with Predictions

A Simple Phase-King Protocol with Predictions Antonia Giannoulea1 , George Papadoulis1,2 , Nikos Leonardos1 , Aris Pagourtzis1,2 1

National Technical University of Athens 2 Archimedes/Athena RC

arXiv:2611.11370v1 [cs.DC] 8 Nov 2026

antoniagian5@gmail.com, geopapadoulis@gmail.com, nikos.leonardos@gmail.com, pagour@cs.ntua.gr

Abstract Inspired by recent work (Ben-David, Dzulfikar, Ellen, and Gilbert, Byzantine Agreement with Predictions, PODC 2025) we study synchronous binary Byzantine Agreement in the learning-augmented setting, where each process receives predictions about which processes are honest or Byzantine. We present a deterministic Phase King protocol for the anauthenticated setting, combining early stopping with a specifically designed prediction-aware king selection procedure. For at most t < n/3 Byzantine processes, the protocol handles arbi
trarily many prediction errors, improving upon the O n3/2 bound of Ben-David et al., and terminates within O (P ) communication rounds, where P = 1 + min{B/n, f }, B is the total number of incorrect prediction bits held by honest number of
processes, and f is the actual
Byzantine processes. Our protocol uses O n2 P messages and O n2 P log n bits, avoiding the initial cubic bit cost of exchanging complete prediction vectors. In comparison to very recent independent work (Dufay, Dzulfikar, and Gilbert, Predictions Can Only Help! Communication Efficient Byzantine Agreement with Predictions, DISC 2026), which achieves the same error tolerance and round complexity but better communication bounds, our construction provides a much simpler Phase King approach that completely avoids involved preprocessing constructions, rendering it more practical, especially for achieving agreement in time-evolving networks. We believe that the novel prediction-aware king selection technique of our scheme is of independent interest and can find further applications in learning-augmented distributed consensus. Keywords: Byzantine agreement · Algorithms with predictions · Phase King · Round complexity · Communication complexity

1

Introduction

Byzantine Agreement is a fundamental problem in distributed computing. A set of processes must agree on a common value, even when some processes behave arbitrarily. The problem was introduced by Pease, Shostak, and Lamport [26]. Any deterministic protocol requires t + 1 rounds in the worst case, and early-stopping protocols, whose round complexity depends on the actual number f of Byzantine processes, require min{f + 2, t + 1} rounds [12]. Classical protocols provide correctness without knowing which processes are Byzantine. In practice, however, processes may have additional information about the behavior of other participants. This raises a natural question: Can such information help processes reach agreement faster? This information is introduced as predictions. The idea behind prediction-based algorithms is the use of an external tool, likely based on AI or machine learning technique, to provide some predictive information. These data are based on historical or other external data independently of the algorithm in question. In our setting, these are insights into the behavior of participating processes and predict those that may be faulty. Being able to correctly identify faulty processes in the protocol would enable faster agreement and termination. However, predictions may have errors. Therefore, when designing such algorithms, we must guarantee that even when predictions are inaccurate, the protocol should still be able to reach agreement with the same asymptotic round complexity as a protocol that does not rely on predictions. The notion of predictions being used for solving Byzantine Agreement was introduced by Ben-David, Dzulfikar, Ellen, and Gilbert in [3]. In their model, each process receives a prediction vector indicating which processes are expected to be honest or Byzantine. These vectors may differ between processes and may contain errors. Their results show that, while predictions do not improve communication complexity, which remains bounded below by Ω(n + t2 ) messages, they can significantly reduce round complexity to O (1 + min{B/n, f }), where B denotes the total number of incorrect prediction bits held by honest processes. This means that accurate predictions improve the round complexity, while inaccurate ones do not worsen it beyond the O (f + 1) rounds that can be achieved without predictions. They also show a lower bound of Ω(1 + min{B/n, f }) rounds for deterministic protocols with classification predictions, making their result tight.
In their unauthenticated construction, this bound is guaranteed only for B = O n3/2 . Extending this guarantee to a quadratic number of prediction errors was left as an open question. Our contribution. We give a specifically designed Phase King protocol that solves synchronous binary Byzantine Agreement with predictions with at most t < n/3 Byzantine processes, terminates within O (1 + min{B/n, f }) communication rounds, and works for any number of prediction errors, i.e. for any B ≤ n2 . Our construction combines the majority-based classification of Ben-David et al. [3], which yields a total of k = O (B/n) misclassified processes, with a new king-selection procedure. This procedure takes advantage of the classification to select a common honest king within the first k+1 executions. We integrate this procedure into Phase King by including both a predetermined king and a prediction-based king in each iteration, with graded consensus supporting agreement and early termination. These two king steps result in termination
in O (P ) communication rounds,
where P = 1 + min{B/n, f }. Honest processes send O n2 P messages and O n3 + n2 P log n bits in total. We further reduce communication by exchanging only a subset of each process’s prediction vector, whose size depends on the prediction errors, rather than the complete vector. Since processes do not know the exact value of B, this approach is based on the
guess-and-double strategy of [3]. The resulting protocol retains the O (P ) round and
O n2 P message bounds
while using O n2 P log n bits, eliminating the initial cost of O n3 bits of full classification. The protocol and its analysis are presented in Appendix A. In independent and concurrent work, Dufay, Dzulfikar, and Gilbert [14] achieve stronger 1

communication bounds using extractor-based groupings derived from expander graphs. Our protocol achieves the same round and error-tolerance bounds through a specifically designed modification of Phase King, without using expander graphs or any other involved constructions. Therefore, despite its higher communication cost, it shows that prediction-aware agreement is possible without relying on heavy preprocessing thus providing a practical solution, especially meaningful in cases of time-evolving networks where a repeated use of the protocol with varying participant sets may occur.

2

Related Work

The Classical Byzantine Agreement requires n > 3t in the unautheticated synchronous setting ([26, 20, 4]). Deterministic protocols require t + 1 rounds and Ω(nt) messages in the worst case ([17, 11]). One way to bypass these lower bounds is through early-stopping protocols, which adapt their termination time to the actual number of
Byzantine faults f . These protocols achieve termination in min{f + 2, t + 1} rounds and O n2 bit complexity [12, 5, 1, 25, 9, 16]. Our work also relates to algorithms with predictions, which leverage imperfect information to improve performance while maintaining worst-case guarantees [24]. Applications range from online algorithms [27, 22, 2] to distributed graph problems [6] and contention resolution [18]. Unlike our work, these studies do not consider Byzantine failures. Another related line of research concerns failure detectors, introduced by Chandra and Toueg [7] for crash failures and extended to Byzantine failures by Malkhi and Reiter [23]. Failure detectors provide processes with information about potentially faulty participants during protocol execution, allowing them to suspect or eventually identify processes exhibiting faulty behavior ([13, 19]. Ben-David et al. [3] introduced synchronous Byzantine agreement with classification predictions in authenticated and unauthenticated settings. Each process receives an additional binary vector that includes predictions for which processes are honest or Byzantine. Processes exchange these predictions and reconcile them into classification vectors with a bounded number of misclassified processes. Let B denote the total number of incorrect prediction bits held by honest processes. Their protocols
achieve asymptotically optimal O (min{(B/n) + 1, f }) round complexity when B = O n3/2 . They also prove an Ω(n + t2 ) message lower bound for deterministic Byzantine agreement with predictions, even in executions where all predictions are correct. In comparison to their work we achieve the same round complexity while tolerating any number of prediction errors, i.e. our protocol works for any B ≤ n2 ; however we deal only with the unauthenticated case. Dallot et al. [10] investigate a complementary role for predictions in Byzantine agreement: improving fault resilience rather than reducing execution cost. They characterize trade-offs between the number of faults tolerated when predictions are correct and the guarantees retained when predictions are arbitrarily inaccurate, in both authenticated and unauthenticated settings. They also study how resilience degrades as prediction errors increase. Our work instead maintains resilience t < n/3 for arbitrary predictions and uses prediction accuracy to improve round and communication complexity. In independent and concurrent work, Dufay, Dzulfikar, and Gilbert [14] developed protocols that achieve optimal O (P ) round complexity for arbitrary prediction errors, where P = 1 + min{B/n, f }. Their unauthenticated construction combines extractor-based grouping with group leader election to form committees sharing
a sufficiently large honest core. This achieves optimal resilience t < n/3 and O n2 log n log P bit complexity without exchanging complete prediction vectors. Their extractor, taken from [15], is the incidence graph of a regular Ramanujan graph, for which they rely on the deterministic polynomial-time construction of Cohen [8]. Instantiating their protocol therefore involves constructing this graph, mapping processes to overlapping groups, and integrating these groups into the agreement protocol. Al-

2

though this construction is of theoretical interest, its practicality is limited, especially in cases of time-evolving networks that would require repeated use of the procedure. Our approach retains the familiar Phase King structure, using broadcasts, prefix exchanges, and local updates to ordered lists, achieving the same error tolerance and round complexity bounds, while avoiding any graph construction or other involved preprocessing. Our contribution thus offers a simpler route to prediction-aware agreement, trading the higher by O (P/ log P ) bit complexity for a fast king selection procedure that directly exploits advice from predictions. This work is thus more applicable to practical settings, especially in dynamic situations where the set of players may vary from epoch to epoch.

3

Preliminaries

Table 1 (see Appendix B) summarizes the notation which will be used throughout the paper. However each symbol is also introduced when first used.

3.1

Model

We consider a protocol in the permissioned setting consisting of n processes p1 , . . . , pn , identified by their indices; i.e., i is the ID of process pi . In the rest of the paper we will use i and pi interchangeably. Up to t < n/3 processes may be Byzantine. We denote by f ≤ t the actual number of Byzantine processes, H the set of honest processes and F the set of the Byzantine processes. We consider a synchronous network. Every process can send a message to every other process directly, and messages between honest processes arrive within the communication round. The receiver can identify the sender through the incoming channel. We use Broadcast(msg) to denote sending msg to all processes and Receive() to denote the messages received during the current round. We count point-to-point messages; therefore, one broadcast by one process consists of O (n) messages. We consider binary Byzantine Agreement, with input and output domain {0, 1}. Each process pi starts with an input xi ∈ {0, 1}. Each process pi also receives a prediction vector ⃗ai ∈ {0, 1}n as input, where ai [j] = 0 denotes a prediction that process pj is Byzantine and ai [j] = 1 denotes a prediction that process pj is honest. We underline that each process may receive different predictions. We denote by B the total number of incorrect prediction bits held by honest processes. Let type(pj ) ∈ {0, 1} denote the actual type of process pj , where 0 means Byzantine and 1 honest. Then n XX B= 1[ai [j] ̸= type(pj )] pi ∈H j=1

3.2

Byzantine Agreement

The problem of Byzantine Agreement is defined as follows: each process pi has input a value xi and produces an output yi satisfying: • Validity: If every honest process has the same input v, then every honest process outputs v. • Agreement: All honest processes output the same value. • Termination: Eventually every honest process terminates and outputs a value. The round complexity of a Byzantine Agreement protocol is the number of rounds it takes for all honest processes to terminate, while the message/bit complexity is the total number of messages/bits sent by honest processes during the execution of the protocol. 3

We will also use a weaker version of the problem called graded-consensus. In this version, each process pi has input a value xi and produces an output (yi , gi ) ∈ {0, 1} × {0, 1} satisfying Termination and: • Validity: If every honest process has the same input v, then every honest process outputs (v, 1). • Graded Agreement: If an honest process outputs a value v with grade 1, i.e. (v, 1), then all honest processes should output (v, ∗). We instantiate graded-consensus with the binary weak validator of [21] , interpreting its output strong i as grade gi . For t < n/3, [21] establish validity and graded agreement and each invocation terminates after two communication rounds, during which each honest process sends at most 2n bits.

4

Classification and King Selection

This section presents two components of our Byzantine Agreement protocol (Algorithm 3 Section 5). Classification (Algorithm 1) aggregates prediction vectors using majority votes. Kingselection (Algorithm 2) uses the resulting classifications to exchange and update proposals in search of a common honest king.

4.1

Classification Algorithm

The initial prediction vectors of honest processes may differ. Algorithm 1 reconciles these predictions by having every process broadcasts its prediction vector and computes each classification bit using a majority vote. This procedure limits the number of inconsistent classifications among honest processes, as formalized by the lemma below. Algorithm 1 Classification Algorithm (code for process pi ) 1: procedure Classify(⃗ ai ) ▷ prediction vector ⃗ai ∈ {0, 1}n 2: Broadcast(⃗ai ) 3: Ri ← Receive() ▷ Ri : set of prediction vectors 4: for j = 1 to n do ▷ #predictions classifying pj as honest 5: honestyj ← |{a ∈ Ri : a[j] = 1}|  n+1  6: if honestyj ≥ 2 then ci [j] ← 1 7: else ci [j] ← 0 8: return ⃗ci ▷ classification vector ⃗ci ∈ {0, 1}n Definition 4.1 (Misclassified Process). A process pj is misclassified if there exists an honest process pi ∈ H such that ci [j] ̸= type(pj ). We denote by k the total number of misclassified processes. Lemma 4.2 ([3]). If f < ϵn for some constant 0 < ϵ < 1/2, then k = O (B/n). Definition 4.3 (Common Process). A process pj is common if all honest processes assign the same classification to pj , i.e., ∀pi , pi′ ∈ H, ci [j] = ci′ [j]. A process pj ∈ H is a common honest process if every honest process classifies it as honest . For each process pi , let Hi be the set of ids that pi classifies as honest after executing Algorithm 1. Formally, Hi = {j ∈ {1, . . . , n} | ci [j] = 1}.

4

4.2

Classification-based King Selection

Algorithm 2 describes the king-selection procedure executed by each process at every Phase King round. Its goal is to ensure that, in some round, all honest processes select the same honest king. We start by an informal discussion of the most important properties of the algorithm and we will then proceed to its formal analysis in Subsection 4.3. Honest processes search for such a king by considering ids they have classified as honest in increasing order. Each process initially proposes the least id in its list of honest ids and once it has proposed an id in a certain round, it never decreases its proposal in consequent rounds. This monotonicity allows a process to discard candidates once it learns that another honest process has proposed a larger id, since those candidates can no longer be proposed by all honest processes. The first rule (line 12) uses a threshold of t + 1 votes to obtain this evidence. A process counts all votes for ids in its candidate list, and selects the largest id j such that the sum of votes for candidates with an id larger or equal to j is at least t + 1. Since at most t votes come from faulty processes, this threshold guarantees that at least one honest process has already proposed a candidate with an id larger or equal to j. Therefore, moving to candidate with id j safely skips smaller ids. However, this rule alone does not guarantee progress. All honest processes could remain at the same proposal indefinitely. The second rule (line 15) breaks such a stalemate. A process advances its next proposal beyond its selected king whenever it has cumulatively received at least 2t + 1 votes for that king or for processes with larger ids, counting for this step votes for all processes regardless of their classification. This ensures that the minimum honest proposal will strictly increase, since every process whose proposed id is the minimum among honest processes receives at least n − t ≥ 2t + 1 votes for this or larger ids. Since progress is guaranteed, it remains to show that no honest process advances beyond the common honest id j ∗ unless all honest processes select it as king in that same round. Consider the first round in which an honest process advances its next proposal beyond j ∗ . In this round, no honest process yet proposes an id larger than j ∗ , so the 2t + 1 threshold must include votes from at least t+1 honest processes proposing j ∗ itself (see Fig. 1 for an illustration). These votes ensure that j ∗ satisfies the first rule in the computation of every honest process. Moreover, no larger candidate can satisfy that rule, since only faulty processes can propose larger ids. Thus, all honest processes select j ∗ as king in that round. only Byzantine proposals (at most t votes)

all honest proposals (proposed ids ≤ j ∗ )

sender

pn ≥ t + 1 honest votes for j ∗

honest vote Byzantine vote

.. .

Round r∗ : every honest pj selects j ∗

p2 p1 1

2

···

n

j∗

proposed id

≥ 2t + 1 votes for ids ≥ j ∗

Figure 1: Illustration of round r∗ in which an honest process advances beyond j ∗ : there are no honestly proposed ids larger than j ∗ , therefore at least t + 1 honest processes have proposed j ∗ in this round. 5

Algorithm 2 King Proposal and Selection (code for process pi ) 1: Input: ordered leader vector Li , current position posi ∈ {1, . . . , |Li |} 2: Output: selected king ID king ∈ {1, . . . , n}, updated position pos′i 3: procedure Propose(Li , posi ) 4: Broadcast(Li [posi ]) 5: votes ← Receive() ▷ votes[u] = #votes for process u ′ 6: cnt ← 0, king ← Li [posi ], posi ← posi 7: for j ← n down to king do 8: if j ∈ Li then 9: cnt ← cnt + votes[j] 10: if cnt ≥ t + 1 then 11: king ← j ▷ j ∈ Li ′ 12: posi ← ℓ such that Li [ℓ] = king 13: break 14: if sum(votes[king..n]) ≥ 2t + 1 ∧ pos′i < |Li | then 15: pos′i ← pos′i + 1 ▷ min{ℓ : Li [ℓ] > king} 16:

return (king, pos′i )

4.3

Analysis

Let n be the number of processes, up to t < n/3 of which may be Byzantine. Let M be the set of ids misclassified by at least one honest process. Thus |M| = k. Throughout this analysis, every honest process executes Propose once in every round, using its fixed list Li . For every r ≥ 1, its invocation in round r + 1 uses the updated position returned by its invocation in round r. Each process counts at most one valid proposed id per sender, including its own proposal. Honest proposals are counted by every honest process and at most t counted votes at any recipient are Byzantine. The loop that selects a king scans ids downwards from n to the process’s current proposal. Let qi (r) = Li [posi (r)] be the proposal of pi in round r (i.e the value of king in Line 6 of Algorithm 2), and Vir (j) be the number of votes for id j received by pi in round r (i.e. the value b r (s) by votes in Algorithm 2). Define the suffix count Uir (s) and the candidate suffix count U i Uir (s) =

n X

Vir (j),

bir (s) = U

j=s

n X

Vir (j).

j=s j∈Li

Note that the suffix count corresponds to sum(votes[king..n]), while the candidate suffix count corresponds to the value of cnt in Algorithm 2. Let si (r) be the king selected by pi during round r, i.e. coincides with the value of king in Line 16 of Algorithm 2. It is the largest id not smaller than qi (r) whose candidate suffix count is at least t + 1. If no such id exists, si (r) = qi (r). More formally, let bir (s) ≥ t + 1}. Ai (r) = {s ∈ {qi (r), . . . , n} : U Then

( max Ai (r), if Ai (r) ̸= ∅, (Line 11 of Algorithm 2) si (r) = qi (r), otherwise (Line 6 of Algorithm 2).

The next proposal is determined by the updated position of Li . The first case of the following

6

update rule is called the advancing branch:   if Uir (si (r)) ≥ 2t + 1 posi (r) + 1, posi (r + 1) = and si (r) < max(Li ),   the unique position of si (r) in Li , otherwise. Now we are ready to prove the following lemmas. Lemma 4.4. If k < n − t, then there exists at least one common honest process. Proof. There are at least n − t honest processes. If none were common honest, then every honest process would be misclassified by at least one honest process and therefore belong to M. This implies |M| ≥ n − t > k, contradicting |M| = k. In all the following lemmas, we consider the case where k < n − t (if not, agreement will be reached by the predetermined kings). Let j ∗ denote the smallest id of a common honest process. Lemma 4.5 (Density). There are at most k ids smaller than j ∗ that are classified as honest by at least one honest process. More formally, let D be the set of these ids     [ D = j < j∗ : j ∈ Hi .   pi ∈H

Then |D| ≤ k. Proof. Let j ∈ Hi for some honest pi . If j ∈ / M, then pj ∈ H and every honest process classifies it as honest. Thus, j is a common honest id. Therefore, each element of D is common honest or misclassified. By the minimality of j ∗ , D contains no common honest process, since all its elements are smaller than j ∗ . Therefore D ⊆ M and |D| ≤ |M| = k. Lemma 4.6 (Monotonicity). For every honest pi and every round r, qi (r + 1) ≥ si (r) ≥ qi (r). Proof. Selection either keeps qi (r) or chooses a larger id, so si (r) ≥ qi (r). By definition qi (r+1) = Li [posi (r + 1)]. The updated position either stays at the selected king or advances to a later entry of the increasing list Li , so qi (r + 1) ≥ si (r). Lemma 4.7 (Progress). Let mr = minpi ∈H qi (r) be the minimum honest proposed id in round r. If mr < j ∗ , then mr+1 > mr . Proof. Fix a round r with mr < j ∗ , and consider any honest process pi . If qi (r) > mr , Theorem 4.6 gives qi (r + 1) ≥ qi (r) > mr . Otherwise, qi (r) = mr . By Theorem 4.6 si (r) ≥ mr . If si (r) > mr , then qi (r + 1) ≥ si (r) > mr . Finally, suppose si (r) = mr . Since mr is the minimum honest proposed id, then every honest process proposes an id ID ≥ mr . Hence Uir (mr ) ≥ n − t and n − t ≥ 2t + 1 since n > 3t. Both conditions of the advancing branch hold: Uir (mr ) ≥ 2t + 1 and si (r) = mr < j ∗ ≤ max(Li ). Hence posi (r + 1) = pos(r) + 1. It follows that qi (r + 1) > mr . Therefore, qi (r + 1) > mr for every honest process pi , and hence mr+1 = minpi ∈H qi (r + 1) > mr .

7

Definition 4.8 (Crossing round). A round r is a crossing round if qi (r + 1) > j ∗ for some honest process pi . The first crossing round is the smallest such round, if one exists. Corollary 4.9. Either a crossing round exists and the first crossing round is at most k + 1, or there is a round r ≤ k + 1 in which every honest process proposes j ∗ : qi (r) = j ∗

for every honest pi .

Proof. If the first crossing round is at most k + 1, the first alternative holds. Otherwise, the proposed id of each honest proposal is initially at most j ∗ . Since no crossing occurs within the first k + 1 rounds, every honest proposal remains at most j ∗ throughout these rounds. Whenever mr < j ∗ , there is an honest process pi with mr = qi (r) ∈ Hi . Thus mr ∈ D. By Lemma 4.5, mr can therefore take at most k distinct values below j ∗ . By Lemma 4.7, it strictly increases whenever it is below j ∗ . Therefore, it must equal j ∗ in some round r ≤ k + 1. In that round, every honest proposal is at least the minimum j ∗ and at most j ∗ . Hence qi (r) = j ∗ for every honest pi . Lemma 4.10 (Convergence). If a crossing round exists, let r∗ be the first crossing round. Then every honest process selects j ∗ as king in round r∗ : si (r∗ ) = j ∗

for every honest pi .

Proof. By the definition of a crossing round, there exists an honest process pi with qi (r∗ + 1) > j ∗ . Since this is the first crossing round, then qj (r∗ ) ≤ j ∗ for every honest pj . Therefore, all votes for ids greater than j ∗ in round r∗ originate from Byzantine processes. This means that b r∗ (s) ≤ U r∗ (s) ≤ t, and thus no id s > j ∗ belongs to Aj (r∗ ). If Aj (r∗ ) ̸= ∅, ∀pj ∈ H, s > j ∗ : U j j then sj (r∗ ) = max Aj (r∗ ) ≤ j ∗ . If Aj (r∗ ) = ∅, then sj (r∗ ) = qj (r∗ ) ≤ j ∗ . Thus, sj (r∗ ) ≤ j ∗ for every honest pj . Therefore, for the witnessing process pi , the update rule must take the advancing branch. Otherwise, it would give qi (r∗ + 1) = si (r∗ ) ≤ j ∗ , contradicting qi (r∗ + 1) > j ∗ . Consequently, ∗ the advancing condition holds, and in particular Uir (si (r∗ )) ≥ 2t + 1. If si (r∗ ) < j ∗ , then, since j ∗ ∈ Li , the first entry of Li larger than si (r∗ ) is at most j ∗ . The advancing branch would therefore give qi (r∗ + 1) ≤ j ∗ , a contradiction. Since si (r∗ ) ≤ j ∗ was established above, we conclude that si (r∗ ) = j ∗ . Substituting into the threshold bound gives ∗

Uir (j ∗ ) ≥ 2t + 1. At most t of these votes originate from Byzantine processes, so at least t + 1 originate from honest processes. Since no honest process proposed an id greater than j ∗ , all these honest votes are for j ∗ itself. Since j ∗ ∈ Hj , ∀pj ∈ H :

bjr∗ (j ∗ ) ≥ t + 1. U

b r∗ (j ∗ ) ≥ t + 1, we have j ∗ ∈ Aj (r∗ ). Together with the earlier Since qj (r∗ ) ≤ j ∗ and U j exclusion of larger ids, this implies max Aj (r∗ ) = j ∗ . Hence sj (r∗ ) = j ∗ for every honest pj . Theorem 4.11. If k < n − t, then among the first k + 1 executions of Algorithm 2, there is one in which all honest processes select the same honest king. Proof. By Lemma 4.4, a common honest process j ∗ exists. By Corollary 4.9, either the first crossing round is at most k + 1, or all honest processes propose j ∗ in some round r ≤ k + 1. In the first case, Lemma 4.10 ensures that all honest processes select j ∗ in the crossing round. In the second case, let r be a round in which qi (r) = j ∗ for every honest pi . Every honest 8

b r (j ∗ ) ≥ n − t ≥ t + 1. recipient receives at least n − t votes for j ∗ . Since j ∗ ∈ Hi , we have U i ∗ Hence j = qi (r) ∈ Ai (r). b r (s) ≤ t for All votes for ids greater than j ∗ originate from Byzantine processes. Therefore, U i ∗ ∗ every s > j , so no such s belongs to Ai (r). Consequently, max Ai (r) = j , and thus si (r) = j ∗ for every honest pi . Since j ∗ is honest, the theorem follows.

5

A protocol for Byzantine Agreement with Predictions

The goal of the protocol is that every honest process decide on the same value and terminate. We will say that a process ‘records a decision’ to express that the process has reached a decision that will never change afterwards, and we will say that a process ‘returns’ to express that the process terminates. The protocol combines two ways of finding a common honest king: one guarantees progress regardless of prediction quality, while the other exploits accurate predictions to reach agreement sooner. To this end, each Phase King round r contains two king selection steps. The first uses the predetermined process pr as king, which guarantees a common honest king within the first f + 1 rounds regardless of prediction quality. The second uses the king returned by Propose (Algorithm 2), which guarantees a common honest king within the first k + 1 rounds by Theorem 4.11. Each king selection is followed by a graded-consensus execution. This allows to preserve agreement once it has been reached, without being affected by the next king selection step. Thus, the protocol benefits from whichever king-selection method provides a common honest king first. To detect when it is safe to decide, each round ends with an additional graded-consensus execution. A process that obtains a value with grade 1 records the returned value as its decision (Line 16 of Algorithm 3). It then participates in one more round, allowing the remaining honest processes to record the same decision, before terminating. As we show below, all honest processes have recorded the same decision by the time any honest process returns. Algorithm 3 Byzantine Agreement (code for process pi ) 1: procedure ba-with-predictions(xi , ⃗ ai ) 2: ⃗ci ← classify(⃗ai ), Hi ← {j : ci [j] = 1}, Li ← sort(Hi ) 3: if Li = ∅ then Li ← [i] 4: posi ← 1, vi ← xi , decidedi ← false 5: for r = 1 to t + 1 do 6: (vi , gi ) ← graded-consensus(vi ) 7: Broadcast(vi ) 8: if gi = 0 then vi ← vr ▷ value received from pr (king) 9: (vi , gi ) ← graded-consensus(vi ) 10: (kingi , posi ) ← Propose(Li , posi ) 11: Broadcast(vi ) 12: if gi = 0 then vi ← vkingi ▷ value received from pking 13: 14: 15: 16: 17: 18:

(vi , gi ) ← graded-consensus(vi ) if decidedi then return decisioni if gi = 1 then decisioni ← vi decidedi ← true return decisioni

▷ record decision vi

9

In all the following lemmas we consider the case where t < n/3. In addition, in the following analysis, a round denotes one iteration of the main loop of Algorithm 3. Each iteration contains three instances of graded-consensus, two value broadcasts, and one invocation of Propose. Since each subprotocol takes a constant number of synchronous communication rounds, each iteration takes O (1) communication rounds. Thus, bounds on loop iterations yield the same asymptotic bounds on communication rounds. Lemma 5.1 (Preservation of a common value). Suppose all honest processes participate in round r and hold the same value v before some graded-consensus instance of round r. Then that instance and every later graded-consensus instance in round r return (v, 1) at every honest process, and all honest processes finish the round holding v. Proof. By the validity of graded consensus, in the first instance of graded-consensus all honest processes return (v, 1). Thus no honest process adopts the predetermined king’s value. So, in the second instance all honest processes start with the same input v and again from validity return (v, 1). No honest process adopts the proposed king’s value, so the final instance again receives only v from honest processes and returns (v, 1). Lemma 5.2 (Validity). If every honest process starts with input v, then every honest process returns v. Proof. By Lemma 5.1 all honest processes in the final graded consensus in the first round return (v, 1). Thus they all record decision v. If t = 0, the loop ends and they all return v. Otherwise, all honest processes participate in the second round, preserve v and since decided i = true for every pi ∈ H they return their stored decision v. Definition 5.3 (Common honest king). A round r has a common honest king if either pr is honest, or every honest process’s invocation of Propose in that round returns the same honest id. Lemma 5.4 (Common Honest King Agreement). If a round has a common honest king, then all honest processes have the same value at the end of that round. In particular, there exists a value v such that the final graded-consensus instance returns (v, 1) at every honest process. Proof. Let r be a round with a common honest king, and choose a king step in which all honest processes use the same honest king. Consider the graded-consensus instance immediately preceding that step: the first instance for the predetermined king (Line 6), or the second instance for the proposed king (Line 9). If some honest process returns (v, 1) for some value v from this instance, then the gradedagreement property ensures that every honest process returns (v, ∗), including the honest king. Processes with grade 1 retain v, while those with grade 0 adopt the honest king’s value, which is also v. Otherwise all honest processes have grade 0 and adopt the same value sent by the honest king. Thus all honest processes hold one common value after the king’s value adoption step. By Lemma 5.1, every remaining graded-consensus instance of round r returns (v, 1) at every honest process, and all honest processes finish the round having decided on v. Lemma 5.5 (Decision Propagation). If an honest process records a decision v at round r, then all honest processes hold v at the end of that round. Also, if r < t + 1 then by the end of round r + 1 all honest processes have recorded v. Proof. A decision is recorded only after the final graded consensus returns grade 1. By the graded-agreement property if an honest process returns (v, 1) then every honest process returns (v, ∗). Therefore, if r < t + 1 then all honest processes start round r + 1 with the same value v, so by Lemma 5.1 every honest process that has not yet recorded a decision records v in round r + 1. If r = t + 1 then all honest processes end with value v. 10

Lemma 5.6 (Termination). Every honest decides and terminates by the end of round R = min{t + 1, f + 2, k + 2}. Proof. We establish two independent upper bounds on termination. • Predetermined selection: Let h be the first iteration whose predetermined king ph is honest. Among the first f + 1 ids at least one is honest, so h ≤ f + 1 ≤ t + 1. If some honest process records a decision in a round r < h, then by Lemma 5.5, every honest process has recorded that decision by round r +1. Thus, all honest processes return by round min{r + 2, t + 1} ≤ min{h + 1, t + 1}. Otherwise, no honest process has recorded a decision before round h, so all honest processes participate in that round. In round h, by Lemma 5.4 the final graded-consensus returns grade 1 in every honest process, so every honest process records a decision. If h ≤ t then in round h + 1 ≤ min{f + 2, t + 1} every honest process terminates. If h = t + 1, every honest process returns after the loop. • Selection by proposals: For the prediction bound, it suffices to consider k < t: if k ≥ t, then f ≤ t ≤ k, so the predetermined-selection bound suffices. Since k < t < n − t, the classification requirement of Theorem 4.11 is satisfied. There is therefore a common honest process whose id appears in every honest process’s leader list. If some honest process records a decision in a round r ≤ k, then by Lemma 5.5, every honest process has recorded that decision by round r + 1. The algorithm therefore makes every honest process return by round r + 2 ≤ k + 2. Otherwise, no honest process returns before round k + 2. Thus, all honest processes participate in the first k + 1 invocations of Propose, and Theorem 4.11 guarantees a common honest king within these rounds. By Lemma 5.4, every honest process records a decision by round k + 1 and returns by round k + 2 ≤ t + 1. Combining the two bounds, every honest process records a decision and returns it by the end of round R = min{t + 1, f + 2, k + 2}. Lemma 5.7 (Agreement). All honest processes return the same value. Proof. Let T = t + 1, and let r be the earliest round in which an honest process records a decision. Such a round exists by Lemma 5.6. Let v be a decision recorded by an honest process in round r. Suppose r < T . By Lemma 5.5, every honest process holds v at the end of round r, and every honest process has recorded v by the end of round r + 1. In round r + 1, the processes that recorded v in round r return v, and every other honest process records v. If r + 1 = T , the remaining processes return v after the loop. Otherwise, they return their recorded decision v at the end of round r + 2, regardless of the outcome of that round. So every honest process returns v. It remains to consider the case r = T . No honest process has recorded a decision earlier, so all honest processes participate through round T . Suppose pj were honest for some 1 ≤ j ≤ t. Then round j < T would have a common honest predetermined king. By Lemma 5.4, every honest process would record a decision in round j, contradicting the choice of r. Therefore, p1 , . . . , pt are all Byzantine. Since f ≤ t, the predetermined king pT = pt+1 is honest. By Lemma 5.4, the final graded-consensus instance of round T returns the same value with grade 1 at every honest process. This common value must be v, since an honest process records v in round T . Thus, every honest process records v and returns it after the loop. Therefore, all honest processes return the same value in all cases. We are now ready to prove our main theorem: 11

Theorem 5.8. For every collection of prediction vectors, Algorithm 3 solves binary Byzantine Agreement when at most t < n/3 processes are Byzantine. Let B ≤ n2 be the total number of incorrect prediction bits held by honest processes, and let P = 1 + min{B/n, f }. Every
honest process returns within O (P ) communication rounds, and honest processes send O n2 P
messages and O n3 + n2 P log n bits in total. Proof. Correctness. Since t < n/3, all lemmas of this section apply. By Lemma 5.6, every honest process returns a value. By Lemma 5.7, all honest processes return the same value, and by Lemma 5.2, if all honest processes start with the same input v, then they all return v. Hence Algorithm 3 satisfies termination, agreement, and validity. Round complexity. Lemma 5.6 shows that every honest process returns by the end of round R = min{t + 1, f + 2, k + 2}. Since f ≤ t < n/3, Lemma 4.2 applies with ϵ = 1/3, so there is a constant c ≥ 1 such that k ≤ c B/n. Therefore, R ≤ 2 + min{f, c B/n} ≤ 2 + c min{f, B/n} ≤ 2 + c P. The classification step takes one communication round, and each round of the main loop takes O (1) communication rounds. Hence every honest process returns within O (1) + O (R) = O (P ) communication rounds. Communication complexity. We count only messages sent by honest processes. With the graded-consensus instantiation specified in the model, each invocation takes two communication rounds and each honest process sends O (n) messages of O (1) bits each. • Classification. Every honest process broadcasts its n-bit prediction vector once. This contributes at most n2 messages and n3 bits. • Main loop. In each round in which it participates, an honest process takes part in three graded-consensus instances (O (n) messages of O (1) bits), performs two value broadcasts (2n messages of one bit), and broadcasts one id in Propose (n messages of log n bits). Thus it sends O (n) messages and O (n log n) bits per round. Since every
honest pro2 R messages and cess participates in at most R rounds, the main loop contributes O n
O n2 R log n bits.

Since R = O (P ) and P ≥ 1, honest processes send O n2 P messages and O n3 + n2 P log n bits in total.
Observation 5.9. The initial classification contributes O n3 bits, while the subsequent agree
ment execution contributes O n2 P log n bits. Exchanging short prefixes of locally predicted honest lists, with lengths chosen by guessand-double, removes the initial O(n3 ) bit cost and reduces total communication to O(n2 P log n) bits. The construction and proof appear in Appendix A. Theorem 5.10. Algorithm 4 (see Appendix A) solves binary Byzantine Agreement when at most t < n/3 processes are Byzantine and for any number of prediction errors. More specifically, let
2 B = O n denote the total number of incorrect prediction bits held by honest processes, and let P = 1 + min{B/n, f }. Every
honest process returns within
O (P ) communication rounds, and honest processes send O n2 P messages and O n2 P log n bits in total.

6

Conclusion

We presented a deterministic protocol for synchronous binary Byzantine agreement with classification predictions and optimal resilience t < n/3. Our construction provides a specifically designed prediction-aware Phase King protocol by combining predetermined and predictionselected kings. It guarantees correctness for arbitrarily many prediction errors and terminates 12

in O (P ) communication rounds, where P = 1 + min{B/n, f }. Thus, accurate predictions accelerate agreement, while inaccurate predictions preserve the O (f + 1) early-stopping guarantee. In the basic construction complete prediction vectors are exchanged. We also present a communication-efficient variant, where prefixes of locally predicted honest lists are exchanged instead, using a guess-and-double strategy to adapt their lengths as the number of prediction
errors is unknown to the processes. This removes the initial cubic bit cost and achieves O n2 P
2 messages and O n P log n bits while preserving the round bound and resilience. Our protocol combines state-of-the-art theoretical guarantees (apart from a P/ log P communication overhead compared to [15]) with practical advantages, due to the avoidance of involved preprocessing (as is the case in [3, 15]). In particular, we believe that our prediction-aware king selection procedure can be of independent interest and can find further applications in learningaugmented consensus. In this direction, an interesting open question is whether our techniques can be extended to the case of authenticated protocols.

13

References [1]

Ittai Abraham and Danny Dolev. “Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity”. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. ACM, 2015, pp. 605–614. doi: 10. 1145/2746539.2746581.

[2]

Yossi Azar, Debmalya Panigrahi, and Noam Touitou. “Online Graph Algorithms with Predictions”. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2022, pp. 35–66. doi: 10.1137/1.9781611977073.3.

[3]

Naama Ben-David et al. “Byzantine Agreement with Predictions”. In: Proceedings of the ACM Symposium on Principles of Distributed Computing,PODC 2025. Ed. by Alkida Balliu and Fabian Kuhn. ACM, 2025, pp. 3–14. doi: 10.1145/3732772.3733518.

[4]

Piotr Berman, Juan A Garay, and Kenneth J Perry. “Bit optimal distributed consensus”. In: Computer science: research and applications. Springer, 1992, pp. 313–321.

[5]

Piotr Berman, Juan A. Garay, and Kenneth J. Perry. “Optimal Early Stopping in Distributed Consensus”. In: Distributed Algorithms: 6th International Workshop, WDAG 1992. Vol. 647. Lecture Notes in Computer Science. Springer, 1992, pp. 221–237. doi: 10.1007/3-540-56188-9_15.

[6]

Joan Boyar, Faith Ellen, and Kim S. Larsen. Distributed Graph Algorithms with Predictions. 2025. arXiv: 2501.05267 [cs.DC]. url: https://arxiv.org/abs/2501.05267.

[7]

Tushar Deepak Chandra and Sam Toueg. “Unreliable Failure Detectors for Reliable Distributed Systems”. In: Journal of the ACM 43.2 (1996), pp. 225–267. doi: 10 . 1145 / 226643.226647.

[8]

Michael B. Cohen. “Ramanujan Graphs in Polynomial Time”. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 2016, pp. 276–281. doi: 10. 1109/FOCS.2016.37.

[9]

Andrei Constantinescu et al. “From Few to Many Faults: Optimal Adaptive Byzantine Agreement”. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, 2026, pp. 177–187. doi: 10.1145/3796701.3815964. url: https://arxiv. org/abs/2505.19989.

[10]

Julien Dallot et al. “Resilient Byzantine Agreement with Predictions”. In: arXiv preprint arXiv:2605.19452 (2026).

[11]

Danny Dolev and Rüdiger Reischuk. “Bounds on information exchange for byzantine agreement”. In: Journal of the ACM (JACM) 32.1 (1985), pp. 191–204.

[12]

Danny Dolev, Ruediger Reischuk, and H. Raymond Strong. “Early Stopping in Byzantine Agreement”. In: Journal of the ACM 37.4 (1990), pp. 720–741. doi: 10.1145/96559. 96565.

[13]

Assia Doudou and André Schiper. “Muteness detectors for consensus with Byzantine processes”. In: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing. 1998, p. 315.

[14]

Marc Dufay, Muhammad Ayaz Dzulfikar, and Seth Gilbert. “Predictions Can Only Help! Communication Efficient Byzantine Agreement with Predictions”. In: 40th International Symposium on Distributed Computing, DISC 2026. Ed. by William K. Moses Jr. and Keren Censor-Hillel. Vol. 397. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, 8:1–8:22. doi: 10.4230/LIPICS.DISC.2026.8.

[15]

Marc Dufay, Diana Ghinea, and Anton Paramonov. “General Convex Agreement with Near-Optimal Communication”. In: arXiv preprint arXiv:2602.21411 (2026). 14

[16]

e 2 ) CommuniYuval Efron, Jovan Komatovic, and Ling Ren. Byzantine Broadcast in O(n cation. Cryptology ePrint Archive, Paper 2026/2504. 2026. url: https://eprint.iacr. org/2026/2504.

[17]

Michael J. Fischer and Nancy A. Lynch. “A Lower Bound for the Time to Assure Interactive Consistency”. In: Information Processing Letters 14.4 (1982), pp. 183–186. doi: 10.1016/0020-0190(82)90033-3.

[18]

Seth Gilbert et al. “Contention Resolution with Predictions”. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. ACM, 2021, pp. 127–137. url: https://arxiv.org/abs/2105.12706.

[19]

Kim Potter Kihlstrom, Louise E Moser, and P Michael Melliar-Smith. “Byzantine fault detectors for solving consensus”. In: The Computer Journal 46.1 (2003), pp. 16–35.

[20]

Leslie Lamport, Robert Shostak, and Marshall Pease. “The Byzantine generals problem”. In: Concurrency: the works of leslie lamport. 2019, pp. 203–226.

[21]

Christoph Lenzen and Sahar Sheikholeslami. “A Recursive Early-Stopping Phase King Protocol”. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. ACM, 2022, pp. 60–69. doi: 10.1145/3519270.3538425.

[22]

Shi Li and Jiayi Xian. “Online Unrelated Machine Load Balancing with Predictions Revisited”. In: Proceedings of the 38th International Conference on Machine Learning. Vol. 139. Proceedings of Machine Learning Research. 2021, pp. 6523–6532. url: https: //proceedings.mlr.press/v139/li21w.html.

[23]

Dahlia Malkhi and Michael K. Reiter. “Unreliable Intrusion Detection in Distributed Computations”. In: Proceedings of the 10th IEEE Computer Security Foundations Workshop. IEEE, 1997, pp. 116–124. doi: 10.1109/CSFW.1997.596799.

[24]

Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with Predictions. 2020. arXiv: 2006.09123 [cs.DS]. url: https://arxiv.org/abs/2006.09123.

[25]

Atsuki Momose and Ling Ren. “Optimal Communication Complexity of Authenticated Byzantine Agreement”. In: 35th International Symposium on Distributed Computing (DISC 2021). Vol. 209. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, 32:1–32:16. doi: 10.4230/LIPIcs.DISC.2021.32. url: https://eprint.iacr.org/2020/1569.

[26]

Marshall Pease, Robert Shostak, and Leslie Lamport. “Reaching Agreement in the Presence of Faults”. In: Journal of the ACM 27.2 (1980), pp. 228–234. doi: 10.1145/322186. 322188.

[27]

Manish Purohit, Zoya Svitkina, and Ravi Kumar. “Improving Online Algorithms via ML Predictions”. In: Advances in Neural Information Processing Systems. Vol. 31. 2018. url: https://papers.nips.cc/paper_files/paper/2018/hash/73a427badebe0e32caa2e1fc7530b7f3Abstract.html.

15

A

Classification with Smaller Communication Cost

The classification algorithm (Algorithm 1) requires every process to broadcast its prediction
vector that has size of Θ (n), resulting in Θ n3 bit complexity. However, the king-selection procedure (Algorithm 2) does not require the processes to create a complete classification vector. Instead, it is sufficient for each honest process to construct a set Si such that there exists at least one common honest process contained in the intersection of those sets: \  Si ∩ H ̸= ∅ i∈H

This weaker requirement allows us to avoid sharing the complete prediction vectors. For each process pi , let
Hpred = sort {j ∈ {1, . . . , n} : ai [j] = 1} i be the list of ids that pi predicts to be honest, ordered increasingly. Instead each process can broadcast a shorter prefix of its local list Hpred . An id is then included in Si only if it appears i in sufficiently many of the received prefixes. Let m ∈ {1, . . . , n} be the common prefix-length. Each process pi sends the prefix Pi containing the first min{m, |Hpred |} ids of Hpred . Let τ be the number of received prefixes in which an i i id must appear in order to be included in Si . For each id j ∈ {1, . . . , n}, let supporti (j) be the number of distinct senders whose proposal list received by pi contains j, including pi ’s own proposal. Each recipient accepts at most one proposal list per sender and counts each id at most once in that list. Define Si = {j ∈ {1, . . . , n} : supporti (j) ≥ τ }. The intuition is that the total number B of prediction errors will restrict the differences of Pi ’s in a way that there will be a common honest process jg∗ that will be “voted” by at least τ honest processes. Therefore, all honest processes will include jg∗ in their set Si . Processes do not know B but let B̃ ≥ B be a common upper bound on the total number of incorrect bits held by honest processes. Let η > 0 be the number of prediction errors that must be “spent” to make one honest process unsuitable as the common candidate. Then for an honest process pj ∈ H, define zj = |{i ∈ H : ai [j] = 0}|, i.e. zj is the number of honest processes that incorrectly predict pj to be faulty. Definition A.1 (η-good process). An honest process pj is η-good if zj < η, where zj = |{i ∈ H : ai [j] = 0}|. j k Lemma A.2. Let d denote the number of honest processes that are not η-good. Then d ≤ B̃ η . Proof. For each honest process pj ∈ H that is not η-good , we have zj ≥ η. So, there are at least η prediction errors. The total prediction errors are bounded by B̃, so d · η ≤ B̃ ⇒ d ≤ ⌊ B̃ η ⌋. If the number of honest processes that are not η-good is d ≥ n − t then our Byzantine Agreement will finish via the predetermined kings. Therefore, we focus on the “useful-prediction” regime, i.e. d < n − t. Observation A.3. In the useful-prediction regime d < n − t there exists at least one honest process that is η-good. Let jg∗ denote the honest process with the smallest id that is η-good . We want to ensure that enough honest (at least τ ) processes will broadcast jg∗ so that each honest process pi will include it in their Si . 16

Lemma A.4. Suppose d < n − t and m > d. The smallest η-good honest id jg∗ is contained in l m B̃ the prefixes of at least n − t − η − m−d honest processes. Proof. Since zjg∗ < η, more than n − t − η honest processes predict jg∗ to be honest. Each such process ph sends the first m smallest ids that it predicts to be honest. Suppose that ph does not include jg∗ in its first m locally-honest ids. Since ph predicts jg∗ as honest, there must be at least m ids preceding jg∗ that ph predicts to be honest. By the minimality of jg∗ , every smaller honest id is not η-good . Thus, by Lemma A.2, at most d of these ids can be actually honest. Hence at least m − d of these ids correspond to Byzantine processes that ph incorrectly predicts to be honest. Each such prediction is an incorrect prediction bit. Consequently, every honest supporter of jg∗ that fails to broadcast it accounts for at least m − d prediction errors. The total number of prediction errors is at most B̃. Hence, the number B̃ of such honest processes is at most ⌊ m−d ⌋. Therefore, the number of honest prefixes containing jg∗ is greater than n−t−η− B̃/(m−d). l m B̃ Lemma A.5. Suppose d < n − t, m > d, and 0 < τ ≤ n − t − η − m−d . Then the sets Si
T constructed by the honest processes with threshold τ satisfy i∈H Si ∩ H ̸= ∅. In particular, ∗ jg ∈ Si ∀i ∈ H. Proof. By Lemma A.4, at least τ honest processes broadcast proposal lists containing jg∗ . Every honest process receives the proposal of every honest sender. Therefore, for every honest pi , ∗ ∗ ∗ support Ti (jg ) ≥
τ . By the definition of Si , jg ∈ Si . Moreover, jg is honest by construction. Thus ∗ jg ∈ i∈H Si ∩ H, which proves the claim. For the subsequent king-selection procedure (Algorithm 2), it is also important to bound the total number of possible candidates appearing in any honest process’s set. Define [ C := Si . i∈H

The round complexity of Algorithm 2 is linear in |C| as we can deduce from Lemma 4.7. Lemma A.6. For any threshold τ > t, the union C satisfies |C| ≤ τnm −t . Proof. Consider any id j ∈ C. Then j ∈ Si for at least one honest process pi ∈ H. Therefore, supporti (j) ≥ τ . At most t of these proposals can originate from Byzantine processes. So, j must have been proposed by at least τ − t honest processes. Each honest process proposes at most m ids. Hence the total number of proposal ids generated by honest processes is at most nm. Every id belonging to C accounts for at least τ − t of these honest proposal ids. Thus, |C|(τ − t) ≤ nm. Dividing by the positive quantity τ − t proves the claim.

A.1

Choosing m and η

Let N = n − 2t and q = n − t − η − m−B̃ . If B̃/η < n − t, m > B̃/η, and q > t, choosing τ = ⌈q⌉ B̃/η satisfies Lemma A.5. By Theorem A.6, the resulting union size |C| is bounded by nm

Φ(m; η) =

n − 2t − η −

17

B̃ m−⌊ B̃ ⌋ η

.

√

For fixed 0 < η < N we want to minimize Φ(m; η). The m that minimizes Φ is: m∗ (η) = η(√B̃N −N√η) . B̃ Substituting this into the bound on C gives: |C| ≤ η(√Nn− √ 2 . Now we optimize for η. Let η) B̃ N ∗ Ψ(η) = η(√Nn− √ 2 . Then, the η that minimizes Ψ is η = 4 . η)

Then the prefix length m and the threshold τ become: m∗ =

8B̃ N

τ=

n 2

Corollary A.7 (Prefix parameters). Let N = n − 2t, let m ∈ {1, . . . , n}, and suppose B ≤ B̃ ≤TN8m . Set η = N/4 and construct the candidate sets with threshold τ = ⌈n/2⌉. Then jg∗ ∈ i∈H Si , |C| ≤ 2nm N < 6m. In particular, the candidate sets share an honest id. m n B̃ ∗ Proof. By Lemma A.2, d ≤ B̃ η ≤ 2 ≤ 2 < n − t. Thus jg exists and m > d. Moreover, m−d ≤   2B̃ N n m ≤ 4 = η. The support bound of Lemma A.4 is therefore at least ⌈n − t − 2η⌉ = 2 = τ . By Lemma A.5, jg∗ belongs to every honest candidate set. Since τ − t ≥ N/2 > 0, Theorem A.6 gives |C| ≤ 2nm/N < 6m, using t < n/3.   Since N = Θ(n), this gives m = Θ(1 + B̃/n) and |C| = O 1 + B̃/n .

A.2

Guess-and-double Wrapper

To remove the assumption that processes know an upper bound B̃ on the number of prediction errors, we use a guess-and-double strategy. Processes execute synchronized phases with geometrically increasing guesses, which determine both the prefix lengths used to construct the candidate sets and the number of iterations executed in each phase. Phases are indexed by ϕ = 0, . . . , ⌈log2 (t + 1)⌉. Write N = n − 2t. In phase ϕ, define   N mϕ 2nmϕ ϕ mϕ = 2 , B̃ϕ = , Lϕ = + 1. 8 N Once B̃ϕ ≥ B, the candidate-set bound guarantees a common honest king within Lϕ − 1 iteration. The additional iteration allows all honest processes to return. Predetermined kings are used consecutively across phases, ensuring termination even when all guesses underestimate the number of prediction errors. Each phase begins with one communication round in which processes broadcast prefixes of at most mϕ ids. In each phase, processes compute support counts using only the prefixes exchanged in that phase, counting their own prefix as well. Processes construct Si using threshold τ = ⌈n/2⌉ and set Li = sort(Si ). The leader list remains fixed within the phase. Let r be the index of the next predetermined king at the beginning of the phase. Each process executes Lϕ iterations in phase ϕ, unless it returns earlier. Each iteration contains the two king steps and final graded-consensus check of Algorithm 3. The first king is pr , while the second is selected by Propose using the current leader list. Each iteration takes O (1) rounds. The counter r is initialized once and incremented after each completed iteration. Thus, predetermined kings are used consecutively across phases. The current value and recorded decision also persist between phases; only the candidate lists and proposal positions are reinitialized. The predetermined kings guarantee progress as a function of f , while the selected kings can accelerate agreement when the candidate sets contain a common honest id. A process records a decision when the final graded consensus returns grade 1. It participates in one further iteration. After iteration t+1, every remaining honest process returns its recorded decision.

18

Algorithm 4 Byzantine Agreement with Predictions (code for process pi ) 1: procedure ba-with-prefixes(xi , ⃗ ai ) 2: Hpred ← sort({j : a [j] = 1}) i i 3: vi ← xi , decidedi ← false, r ← 1, N ← n − 2t 4: for ϕ = 0 to ⌈log2 (t + 1)⌉ do 5: mϕ ← 2ϕ , B̃ϕ ← N mϕ /8, Lϕ ← ⌈2nmϕ /N ⌉ + 1 6: Pi ← first min{mϕ , |Hpred |} ids of Hpred i i 7: Broadcast(Pi ) 8: Si ← {j ∈ {1, . . . , n} : supporti (j) ≥ ⌈n/2⌉} 9: Li ← sort(Si ) 10: if Li = ∅ then Li ← [i] 11: posi ← 1 12: for ℓ = 1 to Lϕ do 13: (vi , gi ) ← graded-consensus(vi ) 14: Broadcast(vi ) 15: if gi = 0 then vi ← vr ▷ Predetermined king pr 16: (vi , gi ) ← graded-consensus(vi ) 17: (kingi , posi ) ← Propose(Li , posi ) 18: Broadcast(vi ) 19: if gi = 0 then vi ← vkingi ▷ Selected king 20: 21: 22: 23: 24: 25: 26: 27: 28:

(vi , gi ) ← graded-consensus(vi ) if decidedi then return decisioni if gi = 1 then decisioni ← vi decidedi ← true if r = t + 1 then return decisioni r ←r+1 return decisioni

Theorem A.8. Algorithm 4 solves binary Byzantine Agreement when at most t < n/3 processes
are Byzantine and for any number of prediction errors. More specifically, let B = O n2 denote the total number of incorrect prediction bits held by honest processes, and let P = 1 + min{B/n, f }. Every honest process returns within
O (P ) communication rounds, and honest
processes send O n2 P messages and O n2 P log n bits in total. Proof. Processes retain their current values and recorded decisions across phases. Therefore, the preservation, decision-propagation, and agreement arguments (Lemmas 5.1, 5.5 and 5.7) for Algorithm 3 remain valid. The phase range mϕ ≤ n provides at least t + 1 iterations, so one of the first f + 1 predetermined king will be honest. Thus every honest process records a decision and returns by iteration R ≤ min{t+1, f +2}. Agreement and validity follow as for Algorithm 3. To prove the prediction-dependent bound, consider a phase with B̃ϕ ≥ B. If an honest process has already recorded a decision, propagation ensures termination within two further iterations. Otherwise, all honest processes participate in the prefix exchange. Let K be the size of the union of the honest candidate sets. By Corollary A.7, their candidate sets share a common honest id jg∗ : \ 2nmϕ . jg∗ ∈ Si and K := |C| ≤ N i∈H

There are at most K − 1 proposed ids below the shared honest id jg∗ . The progress and con19

vergence arguments of Lemmas 4.7 and 4.10 therefore give a common honest king within K iterations. If a first decision occurs in iteration a < K, all honest processes return by iteration a+2 ≤ K +1. Otherwise, the common honest king makes everyone record a decision by iteration K and return in the next iteration. Since K + 1 ≤ Lϕ , all honest processes return by the end of this phase. If the global iteration counter reaches t + 1 earlier, every remaining honest process returns then. n ϕ n In each phase the number of iterations are Lϕ = 2 N 2 + 1. Since n > 3t, then 1 ≤ N < 3. ϕ ϕ ϕ Therefore, 2 · 2 ≤ Lϕ ≤ 6 · 2 + 1 ≤ 7 · 2 . So the number of iterations until a phase ϕ are: ϕ X

  Lψ ≤ 7(2ϕ+1 − 1) = O 2ϕ .

ψ=0 ∗

∗

Let ϕ∗ be the first phase where B̃ϕ∗ ≥ B, which means N 2ϕ /8 ≥ B. If ϕ∗ = 0, then 2ϕ = 1. Otherwise, the upper error bound for the previous phase would be less than B̃, i.e. B̃ϕ∗ −1 < B. ϕ∗ −1

Therefore, N 2 8

∗

< B, hence 2ϕ < 16B N . Consequently, ∗

2ϕ = O (1 + B/n) . Let R denote the number of iterations until every honest process has returned, and Φ = ⌈log(t + 1)⌉ be the last scheduled phase. If ϕ∗ ≤ Φ, all honest
processes return by the end of phase ϕ∗ , or earlier. The geometric sum ∗ above gives R = O 2ϕ = O (1 + B/n) . If ϕ∗ > Φ, in each phase the upper error bound is Φ not greater than the real number of errors. In particular, B > N82 ≥ N (t+1) . In this case, the 8 honest nodes terminates through the predetermined kings in rounds R ≤ t + 1 < 8B N = O (B/n) . Therefore R = O (1 + B/n) in both cases. Independently, predetermined kings give R ≤ f + 2. Combining the two bounds, R = O (min{f + 1, 1 + B/n}) = O (1 + min{f, B/n}) = O (P ) . Communication complexity. In each phase ϕ the processes exchange a prefix of their predic
ϕ . This gives O n2 messages for each round and tion vectors, that each one has size m = 2 ϕ
O n2 · 2ϕ log n bits. P Let q be the last phase reached. Then for the prefixes sizes holds qϕ=0 mϕ = 2q+1 − 1 ≤ R. Therefore, for q phases for the prefixes exchanges the total number of bits are:   q X
O n2 log n mϕ  = O n2 R log n ϕ=0

Each iteration also uses O n2 messages and O n2 log n bits from graded-consensus and propose. The total number of iterations are R = O (P ). So the total nubmer of messages and bits respctively are:

O n2 P messages , O n2 P log n bits.

B

Notation Table

The table 1 below summarizes the notation used throughout the paper.

20

Symbol n t f H, F ⃗ai ⃗ci Hi Li Hpred i B B̃ P k posi (r) qi (r) si (r) η Vir (j) b r (s) U r (s), U i

C m τ

i

Meaning Number of processes. Upper bound on the number of Byzantine processes. Actual number of Byzantine processes. Sets of honest and Byzantine processes, respectively. Raw prediction vector held by process pi . Classification vector computed by process pi . Sets of ids classified as honest according to ⃗ci . the ids of Hi (or of Si in Section A) in increasing order. Increasingly ordered list of ids predicted to be honest according to ⃗ai . Total number of incorrect prediction bits held by honest processes. Common upper bound on B. Round parameter P = 1 + min{B/n, f }. Number of ids misclassified by at least one honest process. Position in Li of the id proposed by pi in round r. id proposed by process pi in round r. King selected by pi in round r. Error threshold defining an η-good honest process. Number of votes for id j received by pi in round r. Number of votes received by pi in round r for ids at least s, counting all ids or only those in Li , respectively. S Union of the candidate sets of honest processes: C = i∈H Si . Maximum number of ids included in a proposal prefix. Support threshold for including an id in Si .

Table 1: Notation used throughout the paper.

21

Related documents

• Communication Efficient Byzantine Agreement with Predictions#180632
• Settling The Round Complexity of Byzantine Agreement Against a Full-Information, Adaptive Adversary#373364
• Scalable Composition of Byzantine Agreements under Reorder Attacks#987959
• Decoupling Trust in Byzantine CRDTs: Fine-grained Post-Compromise Handling without Breaking Causality#324861
• State Without a Landlord: An Architecture Proposal for Peer-to-Peer Replication of Durable Workflow State#1011376