Brief Announcement: Optimal Construction of Unique Identifiers from Bounded Registers
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.
Authors
- Vitaly Aksenov (ORCID: https://orcid.org/0000-0001-9134-5490)
- Petr Kuznetsov (ORCID: https://orcid.org/0000-0003-1148-1228)
- Michael Anoprenko
Institutions
- Télécom Paris (FR)
- St George's, University of London (GB)
- Institut Polytechnique de Paris (FR)
- Laboratoire Traitement et Communication de l’Information (FR)
- City St George's, University of London (GB)
Publication Details
- Published
- 2025-06-13
- DOI
- https://doi.org/10.1145/3732772.3733539
- Primary Topic
- Distributed systems and fault tolerance
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Agence Nationale de la Recherche
- CHIST-ERA