Cooperative data exchange with unreliable clients
Authors:
- 1 September 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 496-503
Abstract
Consider a set of clients in a broadcast network, each of which holds a subset of packets in the ground set X. In the (coded) cooperative data exchange problem, the clients need to recover all packets in X by exchanging coded packets over a lossless broadcast channel. Several previous works analyzed this problem under the assumption that each client initially holds a random subset of packets in X. In this paper we consider a generalization of this problem for settings in which an unknown (but of a certain size) subset of clients are unreliable and their packet transmissions are subject to arbitrary erasures. For the special case of one unreliable client, we derive a closed-form expression for the minimum number of transmissions required for each reliable client to obtain all packets held by other reliable clients (with probability approaching 1 as the number of packets tends to infinity). Furthermore, for the cases with more than one unreliable client, we provide an approximation solution in which the number of transmissions per packet is within an arbitrarily small additive factor from the value of the optimal solution.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Weakly secure data exchange with Generalized Reed Solomon codes2014
- Coded cooperative data exchange for a secret key2014
- Algorithms for weakly secure data exchange2013
- Weighted universal recovery, practical secrecy, and an efficient algorithm for solving both2011
- Deterministic algorithm for the cooperative data exchange problem2011
- A Generalized Model for Cost and Fairness Analysis in Coded Cooperative Data Exchange2011
- An algorithm for cooperative data exchange with cost criterion2011
- Optimal exchange of packets for universal recovery in broadcast networks2010
- Efficient universal recovery in broadcast networks2010
- Linear network codingIEEE Transactions on Information Theory, 2003