Paper Info
Title
A Scalable Algorithm For Multiparty Interactive Communication With Private Channels
Abstract
A group of n players wants to run a distributed protocol P over a network where communication occurs via private point-to-point channels. Unfortunately, an adversary, who knows P, is able to maliciously Yip bits on the channels. Can we efficiently simulate P in the presence of such an adversary?We show that this is possible, even when L, the number of bits sent in P, andT, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of P, P' such that 1) P' fails with probability at most delta, for any delta > 0; and 2) P' sends (O) over tilde (L+T ) bits, where the (O) over tilde notation hides a log (nL/delta) term multiplying L. Critically, our result requires that P be a protocol that runs correctly in an asynchronous network; in contrast, our protocol P' must run in a synchronous network.Additionally, we show how to improve this result when the average message size is not constant. In particular, we show how to create a protocol P' that sends O(L(1 + (1/alpha) log (nL/delta)) + T) bits, where alpha is the average message size. This new P' is adaptive in that it does not require a priori knowledge of alpha. We note that if alpha is Omega(log(nL/delta)),then this improved algorithm sends only O(L+T) bits, and is therefore within a constant factor of optimal.
Year
DOI
Venue
2020
10.1145/3369740.3369771
PROCEEDINGS OF THE 21ST INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING AND NETWORKING (ICDCN 2020)
Keywords
Field
DocType
Interactive Communication, Private Channels, Resource Competitive Analysis
Computer science,Computer network,Communication channel,Scalable algorithms,Distributed computing
Conference
Citations 
PageRank 
References 
0
0.34
0
Authors
4
Name
Order
Citations
PageRank
Abhinav Aggarwal101.69
Varsha Dani243240.05
Thomas P. Hayes365954.21
Jared Saia4101996.95