Computing in additive networks with bounded-information codes

DOI10.1007/978-3-662-48653-5_27MaRDI QIDQ1664154zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, E. Kantor, M. Parter, Nancy Lynch

Publication date 24 August 2018

Full work available at URL https://arxiv.org/abs/1508.03660, http://hdl.handle.net/1721.1/111687

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12)

Abstract: This paper studies the theory of the additive wireless network model, in which the received signal is abstracted as an addition of the transmitted signals. Our central observation is that the crucial challenge for computing in this model is not high contention, as assumed previously, but rather guaranteeing a bounded amount of emph{information} in each neighborhood per round, a property that we show is achievable using a new random coding technique. Technically, we provide efficient algorithms for fundamental distributed tasks in additive networks, such as solving various symmetry breaking problems, approximating network parameters, and solving an emph{asymmetry revealing} problem such as computing a maximal input. The key method used is a novel random coding technique that allows a node to successfully decode the received information, as long as it does not contain too many distinct values. We then design our algorithms to produce a limited amount of information in each neighborhood in order to leverage our enriched toolbox for computing in additive networks.

Recommendations

• Bounded-contention coding for the additive network model
• Bounded-contention coding for wireless networks in the high SNR regime
• Faster information dissemination in dynamic networks via network coding
• On the computational power of radio channels
• Broadcasting in noisy radio networks

Cited in

(3)

• Entropies of the automata networks with additive rule
• Bounded-contention coding for wireless networks in the high SNR regime
• Bounded-contention coding for the additive network model

This page was built for publication: Computing in additive networks with bounded-information codes

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