Consensus Capacity of Noisy Broadcast Channels
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910893491617792 |
|---|---|
| author | Sangwan, Neha Narayanan, Varun Prabhakaran, Vinod M. |
| author_facet | Sangwan, Neha Narayanan, Varun Prabhakaran, Vinod M. |
| contents | We study communication with consensus over a broadcast channel - the receivers reliably decode the sender's message when the sender is honest, and their decoder outputs agree even if the sender acts maliciously. We characterize the broadcast channels which permit this byzantine consensus and determine their capacity. We show that communication with consensus is possible only when the broadcast channel has embedded in it a natural ''common channel'' whose output both receivers can unambiguously determine from their own channel outputs. Interestingly, in general, the consensus capacity may be larger than the point-to-point capacity of the common channel, i.e., while decoding, the receivers may make use of parts of their output signals on which they may not have consensus provided there are some parts (namely, the common channel output) on which they can agree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_06073 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Consensus Capacity of Noisy Broadcast Channels Sangwan, Neha Narayanan, Varun Prabhakaran, Vinod M. Information Theory Cryptography and Security Distributed, Parallel, and Cluster Computing We study communication with consensus over a broadcast channel - the receivers reliably decode the sender's message when the sender is honest, and their decoder outputs agree even if the sender acts maliciously. We characterize the broadcast channels which permit this byzantine consensus and determine their capacity. We show that communication with consensus is possible only when the broadcast channel has embedded in it a natural ''common channel'' whose output both receivers can unambiguously determine from their own channel outputs. Interestingly, in general, the consensus capacity may be larger than the point-to-point capacity of the common channel, i.e., while decoding, the receivers may make use of parts of their output signals on which they may not have consensus provided there are some parts (namely, the common channel output) on which they can agree. |
| title | Consensus Capacity of Noisy Broadcast Channels |
| topic | Information Theory Cryptography and Security Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2205.06073 |