English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

Optimal Uncoordinated Unique IDs