TY - GEN

T1 - Optimal Uncoordinated Unique IDs

AU - Dillinger, Peter C.

AU - Farach-Colton, Martin

AU - Tagliavini, Guido

AU - Walzer, Stefan

N1 - Publisher Copyright:
© 2023 ACM.

PY - 2023/6/18

Y1 - 2023/6/18

N2 - In the Uncoordinated Unique Identifiers Problem (UUIDP) there are n independent instances of an algorithm A that generates IDs from a universe (1, .., m) , and there is an adversary that requests IDs from these instances. The goal is to design 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 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.

AB - In the Uncoordinated Unique Identifiers Problem (UUIDP) there are n independent instances of an algorithm A that generates IDs from a universe (1, .., m) , and there is an adversary that requests IDs from these instances. The goal is to design 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 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.

KW - GUID

KW - uncoordinated

KW - unique identifiers

KW - UUID

UR - http://www.scopus.com/inward/record.url?scp=85164252801&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85164252801&partnerID=8YFLogxK

U2 - 10.1145/3584372.3588674

DO - 10.1145/3584372.3588674

M3 - Conference contribution

AN - SCOPUS:85164252801

T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

SP - 221

EP - 230

BT - PODS 2023 - Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

PB - Association for Computing Machinery

T2 - 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023

Y2 - 18 June 2023 through 23 June 2023

ER -