Abstract
Due to the large size of wireless networks, it is often impractical for nodes to track changes in the complete network state. As a result, nodes have to make distributed decisions about their transmission and reception parameters based on their local view of the network. In this paper, we characterize the impact of distributed decisions on the global network performance in terms of achievable sum-rates. We first formalize the concept of local view by proposing a protocol abstraction using the concept of local message passing. In the proposed protocol, nodes forward information about the network state to other neighboring nodes, thereby allowing network state information to trickle to all the nodes. The protocol proceeds in rounds, where all transmitters send a message followed by a message by all receivers. The number of rounds then provides a natural metric to quantify the extent of local information at each node. We next study three network connectivities, Z-channel, a three-user double Z-channel and a reduced-parametrization $K$-user stacked Z-channel. In each case, we characterize achievable sum-rate with partial message passing leading to three main results. First, in many cases, nodes can make distributed decisions with only local information about the network and can still achieve the same sum-capacity as can be attained with global information irrespective of the actual channel gains. Second, for the case of three-user double Z-channel, we show that universal optimality is not achievable if the per node information is below a threshold. Third, using reduced parametrization $K$-user channel, we show that very few protocol rounds are needed for the case of very weak or very strong interference.
Introduction
In classical information theory, researchers typically assume that every transmitter and receiver in a network possesses "Full Channel State Information" (CSI)—meaning they know every link's strength and the overall network topology. In reality, especially in large-scale or highly mobile wireless networks, centralizing this data is often impossible due to massive overhead.
This paper addresses the "Local View" problem: if nodes only possess information about their immediate neighbors (and perhaps a few hops beyond), can the network still reach its theoretical maximum total data rate (sum-capacity)? The authors aim to quantify the relationship between the extent of local information and the achievable sum-rate.
The Local Message Passing Framework
To rigorously study the impact of limited information, the authors introduce a Local Message Passing Protocol. This protocol serves as a proxy for the "depth" of a node's knowledge. Information exchange occurs in discrete rounds, each consisting of a forward phase (transmitters to receivers) and a reverse phase (receivers to transmitters).
As shown in the figure above, the protocol tracks how channel state information (H) trickles through the network. The number of rounds ($d$) serves as a formal metric for local information. For example, "1.5 rounds" indicates that a node knows its own links and has received one full update from its immediate neighbors plus the subsequent forward phase update.
Network Topologies and Methodology
The study focuses on three "stacked" Z-channel structures, which represent challenging scenarios for information flow due to their linear interference patterns:
- Z-channel: Two pairs of users where only one transmitter interferes with the "wrong" receiver.
- Double Z-channel: Three pairs of users stacked such that interference flows unidirectionally downward.
- K-user Stacked Z-channel: A symmetric chain of $K$ users.
These models are evaluated using both Deterministic Models (simplifying signals to bits to highlight structural constraints) and Gaussian Models (the standard noisy wireless model).
Key Insights and Results
Polite Greediness in the Z-Channel
In the simple Z-channel, the network can reach global optimality with just 1.5 rounds of information. This is achieved through a strategy termed "politely greedy." A node that is unaware of interference acts greedily to maximize its own rate, while the node that is aware it causes interference acts "politely" by choosing transmission parameters that do not harm the other's signal. This achieves universal optimality in deterministic channels and stays within 2 bits of optimality for Gaussian channels.
The Information Threshold
In the three-user Double Z-channel, the authors identify a "phase transition" in performance. With 2.5 rounds of information, universal optimality is possible. However, with only 1.5 rounds, it is mathematically impossible to be optimal for all channel gains. In certain regimes, the lack of information leads to "unbounded losses," where distributed decisions result in a 50% loss in sum-rate compared to the global optimum.
Regime-Dependent Coordination in K-User Networks
For the $K$-user symmetric Gaussian channel, the amount of information needed depends heavily on the interference level ($\alpha$):
- Weak or Strong Interference: If interference is very weak ($\alpha \leq 1/2$) or very strong ($\alpha \geq 2$), 1 round is sufficient for optimality.
- Intermediate Interference: In the "middle" regimes, nodes require $O(K)$ rounds—essentially knowledge of the entire chain—to avoid interfering with each other effectively. Without this, conservative decision-making kills "spatial reuse," the ability for distant nodes to use the same frequency simultaneously.
Conclusion
The core difficulty in distributed networks is not just that nodes have less information, but that they have different information. This mismatch leads to conservative decisions that limit network capacity. While simple topologies can be managed with minimal local views, complex structures require coordination that scales with the network diameter. Future work may extend these findings to fading channels and explore belief propagation as a mechanism for more efficient distributed decision-making.
Summary updated