math.IT — Information Theory

Energy complexity and dissipation of noisy consensus

Contributed by Zhenyu Sun

We characterize the signal-energy complexity of distributed agreement over independent Gaussian point-to-point channels. For $n$ processes deciding $L$ 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 $\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<\varepsilon\leq1/8$. In the presence of $f\leq(1/3-\kappa)n$ static Byzantine faults, the same order is achieved in the polynomial-error regime $\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 $\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.