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. A paradox of eventual linearizability in shared memory
 
conference paper

A paradox of eventual linearizability in shared memory

Guerraoui, Rachid  
•
Ruppert, Eric
2014
Proceedings of the 2014 ACM symposium on Principles of distributed computing - PODC '14
the 2014 ACM symposium

This paper compares, for the rst time, the computational power of linearizable objects with that of eventually linearizable ones. We present the following paradox. We show that, unsurprisingly, no set of eventually linearizable objects can (1) implement any non-trivial linearizable object, nor (2) boost the consensus power of simple objects like linearizable registers. We also show, perhaps surprisingly, that any implementation of an eventually linearizable complex object like a fetch&increment counter (from linearizable base objects), can itself be viewed as a fully linearizable implementation of the same fetch&increment counter (using the exact same set of base objects)

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1145/2611462.2611484
Author(s)
Guerraoui, Rachid  
Ruppert, Eric
Date Issued

2014

Publisher

ACM Press

Publisher place

New York, New York, USA

Published in
Proceedings of the 2014 ACM symposium on Principles of distributed computing - PODC '14
Start page

40

End page

49

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent placeEvent date
the 2014 ACM symposium

Paris, France

15-18 07 2014

Available on Infoscience
May 28, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/114127
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