Interactive communication for data exchange

Himanshu Tyagi, Pramod Viswanath, Shun Watanabe

Research output: Contribution to journalArticle

Abstract

Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.

Original languageEnglish (US)
Pages (from-to)26-37
Number of pages12
JournalIEEE Transactions on Information Theory
Volume64
Issue number1
DOIs
StatePublished - Jan 1 2018

Fingerprint

data exchange
Electronic data interchange
Random variables
communication
Communication
interaction

Keywords

  • Data exchange
  • Interactive communication
  • Omniscience
  • Secret key agreement

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this

Interactive communication for data exchange. / Tyagi, Himanshu; Viswanath, Pramod; Watanabe, Shun.

In: IEEE Transactions on Information Theory, Vol. 64, No. 1, 01.01.2018, p. 26-37.

Research output: Contribution to journalArticle

Tyagi, Himanshu ; Viswanath, Pramod ; Watanabe, Shun. / Interactive communication for data exchange. In: IEEE Transactions on Information Theory. 2018 ; Vol. 64, No. 1. pp. 26-37.
@article{8e625bd5cc8641a7ab0193e7df839b98,
title = "Interactive communication for data exchange",
abstract = "Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.",
keywords = "Data exchange, Interactive communication, Omniscience, Secret key agreement",
author = "Himanshu Tyagi and Pramod Viswanath and Shun Watanabe",
year = "2018",
month = "1",
day = "1",
doi = "10.1109/TIT.2017.2769124",
language = "English (US)",
volume = "64",
pages = "26--37",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "1",

}

TY - JOUR

T1 - Interactive communication for data exchange

AU - Tyagi, Himanshu

AU - Viswanath, Pramod

AU - Watanabe, Shun

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.

AB - Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.

KW - Data exchange

KW - Interactive communication

KW - Omniscience

KW - Secret key agreement

UR - http://www.scopus.com/inward/record.url?scp=85032732128&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85032732128&partnerID=8YFLogxK

U2 - 10.1109/TIT.2017.2769124

DO - 10.1109/TIT.2017.2769124

M3 - Article

AN - SCOPUS:85032732128

VL - 64

SP - 26

EP - 37

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 1

ER -