Graph Codes for Distributed Instant Message Collection in an Arbitrary Noisy Broadcast Network

DOI10.1109/TIT.2017.2725267MaRDI QIDQ4589430zbMATH OpenOpenAlexFDO

Authors Yaoqing Yang, Soummya Kar, Pulkit Grover

Publication date 10 November 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.01553

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We consider the problem of minimizing the number of broadcasts for collecting all sensor measurements at a sink node in a noisy broadcast sensor network. Focusing first on arbitrary network topologies, we provide (i) fundamental limits on the required number of broadcasts of data gathering, and (ii) a general in-network computing strategy to achieve an upper bound within factor $logN$ of the fundamental limits, where $N$ is the number of agents in the network. Next, focusing on two example networks, namely, extcolor{black}{arbitrary geometric networks and random Erd$ddoto$s-R$acutee$nyi networks}, we provide improved in-network computing schemes that are optimal in that they attain the fundamental limits, i.e., the lower and upper bounds are tight extcolor{black}{in order sense}. Our main techniques are three distributed encoding techniques, called graph codes, which are designed respectively for the above-mentioned three scenarios. Our work thus extends and unifies previous works such as those of Gallager [1] and Karamchandani~emph{et. al.} [2] on number of broadcasts for distributed function computation in special network topologies, while bringing in novel techniques, e.g., from error-control coding and noisy circuits, for both upper and lower bounds.

Cited in

(1)

• Redundancy techniques for straggler mitigation in distributed optimization and learning

This page was built for publication: Graph Codes for Distributed Instant Message Collection in an Arbitrary Noisy Broadcast Network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589430)