ECCC-Report TR15-092https://eccc.weizmann.ac.il/report/2015/092Comments and Revisions published for TR15-092en-usThu, 10 May 2018 22:05:48 +0300
Revision 2
| Compressing Communication in Distributed Protocols |
Yael Tauman Kalai,
Ilan Komargodski
https://eccc.weizmann.ac.il/report/2015/092#revision2 We show how to compress communication in selection protocols, where the goal is to agree on a sequence of random bits using only a broadcast channel. More specifically, we present a generic method for converting any selection protocol, into another selection protocol where each message is short while preserving the same number of rounds, the same output distribution, and the same resilience to error. Assuming that the output of the protocol lies in some universe of size $M$, in our resulting protocol each message consists of only $polylog(M,n,d)$ many bits, where $n$ is the number of parties and $d$ is the number of rounds. Our transformation works in the presence of either static or adaptive Byzantine faults.
As a corollary, we conclude that for any $poly(n)$-round collective coin-flipping protocol, leader election protocol, or general selection protocols, messages of length $polylog(n)$ suffice (in the presence of either static or adaptive Byzantine faults).
Thu, 10 May 2018 22:05:48 +0300https://eccc.weizmann.ac.il/report/2015/092#revision2
Revision 1
| Compressing Communication in Distributed Protocols |
Yael Tauman Kalai,
Ilan Komargodski
https://eccc.weizmann.ac.il/report/2015/092#revision1We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of rounds, the same communication pattern, the same output distribution, and the same resilience to error. Assuming that the output lies in some universe of size $M$, in our resulting protocol each message consists of only $\polylog(M,n,d)$ many bits, where $n$ is the number of parties and $d$ is the number of rounds. Our transformation works in the full information model, in the presence of either static or adaptive Byzantine faults.
In particular, our result implies that for any such $\poly(n)$-round distributed protocol which generates outputs in a universe of size $\poly(n)$, long messages are not needed, and messages of length $\polylog(n)$ suffice. In other words, in this regime, any distributed task that can be solved in the $\mathcal{LOCAL}$ model, can also be solved in the $\mathcal{CONGEST}$ model with the same round complexity and security guarantees.
As a corollary, we conclude that for any $\poly(n)$-round collective coin-flipping protocol, leader election protocol, or selection protocols, messages of length $\polylog(n)$ suffice (in the presence of either static or adaptive Byzantine faults).Tue, 04 Aug 2015 12:22:21 +0300https://eccc.weizmann.ac.il/report/2015/092#revision1
Paper TR15-092
| Compressing Communication in Distributed Protocols |
Yael Tauman Kalai,
Ilan Komargodski
https://eccc.weizmann.ac.il/report/2015/092We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of rounds, the same communication pattern, the same output distribution, and the same resilience to error. Assuming that the output lies in some universe of size $M$, in our resulting protocol each message consists of only $\polylog(M,n,d)$ many bits, where $n$ is the number of parties and $d$ is the number of rounds. Our transformation works in the full information model, in the presence of either static or adaptive Byzantine faults.
In particular, our result implies that for any such $\poly(n)$-round distributed protocol which generates outputs in a universe of size $\poly(n)$, long messages are not needed, and messages of length $\polylog(n)$ suffice. In other words, in this regime, any distributed task that can be solved in the $\mathcal{LOCAL}$ model, can also be solved in the $\mathcal{CONGEST}$ model with the same round complexity and security guarantees.
As a corollary, we conclude that for any $\poly(n)$-round collective coin-flipping protocol, leader election protocol, or selection protocols, messages of length $\polylog(n)$ suffice (in the presence of either static or adaptive Byzantine faults).Mon, 08 Jun 2015 03:43:28 +0300https://eccc.weizmann.ac.il/report/2015/092