Multi-terminal Strong Coordination over Noisy Channels with Encoder Co-operation

Viswanathan Ramachandran, Tobias J. Oechtering and Mikael Skoglund · 2025

Read Multi-terminal Strong Coordination over Noisy Channels with Encoder Co-operation by Viswanathan Ramachandran, Tobias J. Oechtering and Mikael Skoglund (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-12227.txt.

Introduction

Viswanathan Ramachandran, Tobias Oechtering, and Mikael Skoglund wrote a 2025 paper on a coordination task over a noisy channel. Two encoding devices each watch a source. A distant decoder must generate a fresh sequence that fits the joint distribution of both sources and a piece of side information. The channel adds noise to everything they send.

The sending pair may or may not peek at the input of each other, a practice called cribbing. The team works out the rates at which the coordination can be achieved when peeking is allowed. With no peeking, their bound is proven tight for one clean case: deterministic links, and sources that are independent once the side information is known. A worked example shows that peeking strictly enlarges the region where success is possible.

Catalog record

CREATORViswanathan Ramachandran, Tobias J. Oechtering and Mikael Skoglund
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-12227

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multi-terminal Strong Coordination over Noisy Channels with Encoder Co-operation Viswanathan Ramachandran, Tobias J. Oechtering and Mikael Skoglund Abstract We investigate the problem of strong coordination over a multiple-access channel (MAC) with cribbing encoders. In this configuration, two encoders observe independent and identically distributed (i.i.d.) samples of a source random variable each and encode the inputs to the MAC. The decoder which observes the output of the MAC together with side-information, must generate approximately i.i.d. samples of another random variable which is jointly distributed with the two sources and the side information. We also allow for possible encoder cooperation, where one of the encoders can non-causally crib from the other encoder’s input. Independent pairwise shared randomness is assumed between each encoder and the decoder at limited rates. Firstly, in the presence of cribbing, we derive an achievable region based on joint source-channel coding. We also prove that in the absence of cribbing, our inner bound is tight for the special case when the MAC is composed of deterministic links, and the sources are conditionally independent given the side information. We then explicitly compute the regions for an example both with and without cribbing between the encoders, and demonstrate that cribbing strictly improves upon the achievable region. I Introduction The framework of coordination [ 1 ] explores the minimal communication necessary to establish a desired joint distribution of actions among all nodes in a network. In light of the explosion of device-to-device communications as part of the Internet of Things (IoT), this architecture is useful in such scenarios where decentralized cooperation is desired amongst distributed agents. We focus on the notion of strong coordination , where the distribution of the sequence of actions must be close in total variation to a target distribution. Enc 1 Dec Y^{n} K_{1}\in[1:2^{nR_{01}}] X_{1}^{n} Enc 2 X_{2}^{n} W^{n} p(\tilde{y}|\tilde{x}_{1},\tilde{x}_{2}) \tilde{X}_{1}^{n} \tilde{X}_{2}^{n} \tilde{Y}^{n} K_{2}\in[1:2^{nR_{02}}] S Fig. 1: Strong coordination over a MAC with cribbing encoders Complete characterizations for strong coordination in multi-terminal networks are comparatively rare. Building upon the the point-to-point network, a cascade network with secrecy constraints was investigated in [ 2 ] , for which the optimal trade-off between communication and common randomness rates was determined. In [ 3 , 4 , 5 , 6 , 7 ] , strong coordination was investigated over a multiple-access network of noiseless links, with a tight characterization derived for independent sources. Simulation of a channel using another channel as a resource, rather than noiseless communication links as in [ 8 ] , was investigated by [ 9 , 10 ] . However, multi-terminal extensions of strong coordination over noisy channels with the interplay between different terminals has not received much attention. Accordingly, the current paper extends channel simulation from noisy channels [ 10 ] to a three-terminal scenario with possible encoder cooperation [ 11 , 12 , 13 ] . It also extends the noiseless setting [ 3 ] to noisy channels. The main technical novelty here lies in bringing out the role of encoder cooperation in reducing the shared randomness needed for coordination. Main Contributions. When the switch S in Fig. 1 is closed, we derive an achievable region (Theorem 1 ) based on joint source-channel coding. When the switch S in Fig. 1 is open, we give a tight characterization for the special case when the MAC is composed of deterministic links, and the sources are conditionally independent given the side information (Theorem 2 ). The non-trivial part lies in leveraging the deterministic channel and independent sources assumptions to obtain a single-letterization matching the inner bound, which is known to be difficult for distributed source coding settings [ 14 ] . We then explicitly compute the regions for an example both with and without encoder cribbing and demonstrate that cribbing strictly improves upon the achievable region (see Section IV ). II System Model The setup comprises two encoders, with Encoder j\in\{1,2\} observing an input given by X_{j}^{n} , and a decoder which observes a side information sequence W^{n} . For j\in\{1,2\} , Encoder j and the decoder can harness pairwise shared randomness K_{j} , assumed to be uniformly distributed on [1:2^{nR_{0j}}] . When the switch S in Fig. 1 is closed, Encoder 2 (which observes X_{2}^{n} and has access to K_{2} ) first generates the channel input sequence \tilde{X}_{2}^{n} . Then, Encoder 1 (which observes X_{1}^{n} and has access to K_{1} as well as \tilde{X}_{2}^{n} ) creates the channel input sequence \tilde{X}_{1}^{n} . A discrete-memoryless multiple-access channel specified by p(\tilde{y}|\tilde{x}_{1},\tilde{x}_{2}) maps the channel input sequences into an observation \tilde{Y}^{n} at the receiver. The sources (X_{1i},X_{2i},W_{i}) , i=1,2,\ldots,n , are assumed to be i.i.d. with joint distribution specified by nature as q_{X_{1}X_{2}W} . The random variables X_{1},X_{2},W,\tilde{X}_{1},\tilde{X}_{2},\tilde{Y} assume values in finite alphabets \mathcal{X}_{1},\mathcal{X}_{2},\mathcal{W},\mathcal{\tilde{X}}_{1},\mathcal{\tilde{X}}_{2},\mathcal{\tilde{Y}} , respectively. The shared randomness indices K_{1} and K_{2} are assumed to be independent of each other and of (X_{1}^{n},X_{2}^{n},W^{n}) . The decoder obtains (K_{1},K_{2},W^{n},\tilde{Y}^{n}) and simulates an output sequence Y^{n} (where Y_{i} , i=1,\dots,n, assumes values in a finite alphabet \mathcal{Y} ) which along with the input sources and side information must be approximately i.i.d. according to the joint distribution q^{(n)}_{X_{1}X_{2}WY}(x_{1}^{n},x_{2}^{n},w^{n},y^{n}):=\prod_{i=1}^{n}q_{X_{1}X_{2}WY}(x_{1i},x_{2i},w_{i},y_{i}) (refer Figure 1 ). Definition 1 . A (2^{nR_{01}},2^{nR_{02}},n) code comprises two randomized encoders p^{\emph{Enc}_{2}}(\tilde{x}_{2}^{n}|x_{2}^{n},k_{2}) and p^{\emph{Enc}_{1}}(\tilde{x}_{1}^{n}|x_{1}^{n},k_{1},\tilde{x}_{2}^{n}) and a randomized decoder p^{\emph{Dec}}(y^{n}|k_{1},k_{2},w^{n},\tilde{y}^{n}) , where k_{j}\in[1:2^{nR_{0j}}] , j\in\{1,2\} . The induced joint distribution of all the random variables and the resulting induced marginal distribution on (X_{1}^{n},X_{2}^{n},W^{n},Y^{n}) are respectively given by \displaystyle p(x_{1}^{n},x_{2}^{n},w^{n},k_{1},k_{2},\tilde{x}_{1}^{n},\tilde{x}_{2}^{n},\tilde{y}^{n},y^{n}) \displaystyle=\frac{1}{2^{n(R_{01}+R_{02})}}q(x_{1}^{n},x_{2}^{n},w^{n})p^{\text{Enc}_{2}}(\tilde{x}_{2}^{n}|x_{2}^{n},k_{2}) \displaystyle\hskip 6.0pt\times p^{\text{Enc}_{1}}(\tilde{x}_{1}^{n}|x_{1}^{n},k_{1},\tilde{x}_{2}^{n})p(\tilde{y}^{n}|\tilde{x}_{1}^{n},\tilde{x}_{2}^{n})p^{\text{Dec}}(y^{n}|k_{1},k_{2},w^{n},\tilde{y}^{n}), and \displaystyle p^{\text{ind}}(x_{1}^{n},x_{2}^{n},w^{n},y^{n}) \displaystyle\hskip 12.0pt=\sum_{k_{1},k_{2},\tilde{x}_{1}^{n},\tilde{x}_{2}^{n},\tilde{y}^{n}}p(x_{1}^{n},x_{2}^{n},w^{n},k_{1},k_{2},\tilde{x}_{1}^{n},\tilde{x}_{2}^{n},\tilde{y}^{n},y^{n}). Definition 2 . A rate pair (R_{01},R_{02}) is said to be achievable for a target joint distribution q_{X_{1}X_{2}WY} with cribbing provided there exists a sequence of (2^{nR_{01}},2^{nR_{02}},n) codes such that \displaystyle\lim_{n\to\infty}||p^{\text{ind}}_{X_{1}^{n},X_{2}^{n},W^{n},Y^{n}}-q^{(n)}_{X_{1}X_{2}WY}||_{1}=0, (1) where q^{(n)}_{X_{1}X_{2}WY} is the target i.i.d. product distribution \displaystyle q^{(n)}_{X_{1}X_{2}WY}(x_{1}^{n},x_{2}^{n},w^{n},y^{n}):=\prod_{i=1}^{n}q_{X_{1}X_{2}WY}(x_{1i},x_{2i},w_{i},y_{i}). Definition 3 . The rate region \mathcal{R}_{\textup{noisy-coord}}^{\textup{MAC, crib}} is the closure of the set of all achievable rate pairs (R_{01},R_{02}) . We also separately consider the case when the switch S in Fig. 1 is open. A code, an achievable rate pair, and the rate region can be defined analogously. In particular, the code and an achievable rate pair can be defined similar to Definitions 1 and 2 by changing the map at Encoder 1 to simply p^{\text{Enc}_{1}}(\tilde{x}_{1}^{n}|x_{1}^{n},k_{1}) . The rate region \mathcal{R}_{\textup{noisy-coord}}^{\textup{MAC}} is the closure of the set of all achievable rate tuples (R_{01},R_{02}) when the switch S in Fig. 1 is open. Let \mathcal{R}_{\textup{noisy-coord, $R_{02}\to\infty$}}^{\textup{MAC}} be the region when the pairwise shared randomness K_{2} is unlimited: \displaystyle\mathcal{R}_{\textup{noisy-coord, $R_{02}\to\infty$}}^{\textup{MAC}}=\{R_{01}:\exists\ R_{02} \displaystyle\text{s.t.}\ (R_{01},R_{02})\in\mathcal{R}_{\textup{noisy-coord}}^{\textup{MAC}}\}. (2) III Main Results We first present our results in the context where one of the encoders is allowed to crib [ 11 , Situation 4] from the other encoder’s input non-causally (the switch S in Figure 1 is closed). This will facilitate cooperation between the encoders, in that Enc 1 can build its codebooks conditioned on the knowledge of the input codeword from Enc 2 . We have the following inner bound to the rate region \mathcal{R}_{\textup{noisy-coord}}^{\textup{MAC, crib}} . In the theorem below, the auxiliary random variables U_{1} , U_{2} are used in the joint source-channel coding scheme to send source descriptions of X_{1} , X_{2} respectively, while T is a time-sharing random variable. The decoder then recovers the source descriptions and locally simulates Y . Theorem

Read the complete text