Deterministic Algorithm for Coded Cooperative Data Exchange

Alex Sprintson; Parastoo Sadeghi; Graham Booker; Salim Rouayheb

Quality, Reliability, Security and Robustness in Heterogeneous Networks. 7th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010, and Dedicated Short Range Communications Workshop, DSRC 2010, Houston, TX, USA, November 17-19, 2010, Revised Selected Papers

Research Article

Deterministic Algorithm for Coded Cooperative Data Exchange

Download

424 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1007/978-3-642-29222-4_20,
    author={Alex Sprintson and Parastoo Sadeghi and Graham Booker and Salim Rouayheb},
    title={Deterministic Algorithm for Coded Cooperative Data Exchange},
    proceedings={Quality, Reliability, Security and Robustness in Heterogeneous Networks. 7th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness, QShine 2010, and Dedicated Short Range Communications Workshop, DSRC 2010, Houston, TX, USA, November 17-19, 2010, Revised Selected Papers},
    proceedings_a={QSHINE},
    year={2012},
    month={10},
    keywords={},
    doi={10.1007/978-3-642-29222-4_20}
}

Alex Sprintson
Parastoo Sadeghi
Graham Booker
Salim Rouayheb
Year: 2012
Deterministic Algorithm for Coded Cooperative Data Exchange
QSHINE
Springer
DOI: 10.1007/978-3-642-29222-4_20

Alex Sprintson¹^,*, Parastoo Sadeghi²^,*, Graham Booker¹^,*, Salim Rouayheb³^,*

1: Texas A&M University
2: Australian National University
3: University of California

*Contact email: spalex@tamu.edu, parastoo.sadeghi@anu.edu.au, gbooker@tamu.edu, salim@eecs.berkeley.edu

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.

Published: 2012-10-16

: http://dx.doi.org/10.1007/978-3-642-29222-4_20