Brief Announcement: Computability and Anonymous Storage-Efficient Consensus with an Abstract MAC Layer
Lewis Tseng, Qinzi Zhang · 2022
This paper explores fault-tolerant algorithms in the abstract MAC layer [7] in a single-hop network. The model captures the basic properties of modern wireless MAC protocols. Newport [11] proves that it is impossible to achieve deterministic fault-tolerant consensus, and Newport and Robinson [10] present randomized crash-tolerant consensus algorithms. We are not aware of any study on the computability in this model.