Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with distributed computing:
TR05-110 | 3rd October 2005
Saurabh Sanghvi, Salil Vadhan

The Round Complexity of Two-Party Random Selection

We study the round complexity of two-party protocols for
generating a random $n$-bit string such that the output is
guaranteed to have bounded bias (according to some measure) even
if one of the two parties deviates from the protocol (even using
unlimited computational resources). Specifically, we require that
the output's ... more >>>

TR06-026 | 27th February 2006
Ronen Gradwohl, Salil Vadhan, David Zuckerman

Random Selection with an Adversarial Majority

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>

TR06-028 | 21st February 2006
Jonathan Katz, Chiu-Yuen Koo

On Expected Constant-Round Protocols for Byzantine Agreement

In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the ... more >>>

TR15-092 | 31st May 2015
Yael Tauman Kalai, Ilan Komargodski

Compressing Communication in Distributed Protocols

Revisions: 2

We 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 ... more >>>

TR16-130 | 11th August 2016
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

Tight Network Topology Dependent Bounds on Rounds of Communication

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent ... more >>>

ISSN 1433-8092 | Imprint