Brief Announcement: Optimal Construction of Unique Identifiers from Bounded Registers
Michael Anoprenko, Petr Kuznetsov, Vitaly Aksenov · 2025
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.