Abstract
This paper presents an algorithm for the dining philosophers problem with a failure locality of two, i.e. in the presence of undetectable fail-stop failures, the algorithm guarantees that a process is free from starvation if no processes that are within two hops away from the process fail. It can be shown that any non-probabilistic algorithm for the problem has a failure locality of at least two; hence, the failure locality of our algorithm is optimal. Our algorithm combines the idea of a dynamic priority scheme with the use of a preemptive fork collecting strategy. Its response time is O(n), where n is the total number of processes, if no failures actually occur or O(n 2) in the presence of failures. As an application, we show how the algorithm can be used to derive a scheduling algorithm for the synchronization of CSP-like processes that is strongly fair and has a failure locality of three.
This research was partially supported by NSF PYI Award number ASC 9157610 and by ONR under grant number N00014-91-J-1605. The work reported here is based on a chapter of the first author's Ph.D. dissertation.
Preview
Unable to display preview. Download preview PDF.
References
B. Awerbuch and M. Saks. A dining philosophers algorithm with polynomial response time. In Proceedings of the 31st IEEE Conference on Foundations of Computer Science, pages 65–74, 1990.
R.L. Bagrodia. Process synchronization: Design and performance evaluation of distributed algorithms. IEEE Transactions on Software Engineering, 15(9):1053–1065, September 1989.
R.L. Bagrodia. Synchronization of asynchronous processes in CSP. ACM TOPLAS, 11(4):585–597, October 1989.
G. Buckley and A. Silberschatz. An effective implementation of the generalized input-output construct of CSP. ACM TOPLAS, 5(2):223–235, April 1983.
K.M. Chandy and J. Misra. The drinking philosophers problem. ACM TOPLAS, 6(4):632–646, October 1984.
K.M. Chandy and J. Misra. Parallel Program Design: A Foundation. Addison-Wesley, 1988.
M. Choy and A.K. Singh. Efficient fault tolerant algorithms for resource allocation in distributed systems. In Proceedings of the 24th ACM Symposium on Theory of Computing, 1992.
M. Choy and A.K. Singh. Tight lower bounds on failure locality of distributed synchronization. In Proceedings of the 30th Annual Allerton Conference on Communication, Control, and Computing, pages 127–136, 1992.
M. Choy and A.K. Singh. Private communication, 1994.
E.W. Dijkstra. Two starvation free solutions of a general exclusion problem, 1978. EWD 625, Plataanstraat 5, 5671 AL Nuenen, Netherlands.
D. Dolev, C. Dwork, and L. Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77–97, January 1987.
M.J. Fischer, N. Lynch, and M. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.
D. Lehmann and M.O. Rabin. On the advantage of free choice: A symmetric and fully distributed solution to the dining philosophers problem. In Proceedings of the 8th ACM Symposium on Principles of Programming Languages, 1981.
N.A. Lynch. Fast allocation of nearby resources in a distributed system. In Proceedings of the 12th ACM Symposium on Theory of Computing, 1980.
M. Naor and L. Stockmeyer. What can be computed locally. In Proceedings of the 25th ACM Symposium on Theory of Computing, 1993.
S. Ramesh. A new implementation of CSP with output guards. In Proceedings of the 7th International Conference on Distributed Computing Systems, pages 266–273, 1987.
F.B. Schneider. Synchronization in distributed programs. ACM TOPLAS, 4(2):125–148, April 1982.
A.P. Sistla. Distributed algorithms for ensuring fair interprocess communication. In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing, pages 266–277, 1984.
E. Styer and G.L. Peterson. Improved algorithms for distributed resource allocation. In Proceedings of the 7th ACM Symposium on Principles of Distributed Computing, pages 105–116, 1988.
Y.-K. Tsay. Distributed Coordination of Process Interactions — Fairness and Fault-Tolerance. PhD thesis, UCLA, September 1993. Also available as technical report CSD-930034.
Y.-K. Tsay and R.L. Bagrodia. Fault-tolerant algorithms for fair interprocess synchronization. IEEE Transactions on Parallel and Distributed Systems, 5(6), June 1994.
Author information
Authors and Affiliations
Corresponding author
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tsay, YK., Bagrodia, R.L. (1994). An algorithm with optimal failure locality for the dining philosophers problem. In: Tel, G., Vitányi, P. (eds) Distributed Algorithms. WDAG 1994. Lecture Notes in Computer Science, vol 857. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0020441
Download citation
DOI: https://doi.org/10.1007/BFb0020441
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58449-0
Online ISBN: 978-3-540-48799-9
eBook Packages: Springer Book Archive