Abstract. Long-lived renaming allows
processes to repeatedly get distinct names from a small name space and
release these names. This paper presents two long-lived renaming
algorithms in which the name a process gets is bounded above by the
number of processes currently occupying a name or performing one of
these operations. The first is asynchronous, uses LLSC objects, and has
step complexity that is linear in the number of processes, c, currently getting or releasing a
name. The second is synchronous, uses registers and counters, and has
step complexity that is polylogarithmic in c. Both tolerate any number of
process crashes.