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).
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.
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