TY - JOUR

T1 - Coded Cooperative Data Exchange Problem for General Topologies

AU - Gonen, Mira

AU - Langberg, Michael

N1 - Publisher Copyright:
© 2014 IEEE.

PY - 2015/10

Y1 - 2015/10

N2 - We consider the coded cooperative data exchange problem for general graphs, both undirected and directed. In this problem, given a graph G=(V,E) representing clients in a broadcast network, each of which initially hold a (not necessarily disjoint) set of information packets; one wishes to design a communication scheme in which eventually all clients will hold all the packets of the network. Communication is performed in rounds, where in each round a single client broadcasts a single (possibly encoded) information packet to its neighbors in G. The objective is to design a broadcast scheme that satisfies all clients with the minimum number of broadcast rounds. The coded cooperative data exchange problem has seen significant research over the last few years; mostly when the graph G is the complete broadcast graph in which each client is adjacent to all other clients in the network, but also on general topologies, both in the fractional and integral setting. In this paper, we focus on the integral setting in general topologies G , both undirected and directed. For undirected graphs, we tie the coded cooperative data exchange problem on G to variants of the dominating set problem and in such show that solving the problem exactly or even approximately within a multiplicative factor of log|V| is intractable (i.e., NP-hard). We then turn to study efficient data exchange schemes for undirected topologies yielding a number of communication rounds comparable with our intractability result. Last, we tie the coded cooperative data exchange problem for directed topologies to the directed Steiner tree problem, yielding efficient data exchange approximation schemes. Our communication schemes do not involve encoding, and in such yield bounds on the coding advantage in the setting at hand.

AB - We consider the coded cooperative data exchange problem for general graphs, both undirected and directed. In this problem, given a graph G=(V,E) representing clients in a broadcast network, each of which initially hold a (not necessarily disjoint) set of information packets; one wishes to design a communication scheme in which eventually all clients will hold all the packets of the network. Communication is performed in rounds, where in each round a single client broadcasts a single (possibly encoded) information packet to its neighbors in G. The objective is to design a broadcast scheme that satisfies all clients with the minimum number of broadcast rounds. The coded cooperative data exchange problem has seen significant research over the last few years; mostly when the graph G is the complete broadcast graph in which each client is adjacent to all other clients in the network, but also on general topologies, both in the fractional and integral setting. In this paper, we focus on the integral setting in general topologies G , both undirected and directed. For undirected graphs, we tie the coded cooperative data exchange problem on G to variants of the dominating set problem and in such show that solving the problem exactly or even approximately within a multiplicative factor of log|V| is intractable (i.e., NP-hard). We then turn to study efficient data exchange schemes for undirected topologies yielding a number of communication rounds comparable with our intractability result. Last, we tie the coded cooperative data exchange problem for directed topologies to the directed Steiner tree problem, yielding efficient data exchange approximation schemes. Our communication schemes do not involve encoding, and in such yield bounds on the coding advantage in the setting at hand.

KW - Communication networks

KW - Cooperative communication

KW - Information exchange

KW - Network Coding

UR - http://www.scopus.com/inward/record.url?scp=84959440743&partnerID=8YFLogxK

U2 - 10.1109/TIT.2015.2457443

DO - 10.1109/TIT.2015.2457443

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84959440743

SN - 0018-9448

VL - 61

SP - 5656

EP - 5669

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 10

M1 - 7161355

ER -