Active disk paxos with infinitely many processes

ABSTRACT

We present an improvement to the Disk Paxos protocol by Gafni and Lamport which utilizes extended functionality and flexibility provided by Active Disks and supports unmediated concurrent data access by an unlimited number of processes. The solution facilitates coordination by an infinite number of clients using finite shared memory. It is based on a collection of read-modify-write objects with faults, that emulate a new, reliable shared memory abstraction called a ranked register. The required read-modify-write objects are readily available in Active Disks and in Object Storage Device controllers, making our solution suitable for state-of-the-art Storage Area Network (SAN) environments.

REFERENCES

• 1: Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared objects, Journal of the ACM (JACM), v.42 n.6, p.1231-1274, Nov. 1995 [doi>10.1145/227683.227688]
• 2: Anurag Acharya , Mustafa Uysal , Joel Saltz, Active disks: programming model, algorithms and evaluation, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.81-91, October 02-07, 1998, San Jose, California, United States
• 3: Khalil Amiri , Garth A. Gibson , Richard Golding, Highly Concurrent Shared Storage, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.298, April 10-13, 2000
• 4: Thomas E. Anderson , Michael D. Dahlin , Jeanna M. Neefe , David A. Patterson , Drew S. Roselli , Randolph Y. Wang, Serverless network file systems, ACM Transactions on Computer Systems (TOCS), v.14 n.1, p.41-79, Feb. 1996 [doi>10.1145/225535.225537]
• 5: K. Birman , T. Joseph, Exploiting virtual synchrony in distributed systems, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.123-138, November 08-11, 1987, Austin, Texas, United States
• 6: R. Boichat, P. Dutta, S. Frolund and R. Guerraoui. Deconstructing Paxos. Technical Report DSC ID:200106, Communication Systems Department (DSC), École Polytechnic Fédérale de Lausanne (EPFL), January 2001. Available at http://dscwww.epfl.ch/EN/publications/documents/tr01_006.pdf.
• 7: Randal Chilton Burns , Darrell D. Long, Data management in a distributed file system for storage area networks, 2000
• 8: James E. Burns , Nancy A. Lynch, Bounds on shared memory for mutual exclusion, Information and Computation, v.107 n.2, p.171-184, Dec. 1993 [doi>10.1006/inco.1993.1065]
• 9: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
• 10: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 11: Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001 [doi>10.1145/503112.503113]
• 12: Backoff Protocols for Distributed Mutual Exclusion and Ordering, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.11, April 16-19, 2001
• 13: B. Chor and C. Dwork. Randomization in Byzantine agreement. Advances in Computing Research, Randomness in Computation, volume 5, JAI Press, edited by S. Micali, pp. 443-497, 1989.
• 14: F. Cristian , C. Fetzer, The Timed Asynchronous Distributed System Model, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.140, June 23-25, 1998
• 15: Roberto De Prisco , Butler Lampson , Nancy Lynch, Revisiting the PAXOS algorithm, Theoretical Computer Science, v.243 n.1-2, p.35-91, July 28, 2000 [doi>10.1016/S0304-3975(00)00042-6]
• 16: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• 17: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 18: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 19: Specifying and using a partitionable group communication service, ACM Transactions on Computer Systems (TOCS), v.19 n.2, p.171-216, May 2001 [doi>10.1145/377769.377776]
• 20: Eli Gafni , Leslie Lamport, Disk Paxos, Proceedings of the 14th International Conference on Distributed Computing, p.330-344, October 04-06, 2000
• 21: Eli Gafni , Michael Merritt , Gadi Taubenfeld, The concurrency hierarchy, and algorithms for unbounded concurrency, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.161-169, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384008]
• 22: Garth A. Gibson , David F. Nagle , Khalil Amiri , Jeff Butler , Fay W. Chang , Howard Gobioff , Charles Hardin , Erik Riedel , David Rochberg , Jim Zelenka, A cost-effective, high-bandwidth storage architecture, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.92-103, October 02-07, 1998, San Jose, California, United States
• 23: G. A. Gibson, D. F. Nagle, K. Amiri, F. W. Chang, H. Gobioff, E. Riedel, D. Rochberg and J. Zelenka. Filesystems for Network-Attached Secure Disks. Technical Report CMU-CS-97-118, July 1997.
• 24: H. Gobioff, G. A. Gibson, D. Tygar. Security for Network Attached Storage Devices. Technical Report CMU-CS-97-185, October 1997.
• 25: S. Hotz, R. Van Meter and G. Finn. Internet protocols for network-attached peripherals. In Proceedings of the Sixth NASA Goddard Conference on Mass Storage Systems and Technologies in conjunction with 15th IEEE Symposium on Mass Storage Systems, 1998.
• 26: The Swarm Scalable Storage System, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.74, May 31-June 04, 1999
• 27: 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]
• 28: 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]
• 29: I. Keidar and D. Dolev. Totally ordered broadcast in the face of network partitions: exploiting group communication for replication in partitionable networks. In Dependable Network Computing, Chapter 3, D. Avresky Editor, Kluwer Academic Publications. January 2000.
• 30: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 31: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 32: L. Lamport. Paxos made simple. Distributed Computing Column of SIGACT News 32(4):34-58, December 2001.
• 33: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 34: Butler W. Lampson, How to Build a Highly Available System Using Consensus, Proceedings of the 10th International Workshop on Distributed Algorithms, p.1-17, October 09-11, 1996
• 35: Edward K. Lee , Chandramohan A. Thekkath, Petal: distributed virtual disks, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.84-92, October 01-04, 1996, Cambridge, Massachusetts, United States
• 36: M. C. Loui and H. H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes, In Franco P. Preparata, editor, Parallel and Distributed Computing, volume 4 of Advances in Computing Research, pages 163-183. JAI Press, Greenwich, Conn., 1987.
• 37: Dahlia Malkhi , Michael K. Reiter, An Architecture for Survivable Coordination in Large Distributed Systems, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.187-202, March 2000 [doi>10.1109/69.842262]
• 38: Michael Merritt , Gadi Taubenfeld, Computing with Infinitely Many Processes, Proceedings of the 14th International Conference on Distributed Computing, p.164-178, October 04-06, 2000
• 39: A. Mostfaoui and M. Raynal. Leader-based consensus. Parallel Processing Letters 11(1):95-107 2001.
• 40: National Storage Industry Consortium. http://www.nsic.org/nasd.
• 41: David Powell, Group communication, Communications of the ACM, v.39 n.4, p.50-53, April 1996 [doi>10.1145/227210.227225]
• 42: Erik Riedel , Christos Faloutsos , Garth A. Gibson , David Nagle, Active Disks for Large-Scale Data Processing, Computer, v.34 n.6, p.68-74, June 2001 [doi>10.1109/2.928624]
• 43: Dale Skeen, Nonblocking commit protocols, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582339]
• 44: M. D. Skeen. Crash Recovery in a Distributed Database System. PhD thesis, UC Berkeley, May 1982.
• 45: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 46: Chandramohan A. Thekkath , Timothy Mann , Edward K. Lee, Frangipani: a scalable distributed file system, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.224-237, October 05-08, 1997, Saint Malo, France