Invited Paper: On the Equivalence of Snapshot/Append Objects and Broadcast Abstractions under Byzantine Failures
摘要
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.