Efficient fork-linearizable access to untrusted shared memory

ABSTRACT

When data is stored on a faulty server that is accessed concurrently by multiple clients, the server may present inconsistent data to different clients. For example, the server might complete a write operation of one client, but respond with stale data to another client. Mazières and Shasha (PODC 2002) introduced the notion of fork-consistency, also called fork-linearizability, which ensures that the operations seen by every client are linearizable and guarantees that if the server causes the views of two clients to differ in a single operation, they may never again see each other's updates after that without the server being exposed as faulty. In this paper, we improve the communication complexity of their fork-linearizable storage access protocol with n clients from Ω(n²) to O(n). We also prove that in every such protocol, a reader must wait for a concurrent writer. This explains a seeming limitation of their and of our improved protocol. Furthermore, we give novel characterizations of fork-linearizability and prove that it is neither stronger nor weaker than sequential consistency.

REFERENCES

• 1: I. Abraham, G. Chockler, I. Keidar, and D. Malkhi. Byzantine disk Paxos: Optimal resilience with Byzantine shared memory. Distributed Computing, 18(5):387--408, 2006.
• 2: Hagit Attiya , Jennifer Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, 2004
• 3: M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories. Algorithmica, 12:225--244, 1994.
• 4: C. Cachin, A. Shelat, and A. Shraer. Efficient fork-linearizable access to untrusted shared memory. TR RZ3688, IBM Research, Apr. 2007.
• 5: D. Clarke, S. Devadas, M. van Dijk, B. Gassend, and G. E. Suh. Incremental multiset hash functions and their application to memory integrity checking. In ASIACRYPT 2003.
• 6: Dwaine Clarke , G. Edward Suh , Blaise Gassend , Ajay Sudan , Marten van Dijk , Srinivas Devadas, Towards Constant Bandwidth Overhead Integrity Checking of Untrusted Data, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.139-153, May 08-11, 2005
• 7: Kevin Fu , M. Frans Kaashoek , David Mazières, Fast and secure distributed read-only file system, ACM Transactions on Computer Systems (TOCS), v.20 n.1, p.1-24, February 2002 [doi>10.1145/505452.505453]
• 8: K. E. Fu. Group sharing and random access in cryptographic storage file systems. Master Thesis, MIT LCS, 1998.
• 9: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 10: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 11: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 12: Prasad Jayanti , Tushar Deepak Chandra , Sam Toueg, Fault-tolerant wait-free shared objects, Journal of the ACM (JACM), v.45 n.3, p.451-500, May 1998 [doi>10.1145/278298.278305]
• 13: L. Lamport. On interprocess communication. Distributed Computing, 1(2):77--85, 86--101, 1986.
• 14: Jinyuan Li , Maxwell Krohn , David Mazières , Dennis Shasha, Secure untrusted data repository (SUNDR), Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.9-9, December 06-08, 2004, San Francisco, CA
• 15: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 16: N. A. Lynch and M. R. Tuttle. An introduction to input/output automata. CWI Quaterly, 2(3):219--246, Sept. 1989.
• 17: Jean-Philippe Martin , Lorenzo Alvisi , Michael Dahlin, Minimal Byzantine Storage, Proceedings of the 16th International Conference on Distributed Computing, p.311-325, October 28-30, 2002
• 18: David Mazières , Dennis Shasha, Building secure file systems out of byzantine storage, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571840]
• 19: A. Oprea and M. K. Reiter. On consistency of encrypted files. In DISC, pages 254--268, 2006.
• 20: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Performance, Reliability, Theory

Keywords:
arbitrary failures, fork-consistency, storage emulations