Computing in Additive Networks with Bounded-Information Codes
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 guar...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2017
|
| Online Access: | http://hdl.handle.net/1721.1/111687 https://orcid.org/0000-0003-3809-8990 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0002-2357-2445 |
| _version_ | 1811087576193302528 |
|---|---|
| author | Censor-Hillel, Keren Kantor, Erez Lynch, Nancy Ann Parter, Merav |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Censor-Hillel, Keren Kantor, Erez Lynch, Nancy Ann Parter, Merav |
| author_sort | Censor-Hillel, Keren |
| collection | MIT |
| description | 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 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 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. |
| first_indexed | 2024-09-23T13:48:17Z |
| format | Article |
| id | mit-1721.1/111687 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:48:17Z |
| publishDate | 2017 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1116872022-09-28T16:20:02Z Computing in Additive Networks with Bounded-Information Codes Censor-Hillel, Keren Kantor, Erez Lynch, Nancy Ann Parter, Merav Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Kantor, Erez Lynch, Nancy Ann Parter, Merav 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 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 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. National Science Foundation (U.S.) (Award CCF-1217506) National Science Foundation (U.S.) (Award CCF-AF-0937274) National Science Foundation (U.S.) (Award CCF-0939370) United States. Air Force Office of Scientific Research (Contract FA9550-14-1-0403) United States. Air Force Office of Scientific Research (Contract FA9550-13-1-0042) 2017-10-03T19:14:33Z 2017-10-03T19:14:33Z 2015-11 Article http://purl.org/eprint/type/ConferencePaper 978-3-662-48652-8 978-3-662-48653-5 0302-9743 1611-3349 http://hdl.handle.net/1721.1/111687 Censor-Hillel, Keren et al. “Computing in Additive Networks with Bounded-Information Codes.” Distributed Computing (November 2015): 405–419 © 2015 Springer-Verlag https://orcid.org/0000-0003-3809-8990 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0002-2357-2445 en_US http://dx.doi.org/10.1007/978-3-662-48653-5_27 Distributed Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Censor-Hillel, Keren Kantor, Erez Lynch, Nancy Ann Parter, Merav Computing in Additive Networks with Bounded-Information Codes |
| title | Computing in Additive Networks with Bounded-Information Codes |
| title_full | Computing in Additive Networks with Bounded-Information Codes |
| title_fullStr | Computing in Additive Networks with Bounded-Information Codes |
| title_full_unstemmed | Computing in Additive Networks with Bounded-Information Codes |
| title_short | Computing in Additive Networks with Bounded-Information Codes |
| title_sort | computing in additive networks with bounded information codes |
| url | http://hdl.handle.net/1721.1/111687 https://orcid.org/0000-0003-3809-8990 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0002-2357-2445 |
| work_keys_str_mv | AT censorhillelkeren computinginadditivenetworkswithboundedinformationcodes AT kantorerez computinginadditivenetworkswithboundedinformationcodes AT lynchnancyann computinginadditivenetworkswithboundedinformationcodes AT partermerav computinginadditivenetworkswithboundedinformationcodes |