PaperlayerView exact revision on arXiv

Source-linked AI summary

Coordination Capacity

Paul Cuff, Haim Permuter, Thomas Cover

arXiv:0909.2408v2cs.IT

TL;DR

The paper asks what dependence among network actions can be established under communication-rate constraints, rather than treating networks only as information-transfer systems. It develops coordination-capacity characterizations for several network settings, including cascade networks, and examines strong coordination and common randomness. The results connect coordination capacity with rate-distortion regions and establish additional network-specific conclusions, including a low-rate broadcast construction.

  • Problem

    The paper asks which joint distributions of actions are achievable among network nodes when communication links have specified rate constraints.

  • Method

    It formulates coordination through network-specific achievable-distribution regions and analyzes empirical and strong coordination using communication, common randomness, coding, and information-theoretic proofs.

  • Results

    The paper characterizes coordination capacity in several settings, relates rate-distortion regions to coordination capacity, and reports a broadcast construction with I(X; U) ≈ 0.04 bits.

  • Takeaways & Limitations

    Coordination capacity provides a framework for studying dependence among distributed actions and for quantifying the communication and common randomness needed to realize target distributions.

Abstract

from arXiv · show

We develop elements of a theory of cooperation and coordination in networks. Rather than considering a communication network as a means of distributing information, or of reconstructing random processes at remote nodes, we ask what dependence can be established among the nodes given the communication constraints. Specifically, in a network with communication rates {R_{i,j}} between the nodes, we ask what is the set of all achievable joint distributions p(x1, ..., xm) of actions at the nodes of the network. Several networks are solved, including arbitrarily large cascade networks. Distributed cooperation can be the solution to many problems such as distributed games, distributed control, and establishing mutual information bounds on the influence of one part of a physical system on another.

I. INTRODUCTION

The paper frames network communication as a way to establish coordinated dependence among nodes, rather than merely moving or reconstructing information. It studies achievable action distributions under rate-limited communication, common randomness, and different network settings.

  • Motivation: Coordination is posed as finding the communication needed to establish a desired joint distribution of behavior among network nodes.The framework differs from traditional source coding, which focuses on transmitting data under fidelity constraints.
  • Framework: Nature assigns some node actions randomly, while other actions are constructed using communication and common randomness under network constraints.In the general framework, source actions follow p0(x1, x2, x3), and produced actions must satisfy compatible conditional distributions.
  • Applications: The framework applies to sensor networks, cooperative wireless transmission, distributed control, and coherent computation across networks.These applications involve coordinating node behavior, sometimes without treating communication as conventional information transfer.
  • Introduction: Without communication, common randomness allows isolated nodes to generate any desired joint distribution when none of their actions are fixed by nature.The nodes agree in advance on functions of shared randomness, such as a timestamp used as a random-number-generator seed.
  • Introduction: The problem changes when nature specifies an action at a node, because the remaining nodes must coordinate with that externally selected value.This distinction motivates the subsequent network coordination scenarios.
  • Contributions: The paper develops coordination results for two- and three-node networks, including complete characterizations for some settings and bounds or special-case solutions for others.It also identifies a recurring coordination strategy, connects rate-distortion regions to coordination capacity, and studies strong coordination and common-randomness requirements.

B. Preliminary observations

The paper establishes foundational properties of coordination regions and applies the framework to two-node coordination and task assignment. Coordination regions are convex, common randomness is unnecessary for empirical coordination, and the two-node rate threshold is mutual information.

  • Preliminary observations: Cp0, Rp0, and Pp0 are convex sets.Time-sharing concatenates coordination codes, producing weighted averages of achievable rate-coordination pairs and joint types.
  • Preliminary observations: Common randomness does not enlarge the empirical coordination region.Any empirically achievable distribution at a given rate pair remains achievable with no common randomness.
  • Two nodes: Empirical coordination codes specify actions selected by nature, communication functions, and node actions generated from received messages.The framework studies network-wide coordination distributions rather than conventional point-to-point fidelity.
  • Two nodes: R ≥ I(X;Y) characterizes the two-node empirical coordination capacity region.With R = 0, only independent distributions p0(x)p(y) are achievable.
  • Two nodes: R ≥ log(k/k −1) is necessary and sufficient for node Y to choose a task different from node X.Node X receives one of k tasks randomly, and node Y selects one of the remaining tasks.

B. Isolated node

