Deterministic Algorithm for Coded Cooperative Data Exchange

Alex Sprintson; Parastoo Sadeghi; Graham Booker; Salim El Rouayheb

doi:10.1007/978-3-642-29222-4_20

Deterministic Algorithm for Coded Cooperative Data Exchange

Alex Sprintson, Parastoo Sadeghi, Graham Booker, Salim El Rouayheb

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

7 Citations (Scopus)

Abstract

We consider the problem of cooperative data exchange in a group of wireless clients. In this problem each client initially holds a subset of packets and needs to obtain all packets held by other clients. Each client can broadcast its own packets or a combinations thereof to other clients via an error-free broadcast channel. Assuming that clients know which packets are available to other clients, our goal is to minimize the total number of transmissions needed to satisfy the demands of all clients. We present a deterministic algorithm that computes an optimal solution to this problem in polynomial time.

Original language	English
Title of host publication	Quality, Reliability,Security and Robustness in Heterogeneous Networks - 7th Int. Conf. on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010 and DSRC 2010.
Pages	282-289
Number of pages	8
DOIs	https://doi.org/10.1007/978-3-642-29222-4_20
Publication status	Published - 2012
Event	7th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010, and Dedicated Short Range CommunicationsWorkshop, DSRC 2010 - Houston, TX, United States Duration: 17 Nov 2010 → 19 Nov 2010

Publication series

Name	Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST
Volume	74 LNICST
ISSN (Print)	1867-8211

Conference

Conference	7th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010, and Dedicated Short Range CommunicationsWorkshop, DSRC 2010
Country/Territory	United States
City	Houston, TX
Period	17/11/10 → 19/11/10

Access to Document

10.1007/978-3-642-29222-4_20

Cite this

Sprintson, A., Sadeghi, P., Booker, G., & El Rouayheb, S. (2012). Deterministic Algorithm for Coded Cooperative Data Exchange. In Quality, Reliability,Security and Robustness in Heterogeneous Networks - 7th Int. Conf. on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010 and DSRC 2010. (pp. 282-289). (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST; Vol. 74 LNICST). https://doi.org/10.1007/978-3-642-29222-4_20

Sprintson, Alex ; Sadeghi, Parastoo ; Booker, Graham et al. / Deterministic Algorithm for Coded Cooperative Data Exchange. Quality, Reliability,Security and Robustness in Heterogeneous Networks - 7th Int. Conf. on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010 and DSRC 2010.. 2012. pp. 282-289 (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST).

@inproceedings{02f3f21ceb0a457fb9f65df346fcc4aa,

title = "Deterministic Algorithm for Coded Cooperative Data Exchange",

abstract = "We consider the problem of cooperative data exchange in a group of wireless clients. In this problem each client initially holds a subset of packets and needs to obtain all packets held by other clients. Each client can broadcast its own packets or a combinations thereof to other clients via an error-free broadcast channel. Assuming that clients know which packets are available to other clients, our goal is to minimize the total number of transmissions needed to satisfy the demands of all clients. We present a deterministic algorithm that computes an optimal solution to this problem in polynomial time.",

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

year = "2012",

doi = "10.1007/978-3-642-29222-4_20",

language = "English",

isbn = "9783642292217",

series = "Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST",

pages = "282--289",

booktitle = "Quality, Reliability,Security and Robustness in Heterogeneous Networks - 7th Int. Conf. on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010 and DSRC 2010.",

note = "7th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010, and Dedicated Short Range CommunicationsWorkshop, DSRC 2010 ; Conference date: 17-11-2010 Through 19-11-2010",

}

Sprintson, A, Sadeghi, P, Booker, G & El Rouayheb, S 2012, Deterministic Algorithm for Coded Cooperative Data Exchange. in Quality, Reliability,Security and Robustness in Heterogeneous Networks - 7th Int. Conf. on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010 and DSRC 2010.. Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST, vol. 74 LNICST, pp. 282-289, 7th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010, and Dedicated Short Range CommunicationsWorkshop, DSRC 2010, Houston, TX, United States, 17/11/10. https://doi.org/10.1007/978-3-642-29222-4_20

Deterministic Algorithm for Coded Cooperative Data Exchange. / Sprintson, Alex; Sadeghi, Parastoo; Booker, Graham et al.
Quality, Reliability,Security and Robustness in Heterogeneous Networks - 7th Int. Conf. on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010 and DSRC 2010.. 2012. p. 282-289 (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST; Vol. 74 LNICST).

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

TY - GEN

T1 - Deterministic Algorithm for Coded Cooperative Data Exchange

AU - Sprintson, Alex

AU - Sadeghi, Parastoo

AU - Booker, Graham

AU - El Rouayheb, Salim

PY - 2012

Y1 - 2012

N2 - We consider the problem of cooperative data exchange in a group of wireless clients. In this problem each client initially holds a subset of packets and needs to obtain all packets held by other clients. Each client can broadcast its own packets or a combinations thereof to other clients via an error-free broadcast channel. Assuming that clients know which packets are available to other clients, our goal is to minimize the total number of transmissions needed to satisfy the demands of all clients. We present a deterministic algorithm that computes an optimal solution to this problem in polynomial time.

AB - We consider the problem of cooperative data exchange in a group of wireless clients. In this problem each client initially holds a subset of packets and needs to obtain all packets held by other clients. Each client can broadcast its own packets or a combinations thereof to other clients via an error-free broadcast channel. Assuming that clients know which packets are available to other clients, our goal is to minimize the total number of transmissions needed to satisfy the demands of all clients. We present a deterministic algorithm that computes an optimal solution to this problem in polynomial time.

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

U2 - 10.1007/978-3-642-29222-4_20

DO - 10.1007/978-3-642-29222-4_20

M3 - Conference contribution

SN - 9783642292217

T3 - Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST

SP - 282

EP - 289

BT - Quality, Reliability,Security and Robustness in Heterogeneous Networks - 7th Int. Conf. on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010 and DSRC 2010.

T2 - 7th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010, and Dedicated Short Range CommunicationsWorkshop, DSRC 2010

Y2 - 17 November 2010 through 19 November 2010

ER -

Sprintson A, Sadeghi P, Booker G, El Rouayheb S. Deterministic Algorithm for Coded Cooperative Data Exchange. In Quality, Reliability,Security and Robustness in Heterogeneous Networks - 7th Int. Conf. on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010 and DSRC 2010.. 2012. p. 282-289. (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST). doi: 10.1007/978-3-642-29222-4_20

Deterministic Algorithm for Coded Cooperative Data Exchange

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this