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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This does not include the \(\varTheta (\log m/\log \log m)\)-step m-valued conflict detector that appears in [5], but does include a simpler \(\varTheta (\log m)\)-step conflict detector in which a write of a value whose bits are \(x_{k-1},\dots , x_0\) is done by setting to 1 the corresponding bits \(A[i][x_i]\) in a \(k \times 2\) array A.
- 2.
For the purpose of obtaining only a non-blocking SWSR write-once register, it is sufficient to construct an infinite array of m-bit locations to which the writer writes in increasing order and the reader searches for the last written location. However, we use here a max-register based implementation in order to build upon it when constructing our following wait-free SWSR and MWMR implementations.
References
Aghazadeh, Z., Woelfel, P.: On the time and space complexity of ABA prevention and detection. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, (PODC), pp. 193–202 (2015)
Alistarh, D., Aspnes, J.: Sub-logarithmic test-and-set against a weak adversary. In: Peleg, D. (ed.) DISC 2011. LNCS, vol. 6950, pp. 97–109. Springer, Heidelberg (2011). doi:10.1007/978-3-642-24100-0_7
Aspnes, J., Attiya, H., Censor-Hillel, K.: Polylogarithmic concurrent data structures from monotone circuits. J. ACM 59(1), 2 (2012)
Aspnes, J., Censor-Hillel, K.: Atomic snapshots in \(O(\log ^{3} n)\) steps using randomized helping. In: Proceedings of the 27th International Symposium on Distributed Computing, (DISC), pp. 254–268 (2013)
Aspnes, J., Ellen, F.: Tight bounds for adopt-commit objects. Theor. Comput. Syst. 55(3), 451–474 (2014)
Attiya, H., Fouren, A.: Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput. 31(2), 642–664 (2001)
Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley, Chichester (2004)
Balakrishnan, M., Malkhi, D., Davis, J.D., Prabhakaran, V., Wei, M., Wobber, T.: CORFU: a distributed shared log. ACM Trans. Comput. Syst. 31(4), 10:1–10:24 (2013)
Bhatia, A., Iyengar, A., Siegel, P.H.: Multilevel 2-cell \(t\)-write codes. In: IEEE Information Theory Workshop (ITW) (2012)
Borowsky, E., Gafni, E., Lynch, N.A., Rajsbaum, S.: The BG distributed simulation algorithm. Distrib. Comput. 14(3), 127–146 (2001)
Burshtein, D., Strugatski, A.: Polar write once memory codes. IEEE Trans. Inf. Theory 59(8), 5088–5101 (2013)
Cassuto, Y., Yaakobi, E.: Short (Q)-ary fixed-rate WOM codes for guaranteed rewrites and with hot/cold write differentiation. IEEE Trans. Inf. Theory 60(7), 3942–3958 (2014)
Cohen, G.D., Godlewski, P., Merkx, F.: Linear binary code for write-once memories. IEEE Trans. Inf. Theory 32(5), 697–700 (1986)
Gad, E.E., Wentao, H., Li, Y., Bruck, J.: Rewriting flash memories by message passing. In: IEEE International Symposium on Information Theory (ISIT) (2015)
Fiat, A., Shamir, A.: Generalized ‘write-once’ memories. IEEE Trans. Inf. Theory 30(3), 470–479 (1984)
Fu, F.-W., Han Vinck, A.J.: On the capacity of generalized write-once memory with state transitions described by an arbitrary directed acyclic graph. IEEE Trans. Inf. Theory 45(1), 308–313 (1999)
Giakkoupis, G., Woelfel, P.: On the time and space complexity of randomized test-and-set. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, (PODC), pp. 19–28 (2012)
Godlewski, P.: WOM-codes construits à partir des codes de Hamming. Discrete Math. 65(3), 237–243 (1987)
Heegard, C.: On the capacity of permanent memory. IEEE Trans. Inf. Theory 31(1), 34–41 (1985)
Helmi, M., Higham, L., Woelfel, P.: Strongly linearizable implementations: possibilities and impossibilities. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, (PODC), pp. 385–394 (2012)
Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann, San Francisco (2008)
Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)
Inoue, M., Masuzawa, T., Chen, W., Tokura, N.: Linear-time snapshot using multi-writer multi-reader registers. In: Tel, G., Vitányi, P. (eds.) WDAG 1994. LNCS, vol. 857, pp. 130–140. Springer, Heidelberg (1994). doi:10.1007/BFb0020429
Israeli, A., Shaham, A.: Optimal multi-writer multi-reader atomic register. In: Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, PODC 1992, pp. 71–82, New York, NY, USA. ACM (1992)
Israeli, A., Shaham, A.: Time and space optimal implementations of atomic multi-writer register. Inf. Comput. 200(1), 62–106 (2005)
Jacobvitz, A.N., Calderbank, R., Sorin, D.J.: Coset coding to extend the lifetime of memory. In: IEEE 19th International Symposium on High Performance Computer Architecture (HPCA) (2013)
Kraft, L.G.: A device for quantizing, grouping, and coding amplitude-modulated pulses. M.S. thesis, Department of Electrical Engineering, Massachusetts Institute of Technology (1949)
Lamport, L.: On interprocess communication part I: basic formalism. Distrib. Comput. 1(2), 77–85 (1986)
Lamport, L.: On interprocess communication part II: algorithms. Distrib. Comput. 1(2), 86–101 (1986)
Li, J., Mohanram, K.: Write-once-memory-code phase change memory. In: Design, Automation and Test in Europe Conference and Exhibition (DATE) (2014)
Margaglia, F., Brinkmann, A.: Improving MLC flash performance and endurance with extended P/E cycles. In: IEEE 31st Symposium on Mass Storage Systems and Technologies (MSST) (2015)
Plotkin, S.A.: Sticky bits and universality of consensus. In: Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, PODC 1989, pp. 159–175, New York, NY, USA. ACM (1989)
Rivest, R.R., Shamir, A.: How to reuse a “write-once” memory. Inf. Control 55, 1–19 (1982)
Shpilka, A.: New constructions of WOM codes using the Wozencraft ensemble. IEEE Trans. Inf. Theory 59(7), 4520–4529 (2013)
Shpilka, A.: Capacity achieving multiwrite WOM codes. IEEE Trans. Inf. Theory 60(3), 1481–1487 (2014)
Wolf, J.K., Wyner, A.D., Ziv, J., Korner, J.: Coding for a write-once memory. AT&T Bell Laboratories Tech. J. 63(6), 1089–1112 (1984)
Yunnan, W.: Low complexity codes for writing a write-once memory twice. In: IEEE International Symposium on Information Theory (ISIT) (2010)
Wu, Y., Jiang, A.: Position modulation code for rewriting write-once memories. IEEE Trans. Inf. Theory 57(6), 3692–3697 (2011)
Yaakobi, E., Kayser, S., Siegel, P.H., Vardy, A., Wolf, J.K.: Codes for write-once memories. IEEE Trans. Inf. Theory 58(9), 5985–5999 (2012)
Yaakobi, E., Shpilka, A.: High sum-rate three-write and non-binary WOM codes. In: IEEE International Symposium on Information Theory (ISIT) (2012)
Yadgar, G., Yaakobi, E., Schuster, A.: Write once, get 50% free: saving SSD erase costs using WOM codes. In: 13th USENIX Conference on File and Storage Technologies (FAST) (2015)
Zhang, X., Jang, L., Zhang, Y., Zhang, C., Yang, J.: WoM-SET: low power proactive-SET-based PCM write using WoM code. In: IEEE International Symposium on Low Power Electronics and Design (ISLPED) (2013)
Acknowledgments
Keren Censor-Hillel is supported in part by the Israel Science Foundation (grant 1696/14). The authors thank the anonymous reviewers for helpful comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Aspnes, J., Censor-Hillel, K., Yaakobi, E. (2016). Concurrent Use of Write-Once Memory. In: Suomela, J. (eds) Structural Information and Communication Complexity. SIROCCO 2016. Lecture Notes in Computer Science(), vol 9988. Springer, Cham. https://doi.org/10.1007/978-3-319-48314-6_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-48314-6_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-48313-9
Online ISBN: 978-3-319-48314-6
eBook Packages: Computer ScienceComputer Science (R0)