Broadcasting on Random Networks
© 2019 IEEE. We study a generalization of the problem of broadcasting on trees to the setting of directed acyclic graphs (DAGs). At time 0, a source vertex X transmits a uniform bit along binary symmetric channels (BSCs) to a set of vertices called layer 1. Each vertex except X has indegree d. At ti...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021
|
| Online Access: | https://hdl.handle.net/1721.1/138083 |
| _version_ | 1826208941352157184 |
|---|---|
| author | Makur, Anuran Mossel, Elchanan Polyanskiy, Yury |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Makur, Anuran Mossel, Elchanan Polyanskiy, Yury |
| author_sort | Makur, Anuran |
| collection | MIT |
| description | © 2019 IEEE. We study a generalization of the problem of broadcasting on trees to the setting of directed acyclic graphs (DAGs). At time 0, a source vertex X transmits a uniform bit along binary symmetric channels (BSCs) to a set of vertices called layer 1. Each vertex except X has indegree d. At time k ≥ 1, vertices at layer k apply d-input Boolean processing functions to their received bits and send out the results to vertices at layer k + 1. We say that broadcasting is possible if we can reconstruct X with probability of error bounded away from frac{1}{2} using the values of all vertices at an arbitrarily deep layer k. This question is closely related to models of reliable computation and storage, probabilistic cellular automata, and information flow in biological networks.In this work, we analyze randomly constructed DAGs and demonstrate that broadcasting is only possible if the BSC noise level is below a certain (degree and function dependent) critical threshold. Specifically, for every d ≥ 3, we identify the critical threshold for random DAGs with layers of size (log(k)) and majority processing functions. For d = 2, we establish a similar result for the NAND processing function. Furthermore, for odd d ≥ 3, we prove that the identified thresholds cannot be improved by other processing functions if reconstruction is required from a single vertex. Finally, for any BSC noise level, in quasi-polynomial or randomized polylogarithmic time in the depth, we construct deterministic bounded degree DAGs with layers of size Θ(log(k)) that admit reconstruction using lossless expander graphs. |
| first_indexed | 2024-09-23T14:14:45Z |
| format | Article |
| id | mit-1721.1/138083 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:14:45Z |
| publishDate | 2021 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1380832021-11-10T03:17:06Z Broadcasting on Random Networks Makur, Anuran Mossel, Elchanan Polyanskiy, Yury Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics © 2019 IEEE. We study a generalization of the problem of broadcasting on trees to the setting of directed acyclic graphs (DAGs). At time 0, a source vertex X transmits a uniform bit along binary symmetric channels (BSCs) to a set of vertices called layer 1. Each vertex except X has indegree d. At time k ≥ 1, vertices at layer k apply d-input Boolean processing functions to their received bits and send out the results to vertices at layer k + 1. We say that broadcasting is possible if we can reconstruct X with probability of error bounded away from frac{1}{2} using the values of all vertices at an arbitrarily deep layer k. This question is closely related to models of reliable computation and storage, probabilistic cellular automata, and information flow in biological networks.In this work, we analyze randomly constructed DAGs and demonstrate that broadcasting is only possible if the BSC noise level is below a certain (degree and function dependent) critical threshold. Specifically, for every d ≥ 3, we identify the critical threshold for random DAGs with layers of size (log(k)) and majority processing functions. For d = 2, we establish a similar result for the NAND processing function. Furthermore, for odd d ≥ 3, we prove that the identified thresholds cannot be improved by other processing functions if reconstruction is required from a single vertex. Finally, for any BSC noise level, in quasi-polynomial or randomized polylogarithmic time in the depth, we construct deterministic bounded degree DAGs with layers of size Θ(log(k)) that admit reconstruction using lossless expander graphs. 2021-11-09T21:42:51Z 2021-11-09T21:42:51Z 2019-07 2019-11-18T13:35:47Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/138083 Makur, Anuran, Mossel, Elchanan and Polyanskiy, Yury. 2019. "Broadcasting on Random Networks." en 10.1109/isit.2019.8849393 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE MIT web domain |
| spellingShingle | Makur, Anuran Mossel, Elchanan Polyanskiy, Yury Broadcasting on Random Networks |
| title | Broadcasting on Random Networks |
| title_full | Broadcasting on Random Networks |
| title_fullStr | Broadcasting on Random Networks |
| title_full_unstemmed | Broadcasting on Random Networks |
| title_short | Broadcasting on Random Networks |
| title_sort | broadcasting on random networks |
| url | https://hdl.handle.net/1721.1/138083 |
| work_keys_str_mv | AT makuranuran broadcastingonrandomnetworks AT mosselelchanan broadcastingonrandomnetworks AT polyanskiyyury broadcastingonrandomnetworks |