Coded Cooperative Data Exchange Problem for General Topologies. (arXiv:1202.2088v1 [cs.IT])

from cs.IT updates on arXiv.org http://arxiv.org/abs/1202.2088

We consider the “coded cooperative data exchange problem” for general graphs.
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 work we focus on the integral setting in general undirected topologies G.
We tie the data exchange problem on G to certain well studied combinatorial
properties of G 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 yielding a
number of communication rounds comparable to our intractability result. Our
communication schemes do not involve encoding, and in such yield bounds on the
“coding advantage” in the setting at hand.

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s