Expected Robustness in Dining Philosophers Algorithms

Abstract

The problem of distributed resource allocation and synchronization consists of a set of processes sharing a set of resources. The processes request access to needed resources which are allocated in accordance to two properties: a single resource can not be simultaneously used by multiple processes (mutual exclusion), and every resource request is eventually satisfied (progress). This problem is formalized as the Dining Philosophers Problem, in which processes and resources are represented in a graph. Nodes correspond to processes and edges between nodes correspond to resources shared by the processes. Many algorithms exist for solving the Dining Philosophers Problem. These algorithms differ with respect to a variety of performance metrics including the speed with which a process acquires all its needed resources and the efficiency of communication between processes. We are investigating a new performance metric: the degree to which a process failure impacts other processes in the system. When a process fails, any resources that it holds become irrecoverable, and hence future requests for these resources will not be satisfied. Processes whose requests are never satisfied are characterized as 'starving'. This effect could cascade throughout the system, causing more processes to starve. The new performance metric, failure locality, is the distance in the graph from the failed node to the farthest starving node. In the worst case, all processes within that distance will starve. We have developed a new variant on this metric, integrated failure locality, which better represents the number of processes effected compared to the total number of processes, and the distance of the starved processes to the failed process. Integrated failure locality is defined to be the sum of the ratios of starving processes to the total number of processes within successive distances to the failed process (i.e. the ratio of processes of distance 1 from the failed process plus the ratio of processes of distance 2, etc.). We have evaluated and compared several Dining Philosophers algorithms, including the hygienic algorithm (Chandy & Misra, 1988), the double-doorway algorithm (Choy & Singh, 1995), the bounded doorway algorithm (Choy & Singh, 1996) the dynamic thresholds algorithm (Sivilotti, Pike, & Sridhar, 2000), and the biserial algorithm (a new variation on the dynamic thresholds algorithm), with respect to expected integrated failure locality. First, we evaluated the various algorithms analytically to help develop our intuitions, to help form hypotheses with regards to their expected behaviors under different situations, and to help guide the design of our experiments. We then implemented simulations of these algorithms using the AnyLogic 5.0 simulation toolkit, and ran experiments, varying parameters such as contention on resources and graph topology. Specifically, we compared the behavior of algorithms on similar sets of parameters, as well as examined which factors had the most impact on the expected integrated failure locality of the system. In the thesis, I will discuss the motivation for the integrated failure locality metric, describe the algorithms we have examined, describe the experiments and methods to derive integrated failure locality for the algorithms, and present data and analysis of the behaviors of these algorithms with respect to the robustness that integrated failure locality measures.