On the Privacy-Robustness Trade-Off in Distributed Average Consensus

Distributed consensus algorithms face a dual challenge in modern networked systems: safeguarding sensitive data through privacy-preserving mechanisms while maintaining robustness against adversarial nodes (e.g., Byzantine faults). While prior work addresses these goals separately, their interplay remains poorly understood, particularly in scenarios where output accuracy must be preserved. In this work, we reconcile these objectives by integrating a subspace perturbation framework, which guarantees privacy by confining noise to redundant network subspaces, with a median absolute deviation (MAD)-based thresholding mechanism to detect active adversarial nodes transmitting corrupted data. Through in-depth analysis, we demonstrate that enhancing privacy via subspace perturbation inherently limits the discriminative power of MAD-based detection, as adversarial updates become statistically indistinguishable from privacy-preserving perturbations. Numerical simulations quantify this tension, demonstrating that as privacy guarantees strengthen, the ability to detect active adversaries diminishes. These findings highlight a core challenge in distributed consensus—achieving both strong privacy and Byzantine robustness simultaneously is inherently difficult.