The isolated-node setting shows that an uninformed node can still coordinate with another node, while the cascade region is characterized by successive mutual-information constraints. Task assignment illustrates the resulting rate requirements.

  • Isolated node: R ≥ I(X;Y|Z), with Z independent of X, characterizes the isolated-node coordination capacity region.The permitted distributions have the form p0(x)p(z)p(y|x,z).
  • Isolated node: Z can depend on Y despite receiving no communication, because neither action is selected randomly by nature.At zero communication, the achievable distributions include all p0(x)p(y,z), and Y and Z may be equal.
  • Isolated node: Perfect correlation between X and Y forfeits any potential correlation between Y and Z.The isolated-node results expose a tradeoff between the two correlations.
  • Cascade: R1 ≥ I(X;Y,Z) and R2 ≥ I(X;Z) characterize the cascade coordination capacity region.The achievability argument meets the cut-set bound by specifying Z first and then Y conditioned on Z.
  • Cascade: R1 ≥ log 3 and R2 ≥ log 3 −log 2 allow three cascade nodes to select distinct tasks.The rates enable Y and Z to choose tasks different from X and from each other.

D. Degraded source

The degraded-source network has complete coordination-capacity results, with node Y relaying information from X while node Z receives messages from both X and Y. The broadcast network is treated separately through inner and outer bounds, which are tight for many distributions.

  • D. Degraded source: Node X sends messages to Y and Z, while Y forwards a message to Z; Z produces its action from both received messages.The degraded-source model assumes Y=f0(X), with rates R1, R2, and R3 on the respective links.
  • D. Degraded source: Theorem 6 characterizes the degraded-source coordination capacity region using an auxiliary U with |U| ≤ |X||Z| + 2.The rate constraints are R1 ≥ I(X; U|Y), R2 ≥ I(X; Z|U), and R3 ≥ I(X; U).
  • Results and techniques: The work develops complete results for some multinode networks and partial bounds for others, using shared messages to correlate codebooks across communication links.The common message can reduce the rates needed to specify coordinated actions, while the sum rate may incur a coordination penalty.
  • A. Broadcast: The broadcast network sends separate messages from X to Y and Z, whose actions must match a desired joint conditional distribution.The inner bound uses an auxiliary U and imposes individual and sum-rate constraints; the outer bound gives corresponding necessary constraints.
  • A. Broadcast: For many broadcast distributions, the inner and outer bounds coincide, including Markov-chain cases, independent Y and Z, and pairwise independence of X with both receivers.In these cases, Rp0,in = Rp0,out.
  • A. Broadcast: A positive rate R2 can reduce the required R1 even when X and Z are independent in the desired distribution.In the stated example, the minimum R1 is 1 bit when R2=0 and 1−R2 bits in general.

B. Cascade multiterminal

The cascade multiterminal network requires Y to combine information about X with its own action before transmitting to Z. The paper gives inner and outer bounds, proves tightness in several structural cases, and solves task assignment exactly.

  • B. Cascade multiterminal: Node X sends information to Y, which combines it with its own action before sending a single message to Z.Node Z then produces its action solely from Y’s outgoing message.
  • B. Cascade multiterminal: Theorem 8 bounds the cascade multiterminal coordination region by Cp0,in ⊂ Cp0 ⊂ Cp0,out.The inner and outer regions are defined using auxiliary variables U,V and U, respectively.
  • B. Cascade multiterminal: The inner-bound scheme sends a common component U through Y to Z and a private component V to Y, which recompresses V with its own action.This reflects Y’s dual role as both relay and source of side information.
  • B. Cascade multiterminal: The bounds are tight when X−Y−Z or Y−X−Z forms a Markov chain, and also when X or Y is a function of the other or Z is a function of X and Y.These cases satisfy Rp0 = Rp0,in = Rp0,out.
  • Task assignment: Task assignment computes Z(X,Y), and its exact rate region is R1 ≥ log 2 and R2 ≥ log 3.The achievability uses U=∅ and V=X.

V. STRONG COORDINATION

