Optimal Uncoordinated Unique IDs

In the Uncoordinated Unique Identifiers Problem (UUIDP) there are $n$ independent instances of an algorithm $\mathcal{A}$ that generates IDs from a universe $\{1, \dots, m\}$, and there is an adversary that requests IDs from these instances. The goal is to design $\mathcal{A}$ such that it minimizes the probability that the same ID is ever generated twice across all instances, that is, minimizes the collision probability. Crucially, no communication between the instances of $\mathcal{A}$ is possible. Solutions to the UUIDP are often used as mechanisms for surrogate key generation in distributed databases and key-value stores. In spite of its practical relevance, we know of no prior theoretical work on the UUIDP. In this paper we initiate the systematic study of the UUIDP. We analyze both existing and novel algorithms for this problem, and evaluate their collision probability using worst-case analysis and competitive analysis, against oblivious and adaptive adversaries. In particular, we present an algorithm that is optimal in the worst case against oblivious adversaries, an algorithm that is at most a logarithmic factor away from optimal in the worst case against adaptive adversaries, and an algorithm that is optimal in the competitive sense against both oblivious and adaptive adversaries.