Necessity of Cooperative Transmissions for Wireless MapReduce
Yue Bi 1 , Michèle Wigger 1 · 2026
Read Necessity of Cooperative Transmissions for Wireless MapReduce by Yue Bi 1 , Michèle Wigger 1 (2026) 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-2601-11844.txt.
Introduction
Yue Bi and Michèle Wigger improve a bound for shared computing over wireless links. In MapReduce, many nodes split a big job, share part results, then merge them. The key trade is between compute load on each node and the time to deliver results.
Their new bound is an achievability result, so it shows a scheme that works. It rests on interference alignment plus zero-forcing, two ways to shape signals. The bound holds in set ranges of the trade terms. Tighter bounds guide the design of fast shared compute nets.
Catalog record
| CREATOR | Yue Bi 1 , Michèle Wigger 1 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-11844
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Necessity of Cooperative Transmissions for Wireless MapReduce Yue Bi 1 , Michèle Wigger 1 Abstract The paper presents an improved upper bound (achievability result) on the optimal tradeoff between Normalized Delivery Time (NDT) and computation load for distributed computing MapReduce systems in certain ranges of the parameters. The upper bound is based on interference alignment combined with zero-forcing. The paper further provides a lower bound (converse) on the optimal NDT-computation tradeoff that can be achieved when IVAs are partitioned into sub-IVAs, and these sub-IVAs are then transmitted (in an arbitrary form) by a single node, without cooperation among nodes. For appropriate linear functions (e.g., XORs), such non-cooperative schemes can achieve some of the best NDT-computation tradeoff points so far obtained in the literature. However, as our lower bound shows, any non-cooperative scheme achieves a worse NDT-computation tradeoff than our new proposed scheme for certain parameters, thus proving the necessity of cooperative schemes like zero-forcing to attain the optimal NDT-computation tradeoff. I Introduction MapReduce systems are becoming important building blocks also in wireless scenarios because they allow us to distribute heavy computation tasks over multiple distributed nodes. Important performance parameters of such systems are the computation load \mathsf{r} , which characterizes the average amount of data stored at the nodes (i.e., memory requirements), and the Normalized Delivery Time (NDT) \Delta , which characterizes the duration of the wireless shuffle phase (i.e., communication requirements). The optimal tradeoff between memory requirements and communication duration was first characterized in [ 8 ] , but under the assumption of perfect multicast communication links. The optimal scheme for this noiseless setup splits intermediate values (IVA) into message parts and then communicates appropriate XORs of these parts. Decoding requires that receiving nodes use their knowledge of the message parts transmitted by other nodes to cancel non-desired parts of the XORs. Similar assumptions of ideal multicast or noiseless communication links have also been adopted in several related works, e.g., [ 11 , 10 , 9 ] . Several subsequent works [ 7 , 2 , 3 , 12 ] have studied the NDT-computation tradeoff of wireless MapReduce, i.e., the smallest NDT that can be achieved under a constraint on the computation load. The problem was first investigated for wireless interference networks in [ 7 ] , which proposed a coding scheme based on one-shot beamforming and zero-forcing (ZF). In our previous works in [ 2 , 3 ] , we obtained improved NDT-computation tradeoffs by introducing interference alignment (IA) [ 4 , 6 ] to the shuffle phase. For computation loads \mathsf{r}=\lfloor(\mathsf{K}-1)/2\rfloor , where \mathsf{K} denotes the number of nodes and is assumed to be odd, our work in [ 3 ] also proposes an improved IA scheme based on ZF. Notice that ZF introduces complex dependencies between IA matrices, rendering performance analysis of IA schemes involved [ 1 ] . In this paper, we improve our IA & ZF scheme in [ 3 ] . Our new scheme applies to an arbitrary number of nodes \mathsf{K} but still requires that \mathsf{r}=\lfloor(\mathsf{K}-1)/2\rfloor . For odd values of \mathsf{K} it strictly improves over our previous scheme in [ 3 ] . The new scheme is again based on IA & ZF and the analysis requires proving algebraic independence of certain functions. We provide an analytic proof for \mathsf{K}=5 in this paper as well as numeric verification for \mathsf{K}\in\{6,\ldots,15\} . Inspired by the excellent performance of the scheme in [ 8 ] and to avoid complicated analyses, several schemes (also for related cache-aided scenarios) [ 5 , 2 , 3 ] focused on exploiting the multicast behaviour of wireless MapReduce communication and the IVA side-information at the nodes, but without any form of cooperation between transmit signals. Specifically, the schemes divide the IVAs into submessages and each submessage is transmitted (in an arbitrary form) by only one of the nodes, without cooperation from the other nodes. Transmit signals across nodes are thus independent of each other. Nodes still use all their side-information about IVAs in their decoding steps. In this work, we provide a lower bound (converse result) on the NDT-computation tradeoff that can be achieved by any such non-cooperative scheme. We further show that this lower bound lies above the NDT-computation tradeoffs obtained by our new IA & ZF scheme, thus proving strict suboptimality of non-cooperative schemes. Notice that the previously obtained NDT-computation tradeoffs do not improve over the non-cooperative lower bound and do not allow us to obtain the desired conclusion. Notations: We use standard notation, and also define [n]\triangleq\{1,2,\ldots,n\} and [\mathcal{A}]^{t} as the collection of all the subsets of \mathcal{A} with cardinality t . i.e. [\mathcal{A}]^{t}\triangleq\{\mathcal{T}\colon\mathcal{T}\subseteq\mathcal{A},|\mathcal{T}|=t\} . II Wireless MapReduce Framework Consider a wireless MapReduce system with \mathsf{K}\geq 5 nodes labeled 1,\ldots,\mathsf{K} , with \mathsf{M} input files W_{1},\ldots,W_{\mathsf{M}} , and with \mathsf{K} output functions \phi_{1},\ldots,\phi_{\mathsf{K}} , where function \phi_{k} is assigned to Node k . The system follows the MapReduce framework, in which each output function is decomposed as \phi_{q}(W_{1},\ldots,W_{\mathsf{M}})=v_{q}(a_{q,1},\ldots,a_{q,\mathsf{M}}),\quad q\in[\mathsf{K}], (1) where a_{q,p}=u_{q,p}(W_{p}),\quad p\in[\mathsf{M}], (2) denotes the intermediate value (IVA) computed from file W_{p} . All IVAs are assumed independent and consist of \mathsf{A} i.i.d. bits. The MapReduce framework has 3 phases: Map phase Each node k is assigned a subset of files \mathcal{M}_{k}\subseteq[\mathsf{M}] and computes the IVAs \{a_{q,p}:p\in\mathcal{M}_{k},\ q\in[\mathsf{K}]\} . Shuffle phase Nodes exchange IVAs over \mathsf{n} uses of a wireless channel in full-duplex mode. Node k transmits {\mathbf{X}}_{k}=f_{k}^{(\mathsf{n})}\!\left(\{a_{1,p},\ldots,a_{\mathsf{K},p}\}_{p\in\mathcal{M}_{k}}\right), (3) subject to the average power constraint \frac{1}{\mathsf{n}}\sum_{t=1}^{\mathsf{n}}\mathbb{E}[|X_{k}(t)|^{2}]\leq\mathsf{P}. (4) Node k observes Y_{k}(t)=\sum_{k^{\prime}\in[\mathsf{K}]\backslash\{k\}}H_{k,k^{\prime}}(t)X_{k^{\prime}}(t)+Z_{k}(t),\quad t\in[\mathsf{n}], (5) and {\mathbf{Y}}_{k}\triangleq\left(Y_{k}(1)\dots,Y_{k}(\mathsf{n})\right) , where \{H_{k,k^{\prime}}(t)\} and \{Z_{k}(t)\} are i.i.d. over time and across node pairs. Each coefficient H_{p,q}(t) has independent and identically distributed real and imaginary parts, following a specified continuous distribution over a bounded interval [-\mathsf{H}_{\max},\mathsf{H}_{\max}] for some positive integer \mathsf{H}_{\max} . All nodes have perfect channel state information. Based on {\mathbf{Y}}_{k} and the IVAs computed locally, Node k decodes the missing IVAs as \hat{a}_{k,p}=g_{k,p}^{(\mathsf{n})}\!\left(\{a_{q,i}\}_{i\in\mathcal{M}_{k},q\in[\mathsf{K}]},{\mathbf{Y}}_{k}\right),\quad p\notin\mathcal{M}_{k}. (6) Reduce phase Each node k\in[\mathsf{K}] applies its reduce function v_{k} to its available IVAs to compute its assigned output function \phi_{k} . The performance of the distributed computing system is measured by two factors: computation load and normalized delivery time (NDT) . The computation load is defined as \mathsf{r}\triangleq\sum_{k\in[\mathsf{K}]}\frac{|\mathcal{M}_{k}|}{\mathsf{M}}, (7) and NDT is defined as \mathsf{\Delta}\triangleq\varliminf_{\mathsf{P}\to\infty}\varliminf_{\mathsf{A}\to\infty}\frac{\mathsf{n}}{\mathsf{A}\,\mathsf{K}\,\mathsf{M}}\log\mathsf{P}. (8) We define the optimal NDT–computation tradeoff \Delta^{*}(\mathsf{r}) as the infimum of all \mathsf{\Delta} for which there exist file assignments \{\mathcal{M}_{k}\} and encoding/decoding functions satisfying \Pr\!\left[\bigcup_{k\in[\mathsf{K}]}\bigcup_{p\notin\mathcal{M}_{k}}\hat{a}_{k,p}\neq a_{k,p}\right]\to 0\quad\text{as }\mathsf{A}\to\infty. (9) In this work, we choose a the well known combinatorial file assignment for the wireless MapReduce system. Specifically, the input files \{W_{1},\ldots,W_{\mathsf{M}}\} are partitioned into \binom{\mathsf{K}}{\mathsf{r}} disjoint bundles, each associated with a size- \mathsf{r} subset \mathcal{T}\in[[\mathsf{K}]]^{\mathsf{r}} and stored at the nodes in \mathcal{T} . Since each file is stored at exactly \mathsf{r} nodes, this assignment satisfies the computation load constraint. II-A Relation with \mathsf{r} -fold cooperative channel Under this combinatorial file assignment, the Shuffle phase naturally induces a wireless channel with \mathsf{r} -fold transmitter cooperation. In particular, consider the wireless interference channel described in ( 5 ) under the average power constraint ( 4 ). For a given \mathsf{r}\in[\mathsf{K}] , any subset of \mathsf{r} nodes \mathcal{T}\in[[\mathsf{K}]]^{\mathsf{r}} jointly holds a message a_{k,\mathcal{T}} intended for Node k , for each k\in[\mathsf{K}]\setminus\mathcal{T} . Each message a_{k,\mathcal{T}} is uniformly distributed over