@inproceedings{b870eb6785114e4fbdf4b38962b1bd8a,
title = "Brief Announcement: Optimal Construction of Unique Identifiers from Bounded Registers",
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.",
keywords = "bounded memory, concurrency, unique identifiers",
author = "Michael Anoprenko and Petr Kuznetsov and Vitaly Aksenov",
note = "Publisher Copyright: {\textcopyright} 2025 Copyright held by the owner/author(s).; 44th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2025 ; Conference date: 16-06-2025 Through 20-06-2025",
year = "2025",
month = jun,
day = "13",
doi = "10.1145/3732772.3733539",
language = "English",
series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",
publisher = "Association for Computing Machinery",
pages = "62--65",
booktitle = "PODC 2025 - Proceedings of the 2025 ACM Symposium on Principles of Distributed Computing",
}