Consensus Capacity of Noisy Broadcast Channels

• URL: http://arxiv.org/abs/2205.06073v4
• Date: Wed, 26 Mar 2025 06:39:33 GMT
• Title: Consensus Capacity of Noisy Broadcast Channels
• Authors: Neha Sangwan, Varun Narayanan, Vinod M. Prabhakaran,
• Abstract summary: Communication with consensus is possible only when the broadcast channel has embedded in it a natural ''common channel''<n>We show that communication with consensus is possible only when the broadcast channel has embedded in it a natural ''common channel''
• Score: 8.228995613609118
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Capacity Formulas for the Lossy Bosonic Compound Wiretap Channel [1.534667887016089]
  A pair of lossy channels connects a sender with both a (legitimate) receiver and an eavesdropper. The sender and receiver have only partial information about the actual state of the channels. We prove capacity formulas for the case where both sender and receiver have the same information about the system.
  arXiv  Detail & Related papers  (2025-04-29T15:43:18Z)
• String commitment from unstructured noisy channels [53.04878543623513]
  Noisy channels are valuable resources for cryptography, enabling primitives like bit commitment and oblivious transfer.<n>We present a protocol for string commitment over such channels that is complete, hiding, and binding, and derive its achievable commitment rate.<n>The commitment rate coincides with previous results when the adversarial channels are the same binary symmetric channel as in the honest case.
  arXiv  Detail & Related papers  (2024-12-31T05:28:05Z)
• The Interference Channel with Entangled Transmitters [9.86463469466224]
  It explores communication over a two-sender, two-receiver classical interference channel, enhanced by the availability of entanglement resources between transmitters.<n>It addresses the persistent challenge of the lack of a general capacity formula, even in the purely classical case, and highlights the striking similarities in achievable rate expressions when assessing quantum advantages.
  arXiv  Detail & Related papers  (2024-11-15T09:33:02Z)
• Resolvability of classical-quantum channels [54.825573549226924]
  We study the resolvability of classical-quantum channels in two settings, for the channel output generated from the worst input, and form the fixed independent and identically distributed (i.i.d.) input. For the fixed-input setting, while the direct part follows from the known quantum soft covering result, we exploit the recent alternative quantum Sanov theorem to solve the strong converse.
  arXiv  Detail & Related papers  (2024-10-22T05:18:43Z)
• Fault-tolerant Coding for Entanglement-Assisted Communication [46.0607942851373]
  This paper studies the study of fault-tolerant channel coding for quantum channels. We use techniques from fault-tolerant quantum computing to establish coding theorems for sending classical and quantum information in this scenario. We extend these methods to the case of entanglement-assisted communication, in particular proving that the fault-tolerant capacity approaches the usual capacity when the gate error approaches zero.
  arXiv  Detail & Related papers  (2022-10-06T14:09:16Z)
• Identification Over Quantum Broadcast Channels [19.465727478912072]
  The decoder only identifies whether a message of his choosing was sent or not. An achievable identification region is derived for a quantum broadcast channel. Results are demonstrated for the quantum erasure broadcast channel, where our region is suboptimal, but improves on the best previously known bounds.
  arXiv  Detail & Related papers  (2022-01-26T17:00:03Z)
• Dense Coding with Locality Restriction for Decoder: Quantum Encoders vs. Super-Quantum Encoders [67.12391801199688]
  We investigate dense coding by imposing various locality restrictions to our decoder. In this task, the sender Alice and the receiver Bob share an entangled state.
  arXiv  Detail & Related papers  (2021-09-26T07:29:54Z)
• Undoing Causal Effects of a Causal Broadcast Channel with Cooperating Receivers using Entanglement Resources [0.0]
  We analyse a communication scenario over a causal broadcast channel whose state depends on a modulo sum. We find that when the receivers can share entanglement and communicate classically, they can receive messages at a non-zero rate with verifiable secure collaboration.
  arXiv  Detail & Related papers  (2021-02-15T10:05:04Z)
• Quantum Broadcast Channels with Cooperating Decoders: An Information-Theoretic Perspective on Quantum Repeaters [78.7611537027573]
  Communication over a quantum broadcast channel with cooperation between the receivers is considered. We develop lower and upper bounds on the capacity region in each setting.
  arXiv  Detail & Related papers  (2020-11-18T11:58:48Z)
• Quantum Channel State Masking [78.7611537027573]
  Communication over a quantum channel that depends on a quantum state is considered when the encoder has channel side information (CSI) and is required to mask information on the quantum channel state from the decoder. A full characterization is established for the entanglement-assisted masking equivocation region, and a regularized formula is given for the quantum capacity-leakage function without assistance.
  arXiv  Detail & Related papers  (2020-06-10T16:18:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.