Brief Announcement: Optimal Construction of Unique Identifiers from Bounded Registers
Anoprenko, M., Kuznetsov, P. & Aksenov, V. 
ORCID: 0000-0001-9134-5490 (2025).
Brief Announcement: Optimal Construction of Unique Identifiers from Bounded Registers.
In:
Proceedings of the ACM Symposium on Principles of Distributed Computing.
PODC '25: ACM Symposium on Principles of Distributed Computing, 16-20 Jun 2025, Huatulco, Mexico.
doi: 10.1145/3732772.3733539
Abstract
In this paper, we describe an algorithm implementing the unique-id abstraction from bounded-storage registers maintaining read, write, and FAI operations. Given k registers, storing w bits each, our implementation generates up to (k - 1) · 2w unique identifiers, assuming that k ≤ 2w + 1. We show that this is asymptotically optimal: no unique-id implementation can produce more than k · 2w + k + 1 identifiers.
| Publication Type: | Conference or Workshop Item (Paper) |
|---|---|
| Additional Information: | This work is licensed under a Creative Commons Attribution International 4.0 License. © 2025 Copyright held by the owner/author(s). |
| Publisher Keywords: | concurrency, bounded memory, unique identifiers |
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| Departments: | School of Science & Technology School of Science & Technology > Computer Science |
| SWORD Depositor: |
Available under License Creative Commons: Attribution International Public License 4.0.
Download (524kB) | Preview
Export
Downloads
Downloads per month over past year
Metadata
MetadataActions (login required)
Admin Login