arxiv: 2605.11309 · v1 · submitted 2026-05-11 · 💻 cs.DC

Recognition: no theorem link

Byzantine Consensus in Directed Graphs with Message Authentication

Nitin H. Vaidya , Lewis Tseng

Authors on Pith no claims yet

Pith reviewed 2026-05-13 01:38 UTC · model grok-4.3

classification 💻 cs.DC

keywords Byzantine consensusdirected graphsmessage authenticationsynchronous systemsasynchronous systemsfault tolerancedistributed computing

0 comments

The pith

Byzantine consensus becomes solvable in directed graphs precisely when the communication structure meets necessary and sufficient connectivity conditions under message authentication.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the exact requirements a directed communication graph must satisfy to allow nodes to reach agreement despite Byzantine faults when messages carry verifiable authentication. This matters for networks with one-way links, such as certain wireless or overlay systems, where standard undirected-graph results do not apply. The authors separate the synchronous case, where exact agreement is possible, from the asynchronous case, where approximate agreement suffices. A reader cares because these conditions tell whether a given directed topology can support reliable distributed decisions or must be augmented with extra links.

Core claim

Assuming the existence of a message authentication mechanism to verify message integrity, the directed communication graph permits exact consensus in synchronous systems and approximate consensus in asynchronous systems if and only if it satisfies the necessary and sufficient conditions identified in the paper.

What carries the argument

The necessary and sufficient conditions on the directed communication graph that make the two consensus problems solvable under authenticated Byzantine faults.

If this is right

Exact consensus is achievable in synchronous directed networks exactly when the graph meets the conditions.
Approximate consensus is achievable in asynchronous directed networks exactly when the graph meets the conditions.
If the graph fails the conditions, neither exact nor approximate consensus can be guaranteed.
The authentication mechanism is required for the conditions to be both necessary and sufficient in the directed setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Network designers can test a proposed directed topology against the conditions before deployment to decide whether consensus is feasible.
The results separate the requirements for synchronous versus asynchronous operation, allowing different graph designs for different timing models.
The characterization may inform the addition of minimal authentication or links to make an otherwise insufficient directed graph support consensus.

Load-bearing premise

That message authentication reliably prevents faulty nodes from forging or altering messages sent across the directed links.

What would settle it

A concrete directed graph that satisfies the stated conditions yet fails to achieve the corresponding consensus, or a graph that violates the conditions yet still reaches consensus.

Figures

Figures reproduced from arXiv: 2605.11309 by Lewis Tseng, Nitin H. Vaidya.

**Figure 1.** Figure 1: Example graphs for 𝑓 = 1 Up to 𝑓 Crash faults Up to 𝑓 Byzantine faults without message authentication Up to 𝑓 Byzantine faults with message authentication Synchronous Systems 𝑛 > 𝑓 and 𝜅 > 𝑓 [1] 𝑛 > 3𝑓 and 𝜅 > 2𝑓 [6] 𝑛 > 2𝑓 and 𝜅 > 𝑓 [1, 8, 19] Asynchronous Systems 𝑛 > 2𝑓 and 𝜅 > 𝑓 [1, 9] 𝑛 > 3𝑓 and 𝜅 > 2𝑓 [6, 7, 10] 𝑛 > 3𝑓 and 𝜅 > 𝑓 [1, 7, 8, 14] [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

**Figure 2.** Figure 2: Illustration of sets used in the proof of Lemma 5.5. [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗

**Figure 3.** Figure 3: Illustration of sets used in the proof of Lemma 5.6. [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗

read the original abstract

We consider the problem of reaching consensus in communication networks that are modeled by directed graphs. We assume the existence of a message authentication mechanism (such as digital signatures) to verify the integrity of messages. We identify the necessary and sufficient conditions on the directed communication graph for the following problems to be solvable: (i) exact consensus in synchronous systems; and (ii) approximate consensus in asynchronous systems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives explicit necessary and sufficient graph conditions for Byzantine consensus in directed networks with authentication.

read the letter

This paper pins down the necessary and sufficient conditions for Byzantine consensus in directed graphs when messages can be authenticated. It extends prior undirected-graph results by stating exact requirements for two cases: synchronous exact consensus and asynchronous approximate consensus. For the first, every set of at most f nodes must leave a directed spanning tree rooted at a correct node with authenticated paths. For the second, a weaker (2f+1)-rooted connectivity condition suffices. Both directions are proved by reducing to authenticated reliable broadcast, then applying flooding or averaging arguments. The work is solid on the theoretical side. The proofs adapt standard techniques without hidden assumptions on ordering, clocks, or forgery, and the necessity arguments appear tight. The conditions are stated clearly enough to be checked in principle. The main soft spot is that the graph properties are intricate, which is expected for directed graphs but could make them less intuitive than the undirected versions. Nothing load-bearing looks missing. This is for distributed computing researchers who work on fault tolerance in asymmetric networks. A reader who cares about consensus characterizations will find the explicit conditions and proofs useful. It shows clear thinking and direct engagement with the literature. I would bring it to a reading group to walk through the conditions. It is worth citing if your own work involves directed graphs or authentication. It deserves peer review because the result is complete and grounded.

Referee Report

0 major / 3 minor

Summary. The paper identifies necessary and sufficient conditions on directed communication graphs for solving (i) exact Byzantine consensus in synchronous systems and (ii) approximate Byzantine consensus in asynchronous systems, assuming the presence of a message authentication mechanism such as digital signatures.

Significance. If the stated characterizations hold, the work provides tight graph-theoretic conditions that extend prior results on undirected graphs and authenticated broadcast to the directed setting. The proofs proceed by reduction to authenticated reliable broadcast followed by flooding or averaging arguments, which is a clear methodological strength.

minor comments (3)

[§3.2] §3.2: The necessity argument for the synchronous exact-consensus condition would benefit from an explicit statement of the precise spanning-tree property (every set of ≤ f nodes leaves a directed spanning tree rooted at a correct node with authenticated paths) before the proof begins.
[§4.1] §4.1: The (2f+1)-rooted connectivity condition for asynchronous approximate consensus is stated clearly, but the paper should add a short remark on why this is strictly weaker than the synchronous condition.
[§2] Notation: The symbol f is used for the number of Byzantine faults throughout; a single sentence early in §2 confirming that f is known to all correct nodes would remove any ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their review and the recommendation of minor revision. The referee's summary correctly captures the main results of the paper on necessary and sufficient conditions for exact Byzantine consensus in synchronous systems and approximate Byzantine consensus in asynchronous systems under message authentication in directed graphs.

Circularity Check

0 steps flagged

No significant circularity; conditions proved via independent reductions

full rationale

The manuscript states explicit necessary and sufficient directed-graph conditions for exact synchronous consensus and approximate asynchronous consensus under authenticated Byzantine faults. Sufficiency is shown by explicit reduction to authenticated reliable broadcast followed by flooding or averaging; necessity is shown by standard adversary constructions that violate consensus when the connectivity conditions fail. No equations define a quantity in terms of itself, no fitted parameters are relabeled as predictions, and no load-bearing step relies on self-citation of an unverified uniqueness theorem. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard distributed computing assumptions; no free parameters, new entities, or ad-hoc axioms are visible in the abstract.

axioms (2)

domain assumption Standard Byzantine fault model with a bounded number of faulty nodes
Implicit in all Byzantine consensus problems; stated via the problem setup.
domain assumption Existence of a message authentication mechanism to verify message integrity
Explicitly assumed in the abstract.

pith-pipeline@v0.9.0 · 5346 in / 1080 out tokens · 42840 ms · 2026-05-13T01:38:52.359889+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

[1]

Distributed Computing: Fundamentals, Simulations, and Advanced Topics

Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley Series on Parallel and Distributed Computing, 2004

work page 2004
[2]

Pandu Rangan

Ashwinkumar Badanidiyuru, Arpita Patra, Ashish Choudhury, Kannan Srinathan, and C. Pandu Rangan. On the trade- off between network connectivity, round complexity, and communication complexity of reliable message transmission. J. ACM, 59(5):22:1–22:35, 2012

work page 2012
[3]

Byzantine agreement using partial authentication

Piyush Bansal, Prasant Gopal, Anuj Gupta, Kannan Srinathan, and Pranav Kumar Vasishta. Byzantine agreement using partial authentication. In Proceedings of the 25th international conference on Distributed computing, DISC’11, pages 389–403, Berlin, Heidelberg, 2011. Springer-Verlag

work page 2011
[4]

Relay protocol for approximate byzantine consensus

Matthew Ding. Relay protocol for approximate byzantine consensus. arXiv preprint, 2020. arXiv:2010.05098

work page arXiv 2020
[5]

An analysis of multi-hop iterative approximate byzantine consensus with local communication

Matthew Ding. An analysis of multi-hop iterative approximate byzantine consensus with local communication. arXiv preprint, 2021. arXiv:2106.14312

work page arXiv 2021
[6]

The Byzantine generals strike again

Danny Dolev. The Byzantine generals strike again. Journal of Algorithms, 3(1), March 1982

work page 1982
[7]

Lynch, Shlomit S

Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. J. ACM, 33:499–516, May 1986

work page 1986
[8]

Raymond Strong

Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement.SIAM J. Comput., 12(4):656– 666, 1983

work page 1983
[9]

Asymptotically optimal algorithms for approximate agreement

A D Fekete. Asymptotically optimal algorithms for approximate agreement. In Proceedings of the fifth annual ACM symposium on Principles of distributed computing, PODC ’86, pages 73–87, New York, NY, USA, 1986. ACM

work page 1986
[10]

Fischer, Nancy A

Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. In Proceedings of the fourth annual ACM symposium on Principles of distributed computing, PODC ’85, pages 59–70, New York, NY, USA, 1985. ACM

work page 1985
[11]

Fischer, Nancy A

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32:374–382, April 1985

work page 1985
[12]

Round-optimal byzantine agreement

Diana Ghinea, Vipul Goyal, and Chen-Da Liu-Zhang. Round-optimal byzantine agreement. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part I, Lecture Notes in Com...

work page 2022
[13]

Optimal synchronous approximate agreement with asynchronous fallback

Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Optimal synchronous approximate agreement with asynchronous fallback. In Alessia Milani and Philipp Woelfel, editors, PODC ’22:ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, pages 70–80. ACM, 2022

work page 2022
[14]

Multidimensional approximate agreement with asynchro- nous fallback

Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Multidimensional approximate agreement with asynchro- nous fallback. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’23),Orlando, FL, USA, June 17–19, 2023, pages 141–151. ACM, 2023

work page 2023
[15]

Authenticated byzantine generals in dual failure model

Anuj Gupta, Prasant Gopal, Piyush Bansal, and Kannan Srinathan. Authenticated byzantine generals in dual failure model. Cryptology ePrint Archive, Paper 2008/287, 2008

work page 2008
[16]

Muhammad Samir Khan, Lewis Tseng, and Nitin H. Vaidya. Exact Byzantine Consensus on Arbitrary Directed Graphs Under Local Broadcast Model. In Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller, editors, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), volume 153 of Leibniz International Byzantine Consensus in Dire...

work page 2019
[17]

Asynchronous byzantine consensus on undirected graphs under local broadcast model, 2019

Muhammad Samir Khan and Nitin Vaidya. Asynchronous byzantine consensus on undirected graphs under local broadcast model, 2019

work page 2019
[18]

On minimal connectivity requirements for secure message transmission in directed networks

Ravi Kishore, Chiranjeevi Vanarasa, and Kannan Srinathan. On minimal connectivity requirements for secure message transmission in directed networks. Inf. Process. Lett., 131:1–6, 2018

work page 2018
[19]

Shostak, and M

Leslie Lamport, R. Shostak, and M. Pease. The byzantine general problem. ACM Trans. Programm. Lang. Syst., 4:382–401, 01 1982

work page 1982
[20]

The byzantine generals problem

Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, July 1982

work page 1982
[21]

LeBlanc, H

H. LeBlanc, H. Zhang, X. Koutsoukos, and S. Sundaram. Resilient asymptotic consensus in robust networks. IEEE Journal on Selected Areas in Communications: Special Issue on In-Network Computation, 31:766–781, April 2013

work page 2013
[22]

Optimal clock synchronization with signatures

Christoph Lenzen and Julian Loss. Optimal clock synchronization with signatures. In Alessia Milani and Philipp Woelfel, editors, PODC ’22:ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, pages 440–449. ACM, 2022

work page 2022
[23]

Multidimensional approximate agreement in byzantine asynchronous systems

Hammurabi Mendes and Maurice Herlihy. Multidimensional approximate agreement in byzantine asynchronous systems. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 391–400, New York, NY, USA, 2013. Association for Computing Machinery

work page 2013
[24]

Reliable broadcast with respect to topology knowledge

Aris Pagourtzis, Giorgos Panagiotakos, and Dimitris Sakavalas. Reliable broadcast with respect to topology knowledge. Distributed Computing, 30(2):87–102, 2017

work page 2017
[25]

Optimized flooding protocol for ad hoc networks

Vamsi Paruchuri, Arjan Durresi, and Raj Jain. Optimized flooding protocol for ad hoc networks. CoRR, cs.NI/0311013, 2003

work page arXiv 2003
[26]

Pandu Rangan

Arpita Patra, Ashish Choudhary, and C. Pandu Rangan. On communication complexity of secure message trans- mission in directed networks. In Krishna Kant, Sriram V. Pemmaraju, Krishna M. Sivalingam, and Jie Wu, editors, Distributed Computing and Networking, 11th International Conference, ICDCN 2010, Kolkata, India, January 3-6,

work page 2010
[27]

Springer, 2010

Proceedings, volume 5935 of Lecture Notes in Computer Science, pages 42–53. Springer, 2010

work page 2010
[28]

Pease, R

M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228–234, April 1980

work page 1980
[29]

Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya. Asynchronous byzantine approximate consensus in directed networks. In Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing, PODC 2020. ACM, 2020

work page 2020
[30]

Pandu Rangan

Kannan Srinathan and C. Pandu Rangan. Possibility and complexity of probabilistic reliable communication in directed networks. In Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, PODC ’06, pages 265–274, New York, NY, USA, 2006. ACM

work page 2006
[31]

Lili Su and Nitin H. Vaidya. Reaching approximate byzantine consensus with multi-hop communication. Inf. Comput., 255:352–368, 2017

work page 2017
[32]

Lewis Tseng and Nitin H. Vaidya. Fault-tolerant consensus in directed graphs. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, pages 451–460, New York, NY, USA, 2015. ACM

work page 2015
[33]

Nitin H. Vaidya. Iterative Byzantine vector consensus in incomplete graphs. In In International Conference on Distributed Computing and Networking (ICDCN), January 2014

work page 2014
[34]

Vaidya and Vijay K

Nitin H. Vaidya and Vijay K. Garg. Byzantine vector consensus in complete graphs. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13, pages 65–73, New York, NY, USA, 2013. ACM

work page 2013
[35]

Vaidya, Lewis Tseng, and Guanfeng Liang

Nitin H. Vaidya, Lewis Tseng, and Guanfeng Liang. Iterative approximate Byzantine consensus in arbitrary directed graphs. In Proceedings of the thirty-first annual ACM symposium on Principles of distributed computing, PODC ’12. ACM, 2012

work page 2012
[36]

Condition A

Yungjung Yi, M. Gerla, and Taek Jin Kwon. Efficient flooding in ad hoc networks: a comparative performance study. In IEEE International Conference on Communications, 2003. ICC ’03., volume 2, pages 1059–1063 vol.2, 2003. 14 Nitin H. Vaidya and Lewis Tseng APPENDICES A Equivalence of Graph Conditions for Synchronous Consensus In this section, we prove Lemm...

work page 2003