The Generalized Deadlock Resolution Problem

In this paper we initiate the study of the AND-OR directed feedback vertex set problem from the viewpoint of approximation algorithms. This ANDOR feedback vertex set problem is motivated by a practical deadlock resolution problem that appears in the development of distributed database systems1. This problem also turns out be a natural generalization of the directed feedback vertex set problem. Awerbuch and Micali [1] gave a polynomial time algorithm to find a minimal solution for this problem. Unfortunately, a minimal solution can be arbitrarily more expensive than the minimum cost solution. We show that finding the minimum cost solution is as hard as the directed Steiner tree problem (and thus Ω(log2n) hard to approximate). On the positive side, we give algorithms which work well when the number of writers (AND nodes) or the number of readers (OR nodes) are small.

We also consider a variant that we call permanent deadlock resolution where we cannot specify an execution order for the surviving processes; they should get completed even if they were scheduled adversarially. When all processes are writers (AND nodes), we give an O(log n log log n) approximation for this problem.

Finally we give an LP-rounding approach and discuss some other natural variants.