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

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).

Link to Full Text

Share

COinS