The cooperative data exchange problem is studied for the fully connected network. In this problem, each node initially only possesses a subset of the @math packets making up the file. Nodes make broadcast transmissions that are received by all other nodes. The goal is for each node to recover the full file. In this paper, we present a polynomial-time deterministic algorithm to compute the optimal (i.e., minimal) number of required broadcast transmissions and to determine the precise transmissions to be made by the nodes. A particular feature of our approach is that each of the @math transmissions is a linear combination of exactly @math packets, and we show how to optimally choose the value of @math We also show how the coefficients of these linear combinations can be chosen by leveraging a connection to Maximum Distance Separable (MDS) codes. Moreover, we show that our method can be used to solve cooperative data exchange problems with weighted cost as well as the so-called successive local omniscience problem.
For solving the CCDE problem, only knowing the minimal number of required transmissions is not enough. It is also necessary to design the coding scheme. Given the total number of transmissions, designing the coding scheme is a multicast network code construction problem and can be solved by the polynomial time algorithm proposed by Jaggi in @cite_8 .
@cite_8
2123562143
The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to re-encode the information they receive. We demonstrate examples of networks where the achievable rates obtained by coding at intermediate nodes are arbitrarily larger than if coding is not allowed. We give deterministic polynomial time algorithms and even faster randomized algorithms for designing linear codes for directed acyclic graphs with edges of unit capacity. We extend these algorithms to integer capacities and to codes that are tolerant to edge failures.