Abstractions play a central role in distributed computing, as they capture essential synchronization properties. Equivalence results among abstractions clarify their relative computational power. While many such equivalences are well established in crash-prone systems, far less is known about Byzantine-prone environments, where faulty processes may behave arbitrarily. This paper revisits the equivalence landscape in Byzantine systems, with a particular focus on shared registers and broadcast abstractions. We establish three new reductions. Specifically, we prove that the broadcast abstraction called Byzantine Set-Constrained Delivery Broadcast (BSCD-Broadcast) can implement a Snapshot/Append object and vice versa (I.e., a two-way reduction), and that the FIFO variant of the renowned Byzantine Reliable Broadcast (BRB-Broadcast) can implement BSCD-Broadcast under a majority of correct processes. Interestingly, this assumption mirrors the one required in crash-prone systems for a similar transformation.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Invited Paper: On the Equivalence of Snapshot/Append Objects and Broadcast Abstractions under Byzantine Failures

  • Vincent Kowalski,
  • Achour Mostefaoui,
  • Matthieu Perrin,
  • Jolan Riallo

摘要

Abstractions play a central role in distributed computing, as they capture essential synchronization properties. Equivalence results among abstractions clarify their relative computational power. While many such equivalences are well established in crash-prone systems, far less is known about Byzantine-prone environments, where faulty processes may behave arbitrarily. This paper revisits the equivalence landscape in Byzantine systems, with a particular focus on shared registers and broadcast abstractions. We establish three new reductions. Specifically, we prove that the broadcast abstraction called Byzantine Set-Constrained Delivery Broadcast (BSCD-Broadcast) can implement a Snapshot/Append object and vice versa (I.e., a two-way reduction), and that the FIFO variant of the renowned Byzantine Reliable Broadcast (BRB-Broadcast) can implement BSCD-Broadcast under a majority of correct processes. Interestingly, this assumption mirrors the one required in crash-prone systems for a similar transformation.