Approximation algorithms for erasure correcting Data Exchange

In the Cooperative Data Exchange (CDE) problem, a group of wireless clients need to exchange data over a shared broadcast channel, such that at the end of the transfer all clients have access to all packets held by other clients. In this paper, we focus on the robust version of the problem in which the clients must be able to complete the transfer even if one of the clients fails before the transfer is complete. The event of a client failure is referred to as an erasure. We show that, while the original CDE problem can be solved in polynomial time, the robust version of the problem is NP-hard, even in the special case when robustness to a single failure is required. Focusing on the practically important special case of a single failure, we establish an approximation algorithm for this problem that can find a solution within a constant factor of the optimum. Our simulation studies show that the algorithm is able to find solutions that are very close to the optimum.