Computer Science
Brief Announcement: Computability and Anonymous Storage-Efficient Consensus with an Abstract MAC Layer
Document Type
Conference Paper
Abstract
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. This paper presents a straightforward construction of the store-collect object, which then allows us to apply prior algorithms to solve many well-known distributed problems, such as multi-writer atomic registers, counters, atomic snapshot objects, and approximate and randomized consensus. Our construction does not require a priori information on the participating nodes. Our insight also leads to anonymous approximate consensus and randomized consensus algorithms that use a constant number of variables (or values). All of the algorithms are wait-free.
Publication Title
Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
Publication Date
2022
First Page
265
Last Page
267
ISBN
9781450392624
DOI
10.1145/3519270.3538462
Keywords
abstract MAC layer, computation power, consensus
Repository Citation
Tseng, Lewis and Zhang, Qinzi, "Brief Announcement: Computability and Anonymous Storage-Efficient Consensus with an Abstract MAC Layer" (2022). Computer Science. 101.
https://commons.clarku.edu/faculty_computer_sciences/101
APA Citation
Tseng, L., & Zhang, Q. (2022, July). Brief Announcement: Computability and Anonymous Storage-Efficient Consensus with an Abstract MAC Layer. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (pp. 265-267).