Strong coordination strengthens empirical coordination by requiring the entire induced action sequence to approximate a target joint distribution, not merely its empirical type. This stronger objective matters when coordinated behavior must remain random and unpredictable.

  • V. STRONG COORDINATION: Empirical coordination constrains the joint type of action sequences, without requiring the sequences themselves to be random or their temporal order to matter.The goal is matching the desired distribution on average over time.
  • V. STRONG COORDINATION: Strong coordination requires the induced distribution over the entire coding block to be close to the target i.i.d. joint distribution.The distributions should be statistically indistinguishable based on the generated action sequences.
  • V. STRONG COORDINATION: Strong coordination is more demanding than empirical coordination because i.i.d. random actions would imply empirical agreement, but not conversely.The distinction is important when the sequence of actions must preserve randomness.
  • V. STRONG COORDINATION: In cooperative repeated games, strong coordination can help a team combat an opponent that anticipates and exploits patterns in its joint actions.The team selects a suitable joint distribution for its coordinated behavior.

A. Problem specifics

Strong coordination requires the induced time-sequence distribution to approach a desired i.i.d. distribution in total variation, unlike empirical coordination, which concerns joint types. Common randomness is a central resource: it can enable strong coordination and may make strong and empirical capacity regions coincide.

  • Strong coordination: Strong achievability requires the induced distribution of action sequences to converge in total variation to the desired i.i.d. distribution.This criterion does not depend on the joint type.
  • Strong coordination: Private randomized encoders and decoders do not improve empirical coordination capacity over deterministic coordination codes.Randomization is useful for producing appropriately distributed actions in strong coordination, but not for the empirical objective.
  • Common randomness: Without communication, independent actions are possible without common randomness, whereas sufficient common randomness can generate any desired joint distribution.The required common-randomness rate can be identified for each desired distribution.
  • Strong coordination: Total variation provides a fidelity measure because small distance limits distinguishability by hypothesis tests and changes in expected bounded functions.The paper uses total variation to compare induced and desired distributions.
  • Common randomness: With enough common randomness, strong coordination is conjectured to have the same capacity region as empirical coordination.Under this conjecture, empirical coordination results would inform strong-coordination schemes.

C. No communication

For networks without communication, strong coordination characterizes which joint action distributions can be generated from common randomness. The paper gives a general auxiliary-variable characterization, extends common-information ideas to multiple nodes, and quantifies communication–common-randomness trade-offs in two-node settings.

  • Three nodes: The no-communication result generalizes to any number of nodes and interprets required common randomness as a form of group common information.The proof follows nearly the same steps as Wyner’s common-information proof.
  • Three nodes: The no-communication capacity region consists of joint distributions representable through an auxiliary U with conditionally independent node actions.The characterization requires p(x,y,z,u)=p(u)p(x|u)p(y|u)p(z|u), |U|≤|X||Y||Z|, and R0≥I(X,Y,Z;U).
  • Two nodes: In the two-node network, no common randomness requires communication R≥C(X;Y), where C(X;Y) is Wyner’s common information.C(X;Y) minimizes I(X,Y;U) over Markov chains X−U−Y.
  • Two nodes: If and only if R0≥H(Y†X), the two-node strong-coordination region requires only R≥I(X;Y).H(Y†X) is defined as the necessary conditional entropy and is sufficient to maximize the region.
  • Task assignment: For two-node task assignment, increasing common randomness expands the strong-coordination region until R0 exceeds log(k−1).At that threshold, the required communication is R≥log(k−1); without common randomness, the requirement is R≥2 bits−log(k−1).

VI. RATE-DISTORTION THEORY

The paper connects rate-distortion theory to coordination capacity by viewing distortion constraints as restrictions on achievable joint action distributions. For memoryless sources, the rate-distortion region is a linear projection of the coordination capacity region.

  • Rate-distortion connection: Rate-distortion theory is linked to empirical coordination because both seek a suitable joint distribution between source and reconstruction actions.The single-source benchmark uses a communication rate exceeding I(X;X̂) for a chosen reconstruction conditional distribution.
  • Linear projection: The rate-distortion region Dp0 for any rate-limited network is the linear projection of the coordination capacity region Cp0.The projection is represented by the matrix A.
  • Linear projection: Dp0=A Cp0.The coordination-rate tuples are vectorized, and the distortion matrix is embedded in a block-diagonal projection matrix.
  • Geometry: Because Cp0 is convex, the corresponding rate-distortion region Dp0 is also convex.Distortion constraints define hyperplanes, so fixed-rate optimization searches for extreme points in relevant directions.
  • Rate-distortion connection: A rate-distortion code cannot improve on a code that produces the same joint type for almost every source observation when sources are memoryless.Repeated uses of a code producing varying joint types can be combined to obtain a single jointly coordinated behavior.

