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.
The CDE problem for the fully connected network is also related to the secret key generation problem, which was introduced in @cite_17 and was formulated as a maximization problem over all partitions of the node set. Tyagi @cite_4 leveraged this to derive an algorithm which achieves local omniscience in each step and outputs a sub-optimal solution. The weakly secure data exchange problem was introduced in @cite_7 . The goal is to achieve universal recovery while revealing as little information as possible. In contrast to the coding scheme in @cite_7 in which each transmission is a linear combination of as many packet as possible, our scheme considers a fixed number of packets for every transmission. In general cases, the communication rate in the secret key generation problem is asymptotic which makes the problem NP-hard, while the minimal number of required transmissions in the CDE problem is integer so that it can be solved by polynomial-time algorithms (as previously mentioned).
@cite_4 @cite_7 @cite_17
2963017858 2050536468 2154832352
Multiple parties observing correlated data seek to recover each other’s data and attain omniscience. To that end, they communicate interactively over a noiseless broadcast channel - each bit transmitted over this channel is received by all the parties. We give a universal interactive communication protocol, termed the recursive data exchange protocol (RDE), which attains omniscience for any sequence of data observed by the parties and provide an individual sequence guarantee of performance. As a by-product, for observations of length @math , we show the universal rate optimality of RDE up to an @math term in a generative setting where the data sequence is independent and identically distributed (in time). Furthermore, drawing on the duality between omniscience and secret key agreement due to Csiszar and Narayan, we obtain a universal protocol for generating a multiparty secret key of rate at most @math less than the maximum rate possible. A key feature of RDE is its recursive structure whereby when a subset @math of parties recover each-other’s data, the rates appear as if the parties have been executing the protocol in an alternative model where the parties in @math are collocated. We consider the problem of direct data exchange among a group of wireless clients in the presence of an eavesdropper. An instance of this problem includes a set of packets X and a set of clients, such that each client has an access to a subset of packets and requests the rest of the packets in X. The clients use a lossless broadcast channel to transmit packets to other clients in the group. All transmitted packets can be observed by an eavesdropper that might have prior side information about the packets exchanged by the clients. Our goal is to construct a coding scheme that prevents the eavesdropper from decoding any individual packet in X (beyond those it already knowns). In weakly secure schemes, the more packets the eavesdropper has, the harder it is to construct a scheme that prevents the eavesdropper from obtaining additional packets. Thus, it is natural to measure the degree of secrecy by the maximum number of packets that can be held by the eavesdropper. Accordingly, our goal is to construct a coding scheme that can handle an eavesdropper that has as many packets as possible. We also present randomized and deterministic solutions for this problem and analyze their performance. We also establish a tight upper bound on the maximum degree of secrecy that a weakly secure scheme can provide for each instance of the problem. We derive single-letter characterizations of (strong) secrecy capacities for models with an arbitrary number of terminals, each of which observes a distinct component of a discrete memoryless multiple source, with unrestricted and interactive public communication permitted between the terminals. A subset of these terminals can serve as helpers for the remaining terminals in generating secrecy. According to the extent of an eavesdropper's knowledge, three kinds of secrecy capacity are considered: secret key (SK), private key (PK), and wiretap secret key (WSK) capacity. The characterizations of the SK and PK capacities highlight the innate connections between secrecy generation and multiterminal source coding without secrecy requirements. A general upper bound for WSK capacity is derived which is tight in the case when the eavesdropper can wiretap noisy versions of the components of the underlying multiple source, provided randomization is permitted at the terminals. These secrecy capacities are seen to be achievable with noninteractive communication between the terminals. The achievability results are also shown to be universal.