Name
Abstract | ||
|---|---|---|
Alice and Bob are connected via a two-way channel, and Alice wants to send a message of L bits to Bob. An adversary flips an arbitrary but finite number of bits, T, on the channel. This adversary knows our algorithm and Alice's message, but does not know any private random bits generated by Alice or Bob, nor the bits sent over the channel, except when these bits can be predicted by knowledge of Alice's message or our algorithm. We want Bob to receive Alice's message and for both players to terminate, with error probability at most delta > 0, where delta is a parameter known to both Alice and Bob. Unfortunately, the value T is unknown in advance to either Alice or Bob, and the value L is unknown in advance to Bob. We describe an algorithm to solve the above problem while sending an expected L + O (T + min (T + 1, L/log L) log (L/delta)) bits. A special case is when delta = O(1/ L-c), for some constant c. Then when T = o(L/log L), the expected number of bits sent is L + o(L), and when T = Omega(L), the expected number of bits sent is L + O(T), which is asymptotically optimal. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3154273.3154318 | ICDCN'18: PROCEEDINGS OF THE 19TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING AND NETWORKING |
Keywords | Field | DocType |
Reed Solomon Codes,Interactive Communication,Adversary,Polynomial,AMD Codes,Error Correction Codes,Fingerprinting | Discrete mathematics,Finite set,Alice and Bob,Computer science,Communication channel,Theoretical computer science,Expected value,Omega,Probability of error,Asymptotically optimal algorithm | Conference |
Citations | PageRank | References |
0 | 0.34 | 22 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abhinav Aggarwal | 1 | 0 | 1.69 |
| Varsha Dani | 2 | 432 | 40.05 |
| Thomas P. Hayes | 3 | 659 | 54.21 |
| Jared Saia | 4 | 1019 | 96.95 |