1) Strong Markov Lemma:

The Strong Markov Lemma strengthens typicality arguments for layered network codes. Under Markov structure and permutation-invariant conditional sampling, the generated sequence is jointly close to the Markov joint type with high probability.

  • Role in coding proofs: The generalized lemma supports analysis of layered piggy-back codes used in the paper’s empirical-coordination achievability proofs.It extends the standard Markov Lemma, which lacks sufficient strength for more intricate network encoding schemes.
  • Strong Markov Lemma: The Strong Markov Lemma applies to an X−Y−Z Markov chain when xn and yn are jointly typical and Zn is permutation-invariant conditional on yn.It establishes that Pxn,yn,Zn is close to Pxn,ynPZn|yn.
  • Proof strategy: Permutation invariance makes all sequences within a conditional type class equally likely, enabling counting-based probability bounds.The proof partitions sequences by conditional type classes and bounds atypical classes.
  • Strong Markov Lemma: Most realizations have a joint type within ε of the Markov joint type, with the probability bound depending only on alphabet sizes and ε.The constants α and β depend on ε and |X|, |Y|, and |Z|.
  • Strong Markov Lemma: The lemma’s failure probability is bounded using the exponentially decaying term 2^-αn+β log n.The bound holds with probability at least 1−2^-αn+β log n.
  • Proof strategy: The proof derives the final total-variation bound by repeatedly applying the triangle inequality to intermediate distributions.The resulting bound is ||Pxn,yn,Zn−pX,Y,Z||TV<4ε.

2) Generic Achievability Proof:

The generic two-node scheme uses randomized codebooks, binning, and jointly typical decoding to coordinate a sequence U^n from distributed side information. It succeeds when the communication rate exceeds I(X;U|Y,Z), with error probability vanishing asymptotically.

  • Generic coordination with side information: R > I(X; U|Y, Z) + δ(ε) suffices to generate U^n jointly typical with (X^n,Y^n,Z^n).Here δ(ε) tends to zero as ε tends to zero.
  • Codebook and binning: A codebook of 2^nRc sequences is randomly partitioned into 2^nR bins, allowing the encoder to send only a bin index.The construction uses Rc = I(X,Y;U) + γ/2 and roughly 2^nRb sequences per bin.
  • Encoding and decoding: The encoder finds a codeword typical with (X^n,Y^n), while the decoder selects a codeword in the received bin typical with (Y^n,Z^n).The selected codeword becomes the coordinated sequence U^n.
  • Error analysis: The three declared error events become negligible for sufficiently large n, using covering, the Markov chain Z−(X,Y)−U, and binning analysis.Choosing δ(ε) = max{2δ1(ε), 2δ2(ε), 8ε} makes all error terms vanish.
  • Special case: With Y=Z=∅, the lemma implies that a sequence Y^n jointly typical with X^n can be specified with high probability at any rate R > I(X;Y).This is obtained as a special case of the generic lemma.

3) Two nodes - Theorem 3:

The achievability constructions for several network topologies specify auxiliary sequences in stages, using binning when side information is available and forwarding sequences across links. The resulting rate inequalities are mutual-information expressions determined by each topology.

  • Cascade network: For the cascade network, R1 > I(X;Y,Z) and R2 > I(X;Z) achieve the desired coordination p(y,z|x).The scheme first specifies Z^n and then Y^n conditional on Z^n.
  • Degraded source network: For the degraded-source network, R1 > I(X;U|Y), R2 > I(X;Z|U), and R3 > I(X;U) are achievable.Binning is used to send U^n from node X to node Y, while U^n is forwarded to node Z.
  • Broadcast network: For the broadcast network corner point, R1 = RU + RY > I(X;U,Y) and R2 = RU + RX > I(X;U) + I(X,Y;Z|U).The encoder successively specifies U^n, Y^n, and Z^n.
  • Cascade multiterminal network: For the cascade multiterminal network, the scheme uses auxiliary sequences U^n and V^n, with R2 = RU,2 + RZ > I(X;U) + I(Y,V;Z|U).The Strong Markov Lemma transfers joint typicality through the network.
  • Time mixing: Time mixing with a uniform random index Q equates expected joint types with the distribution of (XQ,YQ,ZQ), supporting single-letter mutual-information bounds.If sequence elements are identically distributed, XQ is independent of Q and has the same distribution as X1.

1) Two nodes - Theorem 3:

