---
res:
  bibo_abstract:
  - 'Most people believe that renaming is easy: simply choose a name at random; if
    more than one process selects the same name, then try again. We highlight the
    issues that occur when trying to implement such a scheme and shed new light on
    the read-write complexity of randomized renaming in an asynchronous environment.
    At the heart of our new perspective stands an adaptive implementation of a randomized
    test-and-set object, that has poly-logarithmic step complexity per operation,
    with high probability. Interestingly, our implementation is anonymous, as it does
    not require process identifiers. Based on this implementation, we present two
    new randomized renaming algorithms. The first ensures a tight namespace of n names
    using O( n log4 n) total steps, with high probability. This significantly improves
    on the complexity of the best previously known namespace-optimal algorithms. The
    second algorithm achieves a namespace of size k (1 + ε) using O( k log4 k / log2
    (1 + ε) ) total steps, both with high probability, where k is the total contention
    in the execution. It is the first adaptive randomized renaming algorithm, and
    it improves on existing deterministic solutions by providing a smaller namespace,
    and by lowering step complexity.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Dan-Adrian
      foaf_name: Alistarh, Dan-Adrian
      foaf_surname: Alistarh
      foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-3650-940X
  - foaf_Person:
      foaf_givenName: Hagit
      foaf_name: Attiya, Hagit
      foaf_surname: Attiya
  - foaf_Person:
      foaf_givenName: Seth
      foaf_name: Gilbert, Seth
      foaf_surname: Gilbert
  - foaf_Person:
      foaf_givenName: Andrei
      foaf_name: Giurgiu, Andrei
      foaf_surname: Giurgiu
  - foaf_Person:
      foaf_givenName: Rachid
      foaf_name: Guerraoui, Rachid
      foaf_surname: Guerraoui
  bibo_doi: 10.1007/978-3-642-15763-9_9
  bibo_volume: 6343 LNCS
  dct_date: 2010^xs_gYear
  dct_language: eng
  dct_publisher: Springer@
  dct_title: Fast randomized test-and-set and renaming@
...