On Deadlocks and Fairness in Self-organizing Resource-Flow Systems

Jan-Philipp Steghöfer, Pratik Mandrekar, Florian Nafz, Hella Seebach, Wolfgang Reif

Systems in which individual units concurrently process indivisible resources are inherently prone to starvation and deadlocks. This paper describes a fair scheduling mechanism for self-organizing resource-flow systems that prevents starvation as well as a distributed deadlock avoidance algorithm. The algorithm leverages implicit local knowledge about the system's structure and uses a simple coordination mechanism to detect loops in the resource-flow. The knowledge about the loops that have been detected is then incorporated into the scheduling mechanism. Limitations of the approach are presented along with extension to the basic mechanism to deal with them.
Proceedings of ARCS 2010 - Architecture of Computing Systems

Publisher: Springer