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的系统研究。我们分析了现有算法和用于解决这个问题的新算法,并使用最坏情况分析和竞争性分析来评估其碰撞概率,以针对显性和自适应对手。特别地,我们提出了一种算法,在显性对手的最坏情况下是最优的,并提出了一种算法,它在自适应对手的最坏情况下至多比最优情况差一个对数因子,并提出了一种算法,它对显性和自适应对手来说是在竞争意义上最优的。

0
下载
关闭预览

相关内容

标识符(identifier)是指用来标识某个实体的一个符号,在不同的应用环境下有不同的含义。在计算机编程语言中,标识符是用户编程时使用的名字,用于给变量、常量、函数、语句块等命名,以建立起名称与使用之间的关系。标识符通常由字母和数字以及其它字符构成。
多智能体顶级会议AAMAS2022最佳论文
专知会员服务
60+阅读 · 2022年5月15日
Artificial Intelligence: Ready to Ride the Wave? BCG 28页PPT
专知会员服务
26+阅读 · 2022年2月20日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
163+阅读 · 2020年3月18日
机器学习相关资源(框架、库、软件)大列表
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | EMNLP 2019等国际会议信息6条
Call4Papers
18+阅读 · 2019年4月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年6月1日
Arxiv
0+阅读 · 2023年5月30日
Arxiv
0+阅读 · 2023年5月30日
VIP会员
相关VIP内容
多智能体顶级会议AAMAS2022最佳论文
专知会员服务
60+阅读 · 2022年5月15日
Artificial Intelligence: Ready to Ride the Wave? BCG 28页PPT
专知会员服务
26+阅读 · 2022年2月20日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
163+阅读 · 2020年3月18日
机器学习相关资源(框架、库、软件)大列表
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | EMNLP 2019等国际会议信息6条
Call4Papers
18+阅读 · 2019年4月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关基金
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员