TY - JOUR
T1 - Capacity Theorems for Distributed Index Coding
AU - Liu, Yucheng
AU - Sadeghi, Parastoo
AU - Arbabjolfaei, Fatemeh
AU - Kim, Young Han
N1 - Publisher Copyright:
© 1963-2012 IEEE.
PY - 2020/8
Y1 - 2020/8
N2 - In index coding, a server broadcasts multiple messages to their respective receivers, each with some side information that can be utilized to reduce the amount of communication from the server. Distributed index coding is an extension of index coding in which the messages are broadcast from multiple servers, each storing different subsets of the messages. In this paper, the optimal tradeoff among the message rates and the server broadcast rates, which is defined formally as the capacity region, is studied for a general distributed index coding problem. Inner and outer bounds on the capacity region are established that have matching sum-rates for all 218 non-isomorphic four-message problems with equal link capacities for all the links from servers to receivers. The proposed inner bound is built on a distributed composite coding scheme that outperforms the existing schemes by incorporating more flexible decoding configurations and enhanced fractional rate allocations into two-stage composite coding, a scheme that was originally introduced for centralized index coding. The proposed outer bound is built on the polymatroidal axioms of entropy, as well as functional dependences such as the fd-separation introduced by the multi-server nature of the problem. This outer bound utilizes general groupings of servers with different levels of granularity, which allows a natural tradeoff between computational complexity and tightness of the bound, and includes and improves upon all existing outer bounds for distributed index coding. Specific features of the proposed inner and outer bounds are demonstrated through concrete examples with four or five messages.
AB - In index coding, a server broadcasts multiple messages to their respective receivers, each with some side information that can be utilized to reduce the amount of communication from the server. Distributed index coding is an extension of index coding in which the messages are broadcast from multiple servers, each storing different subsets of the messages. In this paper, the optimal tradeoff among the message rates and the server broadcast rates, which is defined formally as the capacity region, is studied for a general distributed index coding problem. Inner and outer bounds on the capacity region are established that have matching sum-rates for all 218 non-isomorphic four-message problems with equal link capacities for all the links from servers to receivers. The proposed inner bound is built on a distributed composite coding scheme that outperforms the existing schemes by incorporating more flexible decoding configurations and enhanced fractional rate allocations into two-stage composite coding, a scheme that was originally introduced for centralized index coding. The proposed outer bound is built on the polymatroidal axioms of entropy, as well as functional dependences such as the fd-separation introduced by the multi-server nature of the problem. This outer bound utilizes general groupings of servers with different levels of granularity, which allows a natural tradeoff between computational complexity and tightness of the bound, and includes and improves upon all existing outer bounds for distributed index coding. Specific features of the proposed inner and outer bounds are demonstrated through concrete examples with four or five messages.
KW - Network coding
KW - Satellite broadcasting
KW - source coding
UR - http://www.scopus.com/inward/record.url?scp=85088891933&partnerID=8YFLogxK
U2 - 10.1109/TIT.2020.2977916
DO - 10.1109/TIT.2020.2977916
M3 - Article
SN - 0018-9448
VL - 66
SP - 4653
EP - 4680
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 8
M1 - 9022912
ER -