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.
翻译:在无协调唯一标识符问题(UUIDP)中,有$n$个独立的算法$\mathcal{A}$实例生成从宇宙$\{1,\dots,m\}$中的标识符,并且存在对这些实例请求标识符的对手。目标是设计$\mathcal{A}$,使得在所有实例中甚至不会再次生成相同的标识符,即最小化碰撞概率。至关重要的是,实例之间没有通信可行。UUIDP的解决方案通常用作分布式数据库和键值存储中的替代键生成机制。尽管其实用价值很高,但我们不知道先前任何UUIDP的理论研究。本文开始了对UUIDP的系统研究。我们分析了现有算法和用于解决这个问题的新算法,并使用最坏情况分析和竞争性分析来评估其碰撞概率,以针对显性和自适应对手。特别地,我们提出了一种算法,在显性对手的最坏情况下是最优的,并提出了一种算法,它在自适应对手的最坏情况下至多比最优情况差一个对数因子,并提出了一种算法,它对显性和自适应对手来说是在竞争意义上最优的。