Source-linked AI summary
Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs
Nitin Vaidya, Lewis Tseng, Guanfeng Liang
TL;DR
The paper asks when iterative approximate Byzantine consensus is possible in arbitrary directed graphs with Byzantine faults. It proves necessary and sufficient graph conditions and uses them to analyze specific graphs, while noting that the results rely on assumptions the authors are extending.
Problem
Tight necessary and sufficient conditions for iterative approximate consensus in arbitrary directed graphs under point-to-point Byzantine faults remained an open problem.
Method
The paper proves necessary and sufficient graph conditions for iterative approximate Byzantine consensus and uses the sufficient condition to examine specific graphs.
Results
A correct iterative consensus algorithm requires every partition into F, L, and R, with |F| ≤ f and nonempty L and R, to satisfy L ⇒ R or R ⇒ L; also, n must exceed 3f.
Takeaways & Limitations
The characterization determines whether iterative Byzantine consensus algorithms exist for arbitrary directed graphs and certain specific graphs.
Takeaways & Limitations
The authors are exploring extensions that relax some assumptions made in this work.
Abstract
from arXiv · showhide
In this paper, we explore the problem of iterative approximate Byzantine consensus in arbitrary directed graphs. In particular, we prove a necessary and sufficient condition for the existence of iterative byzantine consensus algorithms. Additionally, we use our sufficient condition to examine whether such algorithms exist for some specific graphs.
3 Coordinated Science Laboratory
The report acknowledges prior technical-report provenance and states funding and disclaimer information.
- The research was supported in part by National Science Foundation award CNS 1059540.
- The authors state that the opinions and conclusions are their own and do not necessarily reflect the funding agencies or U.S. government.
- The report is a modified version of an earlier technical report on the same topic.
1 Introduction
The introduction frames approximate Byzantine consensus in partially connected networks and identifies tight conditions for iterative algorithms in arbitrary directed graphs as an open problem.
- Approximate consensus seeks fault-free nodes whose outputs are approximately equal, with iterative algorithms known for fully connected graphs when n exceeds 3f.
- Prior work examined local convergence, special graphs, asynchronous systems, data aggregation, and broadcast-model distributed function calculation.
- Sufficient conditions and graph constructions have also been studied under the f-local fault model.
- Related work includes continuous-time consensus and broadcast-model conditions for approximate consensus in arbitrary graphs.
- The paper identifies tight necessary and sufficient conditions for iterative approximate consensus in arbitrary directed graphs under point-to-point Byzantine faults as an open problem.
2 Preliminaries
The paper models synchronous iterative consensus over authenticated directed networks with Byzantine faults, state-based outputs, validity, and convergence requirements.
- 2.1 Network Model: The network is a synchronous simple directed graph with authenticated edges, where each edge permits reliable transmission from its source to its destination.
- 2.2 Fault Model: Up to f nodes may behave arbitrarily as Byzantine faults, including sending inconsistent messages and collaborating with complete system knowledge.
- 2.3 Iterative Approximate Byzantine Consensus: Approximate consensus requires validity within the input convex hull and convergence of fault-free outputs, with each node's output equal to its state.
- 2.3 Iterative Approximate Byzantine Consensus: Each iteration transmits current states, receives incoming values, and applies a node-specific transition function to update the state.
- 2.3 Iterative Approximate Byzantine Consensus: The validity condition requires the fault-free maximum state not to increase and the minimum not to decrease across iterations.
- 2.3 Iterative Approximate Byzantine Consensus: The analysis assumes each node has at least 2f incoming links, and the iterative state evolution depends only on the preceding state rather than prior history.
- 2.3 Iterative Approximate Byzantine Consensus: Algorithm 1 sorts received values, removes the smallest f and largest f values, and computes from the remaining values using normalized positive weights.
3 Necessary Condition
Theorem 1 establishes a necessary partition-based condition for iterative approximate Byzantine consensus: every partition with at most f faulty nodes must satisfy one of two directional influence conditions. The proof constructs indistinguishable executions that keep fault-free nodes in opposing sets at m and M, violating convergence.
- Proof of necessity: If both directional conditions fail, faulty nodes can send values below m to L, above M to R, and values in [m, M] to C.The construction uses m− < m < M < M+ and exploits uncertainty about which nodes are faulty.
- Proof of necessity: Validity forces each node in L to retain m and each node in R to retain M after the first iteration, including when two fault scenarios are indistinguishable.For nodes in C, validity keeps the new state within [m, M].
- Proof of necessity: The same state pattern persists by induction, so fault-free nodes in L and R never converge, contradicting the assumed correctness of the iterative algorithm.The persistent separation violates the convergence requirement.
- Corollaries: Corollary 1 states that for any partition F, L, R with |F| ≤ f and nonempty L and R, either L ⇒ R or R ⇒ L.This follows by setting C to the empty set in Theorem 1.
- Corollaries: The node count must satisfy n > 3f, and when f > 0 every node must have at least 2f + 1 incoming links.Both bounds follow from applying the partition condition to carefully chosen partitions.
4 Useful Lemmas
The useful lemmas convert the partition condition into a propagation property between two nonempty sets. Under Theorem 1, if one set does not influence the other, the other propagates toward it; consequently, at least one direction of propagation always exists.
- Propagation definition: A propagates to B when finite sequences transfer nodes from B into A until B becomes empty, with each step supported by at least f + 1 incoming links.The propagation length is finite and is bounded above by n − f − 1.
- Lemma 1: Lemma 1 proves that if B̸ ⇒ A, then A propagates to B under the necessary condition of Theorem 1.The proof repeatedly moves nodes in in(Ak ⇒ Bk) from Bk to Ak until the remaining set is empty.
- Lemma 1 proof: The induction step shows that either the remaining Bτ+1 is empty or Aτ+1 ⇒ Bτ+1, enabling the propagating sequences to continue.Aτ+1 adds nodes influenced by Aτ, while Bτ+1 removes those nodes.
- Lemma 2: Lemma 2 concludes that for any partition A, B, F with nonempty A and B and |F| ≤ f, either A propagates to B or B propagates to A.When A does not influence B, Lemma 1 gives propagation from B to A; otherwise the proof analyzes whether A propagates to B.
5 Sufficiency
The paper proves that the necessary graph condition is sufficient: Algorithm 1 preserves validity and achieves convergence when Theorem 1 holds.
- Validity: Algorithm 1 satisfies validity whenever the graph satisfies Theorem 1.Every fault-free node's updated state remains within the previous fault-free state range [µ[t−1], U[t−1]].
- Validity: After eliminating the f smallest and f largest received values, remaining faulty values are either removed or bounded by fault-free values.With at least 2f + 1 incoming values, trimming 2f values leaves values suitable for a weighted-average update.
- Convergence: Propagation contracts the fault-free state range through repeated weighted averaging.Lemma 5 bounds the range after l propagation steps by (1 −α^l)(U[s] −µ[s]) + α^l(M −m).
- Convergence: For any ǫ > 0, sufficiently many iterations make the fault-free state range small enough to satisfy convergence.The proof repeatedly applies the contraction bound using the sequence of iteration indices τ_i.
6 Applications
The sufficient condition is applied to several network families. Core networks support iterative consensus, whereas connectivity alone does not guarantee it for hypercubes or directed symmetric chord networks.
- Core Network: A core network contains a 2f + 1-node clique, with every other node linked bidirectionally to all clique nodes.The paper states that core networks satisfy Theorem 1, so Algorithm 1 achieves approximate consensus there.
- Core Network: For n = 3f + 1, the paper conjectures that a core network uses the fewest edges among suitable undirected networks.This is explicitly presented as a conjecture, not a proved minimality result.
- Hypercube: A d-dimensional binary hypercube can have connectivity d yet fail Theorem 1 after removing edges along one dimension.Each node then has only one edge across the partition, leaving fewer than f + 1 neighbors across it for any f ≥1.
- Chord Network: For f = 2 and n = 7, the chord network does not satisfy Theorem 1.With faulty nodes 5 and 6, partition L = {0, 2}, R = {1, 3, 4} fails the required propagation relations.
7 Asynchronous Networks
The asynchronous generalization strengthens the incoming-link requirement and imposes larger network-size constraints; full details are deferred to future work.
- Totally Asynchronous Networks: In a totally asynchronous network, the ⇒ relation requires at least 2f + 1 incoming links instead of f + 1.This is the primary change needed to generalize the results to the totally asynchronous setting.
- Totally Asynchronous Networks: For f > 0, each node must have at least 3f + 1 incoming neighbors, and the network must contain more than 5f nodes.These conditions follow from the strengthened incoming-link requirement.
- Partially Asynchronous Networks: The results can also be generalized to a partially asynchronous model allowing message delays of up to B iterations.The supplied passage states that this model is the one defined in Section 7 of.
- Scope: Full details of these asynchronous generalizations are deferred to a future technical report.
8 Conclusion
The paper establishes a necessary and sufficient condition for iterative approximate consensus in arbitrary directed graphs and applies it to selected graphs. Future work explores relaxing some assumptions.
- The paper proves a necessary and sufficient condition for iterative approximate consensus algorithms in arbitrary directed graphs.
- The results also apply to undirected graphs as a special case.
- The condition is used to determine whether iterative algorithms exist for certain specific graphs.
- Ongoing research explores extensions that relax some assumptions made in this work.
A Proof of Claim 3
The proof of Claim 3 proceeds by induction over expanding node sets. It handles nodes already in the current set and newly added nodes using value elimination and contraction inequalities.
- Claim 4 is proved by induction on τ, with Rτ and Rτ+1 − Rτ considered separately.The induction basis holds at τ = 0 by the definition of M.
- Set Rτ: For nodes in Rτ, validity and Lemma 4 propagate the bound in (24) from α^τ(U[s] − M) to α^(τ+1)(U[s] − M).
- Set Rτ+1 − Rτ: For newly added nodes, Algorithm 1 eliminates the f smallest and f largest received values before updating the state.
- Set Rτ+1 − Rτ: When at least f + 1 values from N−i ∩ Rτ are eliminated, the remaining values lie within the interval associated with those nodes.
- Set Rτ+1 − Rτ: A non-eliminated value from a possibly faulty node can be bounded using a fault-free node p, yielding the same α^(τ+1)(U[s] − M) contraction.
- Claim 3 follows by setting τ = l in Claim 4, with Rl = V − F by definition.
B Completing the proof of Lemma 2
The proof completes Lemma 2 by transferring propagation from sets P and Q to sets R and S. An induction preserves set containment until R reaches all fault-free nodes.
- The proof starts from P = Bk and Q = Ak, which form propagating sequences and partition V − F.
- It defines R = B and S = A, with P0 ⊆ R0 and S0 ⊆ Q0; Figure 4 illustrates these set relationships.
- The first expansion defines P1 and R1 through incoming neighbors, then establishes P1 ⊆ R1 and S1 ⊆ Q1.
- Repeating the containment argument inductively gives Pi ⊆ Ri and Si ⊆ Qi for each stage.
- Because Pm = P ∪ Q = V − F, some r ≤ m satisfies Rr = V − F, proving that R = B propagates to S = A.
C Proof of Lemma 4
Lemma 4 bounds each received state by the current global upper bound. The proof distinguishes fault-free and faulty senders, using incoming-degree redundancy in the faulty case.
- Fault-free sender: For a fault-free sender j, the received value equals its previous state and lies between μ[t − 1] and U[t − 1].
- Faulty sender: For a faulty sender j, at least 2f + 1 incoming edges ensure that one of the largest f received values belongs to a fault-free node.
- Faulty sender: That fault-free comparison state is at least the faulty value, so the faulty value is also bounded above by U[t − 1].
- Because the weights in Equation 2 sum to 1, the update equation can be rewritten accordingly.