Concurrent use of write-once memory

James Aspnes, Keren Censor-Hillel, and Eitan Yaakobi. Concurrent use of write-once memory. Submitted to Journal of Parallel and Distributed Computing, January 2017. Last revised September 2017. An earlier version appeared in Structural Information and Communication Complexity - 23rd International Colloquium, SIROCCO 2016, Helsinki, Finland, July 19–21, 2016, Revised Selected Papers, July 2016, pp. 127–142.

Abstract

We consider the problem of implementing general shared-memory objects on top of write-once bits, which can be changed from 0 to 1 but not back again. In a sequential setting, write-once memory (WOM) codes have been developed that allow simulating memory that support multiple writes, even of large values, setting an average of 1+o(1) write-once bits per write. We show that similar space efficiencies can be obtained in a concurrent setting, though at the cost of high time complexity and fixed bound on the number of write operations. As an alternative, we give an implementation that permits unboundedly many writes and has much better amortized time complexity, but at the cost of unbounded space complexity. Whether one can obtain both low time complexity and low space complexity in the same implementation remains open.

BibTeX

Download
@inproceedings{AspnesCY2016,
  author    = {James Aspnes and
               Keren Censor{-}Hillel and
               Eitan Yaakobi},
  editor    = {Jukka Suomela},
  title     = {Concurrent Use of Write-Once Memory},
  booktitle = {Structural Information and Communication Complexity - 23rd International
               Colloquium, {SIROCCO} 2016, Helsinki, Finland, July 19-21, 2016, Revised
               Selected Papers},
  series    = {Lecture Notes in Computer Science},
  volume    = {9988},
  pages     = {127--142},
  year      = {2016},
  url       = {http://dx.doi.org/10.1007/978-3-319-48314-6_9},
  doi       = {10.1007/978-3-319-48314-6_9},
  timestamp = {Fri, 04 Nov 2016 10:15:49 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/sirocco/AspnesCY16},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page