Effect of protocol ordering on multiparty comm. complexity

Question

Brief Background

In Multi-Party Protocols by Chandra, Lipton, and Furst [CFL83], a Ramsey-theoretic proof is used to show a lower bound (and later, a matching upper bound) for the predicate Exactly-$n$ in the NOF multiparty communication complexity model. From the paragraph at the top of the second column of Page 1, we can see that they define the model such that the communication is strictly cyclic: e.g., for parties $P_0, P_1, P_2$, $P_0$ broadcasts at time $t=0$, $P_1$ broadcasts at time $t=1$, $P_2$ broadcasts at time $t=2$, then $P_0$ broadcasts at time $t=3$, and so on.

In most other papers, this cyclic ordering restriction is not made. For (arbitrary) example, in Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity by Beame, David, Pitassi, and Woelfel [BDPW07], a counting argument over protocols separates $\bf{RP}^{cc}_k$ from $\bf{P}^{cc}_k$. By their definition, "a protocol specifies, for every possible [public] blackboard contents [i.e., broadcast history] whether or not the communication is over, the output if over and the next player to speak if not." (emphasis added)

Importantly, the proof technique in [CFL83] appears (to my eyes) to crucially depend on the parties speaking in a cyclic/modular fashion.

Question

Allow me to play Devil's Advocate:

Doesn't the lower bound proof of [CFL83] break if we allow the parties to speak in an ordering specified by the protocol? More specifically, is it possible there could there be a protocol with a different communication pattern than cyclic for Exactly-$n$ in the NOF model that costs less than the $\log(\chi_k(n))$ lower bound given in the paper?

Or more generally -- what's going on here? Why is one (highly cited) paper (I use the following very liberally) "allowed" to restrict the possible protocols to round-robin communication patterns only?

Answer 1

Any protocol $\pi$ can be modified into an equivalent protocol $\hat\pi$ that has the special "round-robin" communication pattern. The modification is as follows: Whenever party $i$ generates an output in $\pi$, it holds it in a buffer until party $i-1$ has spoken. After party $i-1$ speaks, party $i$ either releases its buffer or broadcasts a "dummy" (or empty) message if there is nothing in the buffer.

The conversion of $\pi$ into $\hat\pi$ is without loss of generality, with respect to the correctness and security properties of the protocol. Whether it incurs a loss of generality with respect to communication complexity depends on whether the model allows "empty" messages. You should see whether the proof technique in this paper assumes that parties can broadcast only non-empty messages. If empty messages are allowed, then $\hat\pi$ has the same communication complexity as $\pi$.