Dining philosophers that tolerate malicious crashes
Tóm tắt
We present a solution to the problem of dining philosophers. Our solution tolerates malicious crashes. In a malicious crash the failed process behaves arbitrarily for a finite time and then ceases all operation undetectably to other processes. The tolerance of our solution is achieved by the combination of stabilization and crash failure locality. Stabilization allows our program to recover from an arbitrary state. Crash failure locality ensures that only a limited number of processes are affected by a process crash. The crash failure locality of our solution is optimal. Finally, we argue that the malicious crash fault model and its extensions are worthy of further study as they admit tolerances that are not achieved under stronger fault models and are unnecessary under weaker fault models.
Từ khóa
#Computer crashes #Distributed computingTài liệu tham khảo
10.1145/3149.214121
gouda, 0, The alternator. to appear, J Parallel and Distributed Computing
huang, 2000, The fuzzy philosophers, Proceedings of 15th IPDPS Workshop 2000, 130
10.1016/B978-0-444-88074-1.50023-8
10.1016/S0020-0190(98)00069-6
nesterenko, 1999, Stabilization-preserving atomicity refinement, Distributed Computing 13th International Symposium, 254
10.1145/322186.322188
sivilotti, 2000, A new distributed resource-allocation algorithm with optimal failure locality, Proceedings of the 12th IASTED Internation Conference on Parallel and Distributed Computing and Systems, 2, 524
tsay, 1994, An algorithm with optimal failure locality for the dining philosophers problem, Proceedings of WDAG '94 8th International Workshop on distributed Algorithms, 296, 10.1007/BFb0020441
10.1145/259380.259515
10.1080/00207729708929476
10.1145/203095.203101
10.1145/1780.1804
dijkstra, 1972, Hierarchical Ordering of Sequential Processes, 72
10.1109/71.508250
beauquier, 2000, Self-stabilizing local mutual exclusion and daemon refinement, DISC00 Distributed Computing 14th International Symposium Springer-Verlag LNCS 1914, 223
antonoiu, 1999, Mutual exclusion between neighboring nodes in an arbitrary system graph that stabilizes using read/write atomicity, Proceedings of EuvPar'99, 823
10.1145/361179.361202