Robust and Scalable Renaming with Subquadratic Bits

Sirui Bai, Xinyu Fu, Yuheng Wang +2

In the renaming problem, a set of $n$ nodes, each with a unique identity from a large namespace $[N]$, needs to obtain new unique identities in a smaller namespace $[M]$. A renamin…