The converse arguments single-letterize blocklength-n coordination codes through time mixing and total-variation convergence. Applying two-node bounds to subnetworks yields the necessary rate constraints for cascade, degraded-source, broadcast, and cascade multiterminal networks.

  • Single-letterization: The induced joint distribution converges in total variation to the target distribution, enabling continuity arguments for mutual-information bounds.The achievable-code definition gives convergence in probability of the total variation distance to zero.
  • Cascade network: For the cascade network, R1 ≥ I(X;Y,Z) and R2 ≥ I(X;Z) remain necessary even when the opposite node pairs fully cooperate.The two-node converse is applied once to each link.
  • Degraded source network: For the degraded-source network, an auxiliary U built from message K, past source symbols, and Q yields the outer-bound characterization in Theorem 6.The proof uses time mixing and the closedness of the coordination capacity region.
  • Broadcast network: For the broadcast network, the converse requires R1 ≥ I(X;Y), R2 ≥ I(X;Z), and R1 + R2 ≥ I(X;Y,Z).These bounds hold even when nodes Y and Z are allowed to fully cooperate for the sum-rate argument.
  • Cascade multiterminal network: For the cascade multiterminal network, the auxiliary U satisfies U−XQ−YQ and XQ−(YQ,U)−ZQ, supporting the outer bound in Theorem 8.The time-mixed joint distribution approaches p0(x,y)p(z|x,y).

C. Strong Coordination (Section V)

Strong coordination concerns the full joint distribution rather than only empirical joint types and uses common randomness to generate coordinated actions. In the two-node setting, the achievable communication and common-randomness rates are characterized through an auxiliary variable satisfying conditional independence.

  • Achievability: With common randomness, a shared U^n sequence is passed through separate memoryless channels at each node to produce jointly coordinated actions.Conditional independence given U makes the separate channel outputs match the desired joint construction.
  • Two-node capacity region: The strong coordination region is described by p(y|x) admitting p(u|x,y) with p(x,y,u)=p(u)p(x|u)p(y|u), |U| ≤ |X||Y|+1, R ≥ I(X;U), and R0+R ≥ I(X,Y;U).R0 denotes common-randomness rate and R denotes communication rate.
  • No common randomness: With no common randomness, the communication requirement reduces to Wyner’s common information C(X;Y).The stronger rate inequality becomes R ≥ I(X,Y;U), minimized over auxiliaries satisfying the Markov constraint.
  • Role of common randomness: Common randomness greater than H(Y†X) makes rates R > I(X;Y) sufficient and is the least amount needed to fully expand the strong coordination region.The construction chooses U as a function of Y and uses the chain rule to satisfy the rate constraints.

D. Rate-distortion theory (Sections VI)

The paper relates coordination capacity to rate-distortion theory and extends coordination-rate analysis to larger networks. It finds linear total-rate scaling for cascade task assignment, versus logarithmic scaling for broadcast networks, while noisy-network coordination remains unresolved.

  • Rate-distortion relationship: A coordination code in the interior of the coordination capacity region achieves joint empirical distributions within total variation error ǫ with probability at least 1−ǫ.The resulting bounded distortion is at most E_p d(X, Y) + ǫd_max.
  • Rate-distortion relationship: The coordination-capacity and rate-distortion regions are equivalent under linear projection, linking achievable joint-action distributions to distortion values.The proof establishes both inclusions between the corresponding regions, using repeated rate-distortion codes and total-variation convergence.
  • Coordination framework: The framework asks which joint distributions of network actions are achievable under communication and common-randomness constraints, rather than only how data are transported.For some three-node networks the answer is fully characterized, while for others only bounds are established.
  • Large-network task assignment: For extended cascade networks, assigning a permutation of k tasks to k nodes requires total rate approximately k nats, scaling linearly with network size.The construction uses cascade communication and rates satisfying Ri ≥ I(X; Yi, ..., Yk).
  • Large-network task assignment: For extended broadcast networks, the same permutation task requires total rate approximately ln k + 1 nats, yielding logarithmic rather than linear scaling.The scheme uses default tasks and communicates exceptions, with individual rates satisfying Ri ≥ H(1/k).
  • Noisy networks: The coordination capacity region for noisy broadcast channels remains an open problem, despite known communication-capacity results for several special channel classes.Coordination depends on the joint dependence between outputs, not only their marginal channels.
Loading 0909.2408v2…