HEXAGONbeta

Energy complexity and dissipation of noisy consensus

Primarily human-written textHuman understanding: all partsmath.IT — Information Theorymath.MP — Mathematical Physicscs.CC — Computational Complexity

Contributed by Zhenyu Sun ↗

Version 1 / Nov 11, 2026 / CC BY 4.0

Abstract

We characterize the signal-energy complexity of distributed agreement over independent Gaussian point-to-point channels. For nn processes deciding LL binary coordinates under coordinatewise unanimity validity and a joint failure probability of at most ε\varepsilon, every finite causal protocol requires a worst-input expected signal energy of Ω(N0n[L+ln⁡(n/ε)])\Omega(N_0n[L+\ln(n/\varepsilon)]). This lower bound combines two distinct mechanisms: an exact relative-entropy identity for locally interchanged reception histories yields the reliability term even in the presence of shared randomness and active noisy feedback, while a coordinatewise direct-sum argument establishes the payload term. In the fault-free setting, a deterministic fixed-leader protocol attains this optimal order for all 0<ε≤1/80<\varepsilon\leq1/8. In the presence of f≤(1/3−κ)nf\leq(1/3-\kappa)n static Byzantine faults, the same order is achieved in the polynomial-error regime ε≥n−a\varepsilon\geq n^{-a} via public committee sampling and robust joint decoding within explicit finite storage and computation budgets. Consequently, batching amortizes the reliability overhead, yielding an energy cost of Θ(N0n[1+L−1ln⁡(n/ε)])\Theta(N_0n[1+L^{-1}\ln(n/\varepsilon)]) per coordinate. We then connect this communication optimum to physical dissipation through a stochastic-thermodynamic model of a thermal channel port. Under a non-recovering mode replacement interface, the communication converse translates directly into lower bounds on entropy production and, when the endpoint mean internal energies agree, cyclic work. When work recovery is permitted prior to mode reset, we derive the exact minimum reset entropy production within a bounded-displacement control class as a function of the information accessible to the recovery controller, thereby separating the fundamental communication cost from its control-dependent thermodynamic realization.

Provenance statement

Generative AI tools assisted with mathematical exploration, manuscript drafting and translation, and numerical verification scripts. The author has checked and understood all parts of the manuscript. The accompanying Python scripts provide finite consistency checks, not formal proof verification.

References

  1. Abraham, Ittai; Chan, T.-H. Hubert; Dolev, Danny; Nayak, Kartik; Pass, Rafael; Ren, Ling; Shi, Elaine. Communication Complexity of Byzantine Agreement, Revisited. Distributed Computing, vol. 36, no. 1, pp. 3–28. 2023DOI
  2. Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D. An Information Statistics Approach to Data Stream and Communication Complexity. Journal of Computer and System Sciences, vol. 68, no. 4, pp. 702–732. 2004DOI
  3. Bennett, Charles H. Logical Reversibility of Computation. IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532. 1973DOI
  4. Berman, Piotr; Garay, Juan A.; Perry, Kenneth J. Towards Optimal Distributed Consensus. Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 410–415. 1989DOI
  5. Bonneau, Joseph; Bünz, Benedikt; Christ, Miranda; Efron, Yuval. How Much Public Randomness Do Modern Consensus Protocols Need?. 7th Conference on Advances in Financial Technologies (AFT 2025), vol. 354, pp. 12:1–12:19. 2025DOI
  6. Budish, Eric; Lewis-Pye, Andrew; Roughgarden, Tim. The Economic Limits of Permissionless Consensus. SIAM Journal on Computing, vol. 55, no. 4, pp. 622–670. 2026DOI
  7. Clementi, Andrea; Gualà, Luciano; Natale, Emanuele; Pasquale, Francesco; Scornavacca, Giacomo; Trevisan, Luca. Consensus vs Broadcast, with and Without Noise. 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), vol. 151, pp. 42:1–42:13. 2020DOI
  8. Dechant, Andreas. Minimum Entropy Production, Detailed Balance and Wasserstein Distance for Continuous-Time Markov Processes. Journal of Physics A: Mathematical and Theoretical, vol. 55, pp. 094001. 2022DOI
  9. Esposito, Massimiliano; Lindenberg, Katja; Van den Broeck, Christian. Entropy Production as Correlation Between System and Reservoir. New Journal of Physics, vol. 12, pp. 013013. 2010DOI
  10. Hoeffding, Wassily. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, vol. 58, no. 301, pp. 13–30. 1963DOI
Show all 21 referencesShow fewer references
  1. Kim, Young-Han; Lapidoth, Amos; Weissman, Tsachy. Error Exponents for the Gaussian Channel with Active Noisy Feedback. IEEE Transactions on Information Theory, vol. 57, no. 3, pp. 1223–1236. 2011DOI
  2. Kolchinsky, Artemy; Wolpert, David H. Work, Entropy Production, and Thermodynamics of Information under Protocol Constraints. Physical Review X, vol. 11, pp. 041024. 2021DOI
  3. Komatovic, Jovan; Lewis-Pye, Andrew; Neu, Joachim; Roughgarden, Tim; Tas, Ertem Nusret. From Permissioned to Proof-of-Stake Consensus. 7th Conference on Advances in Financial Technologies (AFT 2025), vol. 354, pp. 18:1–18:26. 2025DOI
  4. Landauer, Rolf. Irreversibility and Heat Generation in the Computing Process. IBM Journal of Research and Development, vol. 5, no. 3, pp. 183–191. 1961DOI
  5. Landauer, Rolf. Minimal Energy Requirements in Communication. Science, vol. 272, no. 5270, pp. 1914–1918. 1996DOI
  6. Lewis-Pye, Andrew; Roughgarden, Tim. Permissionless Consensus. 2023. arXiv:2304.14701link
  7. Meir, Shachar; Mirault, Hugo; Peleg, David; Robinson, Peter. Time-Optimal and Energy-Efficient Deterministic Consensus. 29th International Conference on Principles of Distributed Systems (OPODIS 2025), vol. 361, pp. 15:1–15:16. 2026DOI
  8. Polyanskiy, Yury; Poor, H. Vincent; Verdú, Sergio. Minimum Energy to Send kk Bits Through the Gaussian Channel With and Without Feedback. IEEE Transactions on Information Theory, vol. 57, no. 8, pp. 4880–4902. 2011DOI
  9. Shiraishi, Naoto; Funo, Ken; Saito, Keiji. Speed Limit for Classical Stochastic Processes. Physical Review Letters, vol. 121, pp. 070601. 2018DOI
  10. Yadav, Abhishek; Wolpert, David. Minimal Thermodynamic Cost of Communication. Physical Review Research, vol. 7, pp. 043324. 2025DOI
  11. Zhang, Shou-Cheng. In Math We Trust: Tsinghua x-lab lecture. 2018. In Chinese; republication dated 23 May 2018. Accessed 28 October 2026. Published lecture transcript, Big Data Digest; reproduced by Tencent Cloud Developer Communitylink

Version history

  1. v1 · 24 pagesSubmitted by Zhenyu SunInitial depositCurrentNov 10, 2026