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. Computing with Reads and Writes in the Absence of Step Contention
 
conference paper

Computing with Reads and Writes in the Absence of Step Contention

Hagit, Attiya
•
Guerraoui, Rachid  
•
Kouznetsov, Petr  
2005
DISC 2005: Distributed Computing
19th International Symposium on Distributed Computing (DISC'05)

This paper studies implementations of concurrent objects that exploit the absence of step contention. These implementations use only reads and writes when a process is running solo. The other processes might be busy with other objects, swapped-out, failed, or simply delayed by a contention manager. We study in this paper two classes of such implementations, according to how they handle the case of step contention. The first kind, called obstruction-free implementations, are not required to terminate in that case. The second kind, called solo-fast implementations, terminate using powerful operations (e.g., C\S). We present a generic obstruction-free object implementation that has a linear contention-free step complexity (number of reads and writes taken by a process running solo) and uses a linear number of read/write objects. We show that these complexities are asymptotically optimal, and hence generic obstruction-free implementations are inherently slow. We also prove that obstruction-free implementations cannot be gracefully degrading, namely, be nonblocking when the contention manager operates correctly, and remain (at least) obstruction-free when the contention manager misbehaves. Finally, we show that any object has a solo-fast implementation, based on a solo-fast implementation of consensus. The implementation has linear contention-free step complexity, and we conjecture solo-fast implementations must have non-constant step complexity, i.e., they are also inherently slow.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1007/11561927_11
Author(s)
Hagit, Attiya
Guerraoui, Rachid  
Kouznetsov, Petr  
Date Issued

2005

Published in
DISC 2005: Distributed Computing
Start page

122

End page

136

Subjects

shared memory

•

contention

•

step contention

•

solo-fast

•

obstruction-free

•

lock-free

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event name
19th International Symposium on Distributed Computing (DISC'05)
Available on Infoscience
July 13, 2005
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/214749
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