Paper 2025/931

Communication Depth in Multivalued Broadcast

Abstract

Synchronous protocols are a fundamental and widely studied model in distributed computing and cryptography. In this model, protocols proceed in rounds: at the beginning of each round, parties send messages, and all messages are guaranteed to be delivered before the round ends. The standard communication complexity of a synchronous protocol measures the total number of bits transmitted throughout the execution. However, this metric does not accurately reflect the protocol’s actual running time, since it ignores the inherent parallelism of synchronous communication. In particular, multiple parties may transmit simultaneously within the same round, and the duration of a round is determined not by the total communication volume, but by the longest transmission that must occur sequentially. To capture this aspect of synchronous computation, we introduce \emph{communication-depth}, a new complexity measure for synchronous protocols. Informally, communication-depth quantifies the amount of communication that lies on the protocol’s critical path, namely, the number of bits that must be transmitted sequentially and therefore determine the protocol’s execution time. The communication-depth of a protocol is defined as the sum, over all rounds, of the cost of each round. We consider two variants of round-cost capturing different types of parallel communication the network allows. In the \emph{simultaneous-parties} model, the cost of a round is the maximum number of bits any party sends or receives during that round. In the \emph{simultaneous-channels} model, the cost of a round is the maximum number of bits transmitted over any single channel during the round. We demonstrate the usefulness of communication-depth by fully characterizing the asymptotic complexity of multivalued synchronous broadcast. Perhaps surprisingly, while protocols for $\ell$-bit inputs with asymptotic optimal communication $O(\ell n)$ have been known for a long time, current protocols only achieve communication-depth $\Theta(\ell n)$ in the simultaneous-parties model and $\Theta(\ell)$ in the simultaneous-channels model. Our results provide a complete characterization of multivalued broadcast under communication-depth for both variants. On the negative side, we show that when $n - t = O(1)$, any protocol tolerating up to $t$ corrupt parties requires communication-depth $\Omega(\ell n)$ in the simultaneous-parties model and $\Omega(\ell)$ in the simultaneous-channels model. On the positive side, we show that when $n - t = \Theta(n)$, multivalued broadcast can be achieved with communication-depth $\Theta(\ell)$ in the simultaneous-parties model and $\Theta(\ell/n)$ in the simultaneous-channels model.

Note: Major revision