C. Palamidessi and M. Pilquist (USA)
Process Management, Distributed Systems, Randomized Algorithms
We consider the problem of distributed resource allocation on arbitrary topologies. We focus on symmetric, fully distributed systems, and we address the problem of guaranteeing progress (deadlock-freedom), even in the presence of adversary schedulers, by using randomized algorithms. We show that in the case of the so-called generalized dining philosophers, where each process needs two resources to achieve its task (although a resource can be shared by more than two processes, hence the term generalized), there is a simple solution based on tokens. This solution, how ever, does not work in the completely general case, where each process may need an arbitrary number of resources, and each resource can be shared by an arbitrary number of processes. We thus propose a different algorithm, based on the idea of letting the philosophers assign a random priority to their adjacent forks. Using the progress statements of Lynch and Segala ([7, 10]), we show that this algorithm is deadlock-free. Finally we consider the mobile case, where a process may “move around” and try to acquire different sets of resources over time. Also in this case we show that our algorithm is deadlock-free.
Important Links:
Go Back
