<p>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.</p>

<p>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 <em>communication complexity</em> 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$.</p>

CC BY-SA 3.0
2011-06-21T04:06:13.993Z
Hmm. The idea of a buffer had occurred to me, but not the idea of (effectively) broadcasting the empty string $\epsilon$ such that it won't count w.r.t. the comm complexity. I'll need to go stare at the lemmas in [CFL83] and see if it follows.
Daniel Apon
CC BY-SA 3.0
2011-06-21T03:56:33.370Z
2011-06-21T03:56:33.370Z
mikero
<p><strong>Brief Background</strong></p>

<p>In <em>Multi-Party Protocols</em> by Chandra, Lipton, and Furst [<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.62.5475&amp;rep=rep1&amp;type=pdf" rel="nofollow">CFL83</a>], 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.</p>

<p>In most other papers, this cyclic ordering restriction is not made. For (arbitrary) example, in <em>Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity</em> by Beame, David, Pitassi, and Woelfel [<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.9866&amp;rep=rep1&amp;type=pdf" rel="nofollow">BDPW07</a>], a counting argument over protocols separates $\bf{RP}^{cc}_k$ from $\bf{P}^{cc}_k$. By their definition, "a <em>protocol</em> specifies, for every possible [public] blackboard contents [i.e., broadcast history] whether or not the communication is over, the output if over <strong>and the next player to speak if not</strong>." (<em>emphasis added</em>)</p>

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

<p><strong>Question</strong></p>

<p>Allow me to play Devil's Advocate:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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?</p>

<communication-complexity>
Effect of protocol ordering on multiparty comm. complexity
Daniel Apon
# Effect of protocol ordering on multiparty comm. complexity

(Asked by: username_0 on 2011-06-21)

**Brief Background**

In *Multi-Party Protocols* by Chandra, Lipton, and Furst [[CFL83](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.62.5475&rep=rep1&type=pdf)], 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.9866&rep=rep1&type=pdf)], 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?

**Tags:** communication-complexity


---

## 1 answers

### Answer by username_1 on 2011-06-21. Score: 5 | Accepted answer

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$.

> **Comments:**
> **username_0**: Hmm. The idea of a buffer had occurred to me, but not the idea of (effectively) broadcasting the empty string $\epsilon$ such that it won't count w.r.t. the comm complexity. I'll need to go stare at the lemmas in [CFL83] and see if it follows.  

---

