Optimal Linear Broadcast Rates of the Two-Sender Unicast Index Coding Problem with Fully-Participated Interactions

Chinmayananda Arunachala, Vaneet Aggarwal, B. Sundar RajanarXiv 2018 · arXiv

Abstract

This paper provides the first complete set of optimal linear broadcast rates and code constructions for the two-sender unicast index coding problem (TUICP) under "fully-participated interactions." By decomposing complex multi-sender problems into simpler single-sender sub-problems, the authors offer a definitive solution for a significant class of distributed communication scenarios, proving that linear codes are sufficient to achieve theoretical optima.

Introduction

The Index Coding Problem (ICP) is a fundamental challenge in network information theory, aiming to minimize broadcast transmissions by leveraging receivers' side-information. While the single-sender case is well-studied, modern distributed networks—such as distributed storage or cellular caching—frequently involve multiple senders. In a two-sender unicast index coding problem (TUICP), each sender possesses only a subset of the total messages, necessitating coordinated transmission strategies. This paper addresses a broad class of these problems where interactions between receiver groups are "fully-participated."

Problem Formulation and Interaction Digraphs

In TUICP, receivers are partitioned based on which sender knows their requested message: Sender 1 only ($D_1$), Sender 2 only ($D_2$), or both ($D_{\{1,2\}}$). "Fully-participated interactions" occur when side-information between these groups is complete: if any receiver in one group knows a message from another group, then all receivers in that group know all messages in the other.

To analyze these interactions, the authors utilize interaction digraphs ($\mathcal{H}$). The problem is classified into 64 distinct types of interaction digraphs, organized into Case I (acyclic) and Case II (cyclic).

Classification of the 64 distinct interaction digraph types for the two-sender problem.

Methodology: Sub-problem Decomposition

The core innovation lies in decomposing the complex two-sender problem into three simpler single-sender sub-problems ($D_1, D_2, D_{\{1,2\}}$). The authors demonstrate that the optimal broadcast rate of the entire system can be expressed as a function of the optimal rates of these sub-problems.

For cyclic cases (Case II), the authors employ interference alignment principles to establish lower bounds on signal dimensions. They further provide explicit linear code constructions, often involving XOR operations on codewords from sub-problems with appropriate zero-padding. This structural approach proves that linear codes are sufficient to achieve the theoretical optimum for this class of problems.

Key Results and Optimal Rates

The research culminates in a definitive mapping of optimal linear broadcast rates ($\beta_t$) for all 64 interaction cases. These results show that for fully-participated interactions, the global optimal rate is typically the sum or maximum of the sub-problem rates.

Table of optimal linear broadcast rates for Cases I and II-A through II-E.

Key findings include:

  • Case I & II-A: The optimal rate is the simple sum of sub-problem rates: $\beta_t = \beta_t(D_1) + \beta_t(D_2) + \beta_t(D_{\{1,2\}})$. In these structures, coordination offers no rate reduction.
  • Case II-B: The rate is $\max\{\beta_t(D_1) + \beta_t(D_2), \beta_t(D_{\{1,2\}})\}$, indicating that common messages can essentially be transmitted "for free" if the sender-specific requirements are sufficiently high.
  • Scalability: The authors successfully extended these two-sender results to $s$-sender problems, provided the interaction graph between senders remains acyclic or follows specific hierarchical structures.

Conclusion and Future Directions

This work offers a complete solution for TUICPs with fully-participated interactions, highlighting the power of decomposition and the sufficiency of linear codes. While this covers many structured network topologies, real-world "messy" side-information (partially-participated) remains an open challenge for certain cyclic cases. Future research will focus on extending these results to partially-participated interactions and exploring more complex multi-sender interaction topologies.

Summary updated

Abstract

The two-sender unicast index coding problem consists of finding optimal coded transmissions from the two senders which collectively know the messages demanded by all the receivers. Each receiver demands a unique message. One important class of this problem consists of the message sets at the senders and the side-information at the receivers satisfying \emph{fully-participated interactions}. This paper provides optimal linear broadcast rates and corresponding code constructions for all the possible cases of the two-sender unicast index coding problem with fully-participated interactions. The optimal linear broadcast rate and the corresponding code for the two-sender problem are given in terms of those of the three single-sender unicast problems associated with the two-sender problem. Optimal linear broadcast rates of two-sender problems with fully-participated interactions provide lower bounds for the optimal linear broadcast rates of many related two-sender problems with \emph{partially-participated interactions}. Proof techniques used to obtain the results for the two-sender problem are shown to be useful in obtaining the results for some cases of the multi-sender unicast index coding problem.
BibTeX
@misc{arunachala2018optimal,
  author = {Chinmayananda Arunachala and Vaneet Aggarwal and B. Sundar Rajan},
  title = {{Optimal Linear Broadcast Rates of the Two-Sender Unicast Index Coding Problem with Fully-Participated Interactions}},
  year = {2018},
  eprint = {1808.09775},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1808.09775},
}
Figure