On coding for cooperative data exchange

Salim El Rouayheb; Alex Sprintson; Parastoo Sadeghi

doi:10.1109/ITWKSPS.2010.5503135

On coding for cooperative data exchange

Salim El Rouayheb^*, Alex Sprintson, Parastoo Sadeghi

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

106 Citations (Scopus)

Abstract

We consider the problem of data exchange by a group of closely-located wireless nodes. In this problem each node holds a set of packets and needs to obtain all the packets held by other nodes. Each of the nodes can broadcast the packets in its possession (or a combination thereof) via a noiseless broadcast channel of capacity one packet per channel use. The goal is to minimize the total number of transmissions needed to satisfy the demands of all the nodes, assuming that they can cooperate with each other and are fully aware of the packet sets available to other nodes. This problem arises in several practical settings, such as peer-to-peer systems and wireless data broadcast. In this paper, we establish upper and lower bounds on the optimal number of transmissions and present an efficient algorithm with provable performance guarantees. The effectiveness of our algorithms is established through numerical simulations.

Original language	English
Title of host publication	IEEE Information Theory Workshop 2010, ITW 2010
DOIs	https://doi.org/10.1109/ITWKSPS.2010.5503135
Publication status	Published - 2010
Event	IEEE Information Theory Workshop 2010, ITW 2010 - Cairo, Egypt Duration: 6 Jan 2010 → 8 Jan 2010

Publication series

Name	IEEE Information Theory Workshop 2010, ITW 2010

Conference

Conference	IEEE Information Theory Workshop 2010, ITW 2010
Country/Territory	Egypt
City	Cairo
Period	6/01/10 → 8/01/10

Access to Document

10.1109/ITWKSPS.2010.5503135

Cite this

@inproceedings{4968606066a94c38b4f64053566b9ea0,

title = "On coding for cooperative data exchange",

abstract = "We consider the problem of data exchange by a group of closely-located wireless nodes. In this problem each node holds a set of packets and needs to obtain all the packets held by other nodes. Each of the nodes can broadcast the packets in its possession (or a combination thereof) via a noiseless broadcast channel of capacity one packet per channel use. The goal is to minimize the total number of transmissions needed to satisfy the demands of all the nodes, assuming that they can cooperate with each other and are fully aware of the packet sets available to other nodes. This problem arises in several practical settings, such as peer-to-peer systems and wireless data broadcast. In this paper, we establish upper and lower bounds on the optimal number of transmissions and present an efficient algorithm with provable performance guarantees. The effectiveness of our algorithms is established through numerical simulations.",

author = "{El Rouayheb}, Salim and Alex Sprintson and Parastoo Sadeghi",

year = "2010",

doi = "10.1109/ITWKSPS.2010.5503135",

language = "English",

isbn = "9781424463725",

series = "IEEE Information Theory Workshop 2010, ITW 2010",

booktitle = "IEEE Information Theory Workshop 2010, ITW 2010",

note = "IEEE Information Theory Workshop 2010, ITW 2010 ; Conference date: 06-01-2010 Through 08-01-2010",

}

TY - GEN

T1 - On coding for cooperative data exchange

AU - El Rouayheb, Salim

AU - Sprintson, Alex

AU - Sadeghi, Parastoo

PY - 2010

Y1 - 2010

N2 - We consider the problem of data exchange by a group of closely-located wireless nodes. In this problem each node holds a set of packets and needs to obtain all the packets held by other nodes. Each of the nodes can broadcast the packets in its possession (or a combination thereof) via a noiseless broadcast channel of capacity one packet per channel use. The goal is to minimize the total number of transmissions needed to satisfy the demands of all the nodes, assuming that they can cooperate with each other and are fully aware of the packet sets available to other nodes. This problem arises in several practical settings, such as peer-to-peer systems and wireless data broadcast. In this paper, we establish upper and lower bounds on the optimal number of transmissions and present an efficient algorithm with provable performance guarantees. The effectiveness of our algorithms is established through numerical simulations.

AB - We consider the problem of data exchange by a group of closely-located wireless nodes. In this problem each node holds a set of packets and needs to obtain all the packets held by other nodes. Each of the nodes can broadcast the packets in its possession (or a combination thereof) via a noiseless broadcast channel of capacity one packet per channel use. The goal is to minimize the total number of transmissions needed to satisfy the demands of all the nodes, assuming that they can cooperate with each other and are fully aware of the packet sets available to other nodes. This problem arises in several practical settings, such as peer-to-peer systems and wireless data broadcast. In this paper, we establish upper and lower bounds on the optimal number of transmissions and present an efficient algorithm with provable performance guarantees. The effectiveness of our algorithms is established through numerical simulations.

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

U2 - 10.1109/ITWKSPS.2010.5503135

DO - 10.1109/ITWKSPS.2010.5503135

M3 - Conference contribution

SN - 9781424463725

T3 - IEEE Information Theory Workshop 2010, ITW 2010

BT - IEEE Information Theory Workshop 2010, ITW 2010

T2 - IEEE Information Theory Workshop 2010, ITW 2010

Y2 - 6 January 2010 through 8 January 2010

ER -

On coding for cooperative data exchange

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this