Abstract
We address the problem of emulating a shared read/write memory in a message passing system using a storage server prone to Byzantine failures. Although cryptography can be used to ensure confidentiality and integrity of the data, nothing can prevent a malicious server from returning obsolete data. Fork-linearizability [1] guarantees that if a malicious server hides an update of some client from another client, then these two clients will never see each others’ updates again. Fork-linearizability is arguably the strongest consistency property attainable in the presence of a malicious server. Recent work [2] has shown that there is no fork-linearizable shared memory emulation that supports wait-free operations. On the positive side, it has been shown that lock-based emulations exist [1,2]. Lock-based protocols are fragile because they are blocking if clients may crash. In this paper we present for the first time lock-free emulations of fork-linearizable shared memory. We have developed two protocols, Linear and Concur. With a correct server, both protocols guarantee linearizability and that every operation successfully completes in the absence of step contention, while interfering operations terminate by aborting. The Concur algorithm additionally ensures that concurrent operations invoked on different registers complete successfully.
Research funded in part by IBM Faculty Award, Microsoft Research, and DFG GRK 1362 (TUD GKmM).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Mazières, D., Shasha, D.: Building Secure File Systems out of Byzantine Storage. In: PODC, pp. 108–117. ACM, New York (2002)
Cachin, C., Shelat, A., Shraer, A.: Efficient Fork-Linearizable Access to Untrusted Shared Memory. In: PODC, pp. 129–138. ACM, New York (2007)
Cachin, C., Keidar, I., Shraer, A.: Trusting the Cloud. ACM SIGACT News, Distributed Computing in the Clouds 40(2), 81–86 (2009)
CVS: Concurrent Versions System (visited) (June 2009), http://www.nongnu.org/cvs/
SVN: Subversion (visited) (June 2009), http://subversion.tigris.org/
Whitehead Jr., E.J.: World Wide Web Distributed Authoring and Versioning (WebDAV): An Introduction. Standard View 5(1), 3–8 (1997)
Yang, J., Wang, H., Gu, N., Liu, Y., Wang, C., Zhang, Q.: Lock-free Consistency Control for Web 2.0 Applications. In: WWW, pp. 725–734. ACM, New York (2008)
Google Inc.: Google docs (visited) (June 2009), at http://docs.google.com
Wikipedia: List of file systems, distributed file systems (visited) (June 2009), at http://en.wikipedia.org/wiki/List_of_file_systems
Herlihy, M.: Wait-Free Synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)
Herlihy, M.P., Wing, J.M.: Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)
Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P.: The Complexity of Obstruction-Free Implementations. J. ACM 56(4), 1–33 (2009)
Herlihy, M., Luchangco, V., Moir, M.: Obstruction-Free Synchronization: Double-Ended Queues as an Example. In: ICDCS, Washington, DC, USA, p. 522. IEEE Computer Society Press, Los Alamitos (2003)
Oprea, A., Reiter, M.K.: On consistency of encrypted files. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 254–268. Springer, Heidelberg (2006)
Cachin, C., Keidar, I., Shraer, A.: Fork Sequential Consistency is Blocking. Inf. Process. Lett. 109(7), 360–364 (2009)
Aguilera, M.K., Frolund, S., Hadzilacos, V., Horn, S.L., Toueg, S.: Abortable and Query-Abortable Objects and Their Efficient Implementation. In: PODC: Principles of distributed computing, pp. 23–32. ACM, New York (2007)
Cachin, C., Keidar, I., Shraer, A.: Fail-Aware Untrusted Storage. In: DSN (2009)
Li, J., Mazières, D.: Beyond One-Third Faulty Replicas in Byzantine Fault Tolerant Systems. In: NSDI (2007)
Aguilera, M.K., Toueg, S.: Timeliness-Based Wait-Freedom: A Gracefully Degrading Progress Condition. In: PODC 2008: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, pp. 305–314. ACM, New York (2008)
Jayanti, P., Chandra, T.D., Toueg, S.: Fault-tolerant Wait-free Shared Objects. J. ACM 45(3), 451–500 (1998)
Pease, M., Shostak, R., Lamport, L.: Reaching Agreement in the Presence of Faults. J. ACM 27(2), 228–234 (1980)
Attiya, H., Guerraoui, R., Kouznetsov, P.: Computing with Reads and Writes in the Absence of Step Contention. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 122–136. Springer, Heidelberg (2005)
Dobre, D., Majuntke, M., Serafini, M., Suri, N.: Abortable Fork-Linearizable Storage. Technical Report TR-TUD-DEEDS-07-03-2009 (July 2009), http://www.deeds.informatik.tu-darmstadt.de/matze/afcs.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Majuntke, M., Dobre, D., Serafini, M., Suri, N. (2009). Abortable Fork-Linearizable Storage. In: Abdelzaher, T., Raynal, M., Santoro, N. (eds) Principles of Distributed Systems. OPODIS 2009. Lecture Notes in Computer Science, vol 5923. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10877-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-10877-8_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10876-1
Online ISBN: 978-3-642-10877-8
eBook Packages: Computer ScienceComputer Science (R0)