Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Early Deciding Synchronous Renaming in O( logf ) Rounds or Less
 
conference paper

Early Deciding Synchronous Renaming in O( logf ) Rounds or Less

Alistarh, Dan  
•
Attiya, Hagit
•
Guerraoui, Rachid  
Show more
Even, Guy
•
Halldórsson, Magnús M.
2012
Structural Information and Communication Complexity
19th International Colloquium, SIROCCO

Renaming is a fundamental problem in distributed computing, in which a set of n processes need to pick unique names from a namespace of limited size. In this paper, we present the first early-deciding upper bounds for synchronous renaming, in which the running time adapts to the actual number of failures f in the execution. We show that, surprisingly, renaming can be solved in \emphconstant time if the number of failures f is limited to O(n√) , while for general f ≤ n − 1 renaming can always be solved in O( logf ) communication rounds. In the wait-free case, i.e. for f = n − 1, our upper bounds match the Ω( logn ) lower bound of Chaudhuri et al. [13].

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

early_F978-3-642-31104-8_17.pdf

Type

Preprint

Version

http://purl.org/coar/version/c_71e4c1898caa6e32

Access type

openaccess

Size

254.67 KB

Format

Adobe PDF

Checksum (MD5)

f126b78e917981aca114bce7e8105b37

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés