Article

The generalized deadlock resolution problem

Authors:

MohammadTaghi Hajiaghayi,

Kunal TalwarAuthors Info & Claims

ICALP'05: Proceedings of the 32nd international conference on Automata, Languages and Programming

Pages 853 - 865

https://doi.org/10.1007/11523468_69

Published: 11 July 2005 Publication History

Abstract

In this paper we initiate the study of the AND-OR directed feedback vertex set problem from the viewpoint of approximation algorithms. This AND-OR feedback vertex set problem is motivated by a practical deadlock resolution problem that appears in the development of distributed database systems. 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 Ω(log²n) 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.

References

[1]

B. AWERBUCH AND S. MICALI, Dynamic deadlock resolution protocols, in The 27th Annual Symposium on Foundations of Computer Science, 1986, 196-207.

Digital Library

[2]

R. BAR-YEHUDA, D. GEIGER, J. NAOR, AND R. M. ROTH, Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference, SIAM J. Comput., 27 (1998), 942-959.

Digital Library

[3]

G. BRACHA AND S. TOUEG, A distributed algorithm for generalized deadlock detection, in Proceedings of the 3rd annual ACM symposium on Principles of distributed computing, ACM Press, 1984, 285-301.

Digital Library

[4]

K. M. CHANDY AND L. LAMPORT, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), 3 (1985), 63-75.

Digital Library

[5]

K. M. CHANDY AND J. MISRA, A distributed algorithm for detecting resource deadlocks in distributed systems, in Proceedings of the 1st ACM SIGACT-SIGOPS symposium on Principles of distributed computing, ACM Press, 1982, 157-164.

Digital Library

[6]

K. M. CHANDY, J. MISRA, AND L. M. HAAS, Distributed deadlock detection, ACMTransactions on Computer Systems (TOCS), 1 (1983), 144-156.

Digital Library

[7]

M. CHARIKAR, C. CHEKURI, T.-Y. CHEUNG, Z. DAI, A. GOEL, S. GUHA, AND M. LI, Approximation algorithms for directed Steiner problems, J. Algorithms, 33 (1999), 73-91.

Digital Library

[8]

J. CHERIYAN, H. J. KARLOFF, AND Y. RABANI, Approximating directed multicuts, in The 42th Annual Symposium on Foundations of Computer Science, 2001, 348-356.

Digital Library

[9]

G. EVEN, J. NAOR, B. SCHIEBER, AND M. SUDAN, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20 (1998), 151-174.

[10]

U. FEIGE, A threshold of ln n for approximating set cover, J. ACM, 45 (1998), 634-652.

Digital Library

[11]

M. FLATEBO AND A. K. DATTA, Self-stabilizing deadlock detection algorithms, in Proceedings of the '92 ACM annual conference on Communications, ACM Press, 1992, 117-122.

Digital Library

[12]

J. GRAY, P. HOMAN, R. OBERMARCK, AND H. KORTH, A straw man analysis of probability of waiting and deadlock, in Proceedings of the 5th Internafional Conference on Distributed Data Management and Computer Networks, 1981.

[13]

E. HALPERIN AND R. KRAUTHGAMER, Polylogarithmic inapproximability, in The 35th Annual ACM Symposium on Theory of Computing (STOC'03), 2003, 585-594.

Digital Library

[14]

J.-M. HELARY, C. JARD, N. PLOUZEAU, AND M. RAYNAL, Detection of stable properties in distributed applications, in Proceedings of the 6th PODC, ACM Press, 1987, 125-136.

Digital Library

[15]

T. HERMAN AND K. M. CHANDY, A distributed procedure to detect and/or deadlock, Tech. Rep. TR LCS-8301, Dept. of Computer Sciences, Univ. of Texas, 1983.

[16]

K. JAIN, M. MAHDIAN, AND M. R. SALAVATIPOUR, Packing Steiner trees, in The 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), 2003, 266-274.

Digital Library

[17]

E. KNAPP, Deadlock detection in distributed databases, ACM Computing Surveys (CSUR), 19 (1987), 303-328.

Digital Library

[18]

T. LEIGHTON AND S. RAO, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM, 46 (1999), 787-832.

Digital Library

[19]

R. J. LIPTON AND R. E. TARJAN, Applications of a planar separator theorem, SIAM J. Comput., 9 (1980), 615-627.

[20]

C. LUND AND M. YANNAKAKIS, On the hardness of approximating minimization problems, J. Assoc. Comput. Mach., 41 (1994), 960-981.

Digital Library

[21]

K. MAKKI AND N. PISSINOU, Detection and resolution of deadlocks in distributed database systems, in Proceedings of the 4th international conference on Information and knowledge management, ACM Press, 1995, 411-416.

Digital Library

[22]

P. D. SEYMOUR, Packing directed circuits fractionally, Combinatorica, 15 (1995), 281-288.

[23]

H. WU, W.-N. CHIN, AND J. JAFFAR, An efficient distributed deadlock avoidance algorithm for the and model, IEEE Transactions on Software Engineering, 28 (2002), 18-29.

Digital Library

Cited By

Cogumbreiro THu RMartins FYoshida N(2018)Dynamic Deadlock Verification for General Barrier SynchronisationACM Transactions on Programming Languages and Systems10.1145/322906041:1(1-38)Online publication date: 11-Dec-2018
https://dl.acm.org/doi/10.1145/3229060
Bonsma PLokshtanov D(2011)Feedback vertex set in mixed graphsProceedings of the 12th international conference on Algorithms and data structures10.5555/2033190.2033201(122-133)Online publication date: 15-Aug-2011
https://dl.acm.org/doi/10.5555/2033190.2033201

Index Terms

The generalized deadlock resolution problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Faster algorithms for the generalized network flow problem
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science

We consider the generalized network flow problem. Each arc e in the network has a gain factor /spl gamma/(e). If f(e) units of flow enter arc e, then f(e)/spl gamma/(e) units arrive at the other end of e. The generalized network flow problem is to ...
Generalised k-Steiner Tree Problems in Normed Planes

The 1-Steiner tree problem, the problem of constructing a Steiner minimum tree containing at most one Steiner point, has been solved in the Euclidean plane by Georgakopoulos and Papadimitriou using plane subdivisions called oriented Dirichlet cell ...
An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs
APPROX'11/RANDOM'11: Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques

A spanning tree T of a graph G is called a tree t-spanner of G if the distance between every pair of vertices in T is at most t times their distance in G. In this paper, we present an algorithm which constructs for an n-vertex m-edge unweighted graph G: ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICALP'05: Proceedings of the 32nd international conference on Automata, Languages and Programming

July 2005

1476 pages

ISBN:3540275800

Editors:
Luís Caires
CITI / Departamento de Informática, Universidade Nova de Lisboa, Portugal
,
Giuseppe F. Italiano
Dipartimento di Informatica, Sistemi e Produzione, Università di Roma "Tor Vergata", via del Politecnico 1, Roma, Italy
,
Luís Monteiro
Departamento de Informatica, Universidade Nova de Lisboa, via del Politecnico 1, Caparica, Portugal
,
Catuscia Palamidessi
Departamento de Informatica, Ecole Polytechnique, Rue de Saclay, Palaiseau Cedex, France
,
Moti Yung
Computer Science Department, Google Inc. and Columbia University, 1214 Amsterdam Avenue, New York, France

Sponsors

Fundacao para a Ciencia e Tecnologia
FCT: Foundation for Science and Technology
Centro de Lógica e Computação/IST/UTL: Centro de Lógica e Computação/IST/UTL

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 11 July 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cogumbreiro THu RMartins FYoshida N(2018)Dynamic Deadlock Verification for General Barrier SynchronisationACM Transactions on Programming Languages and Systems10.1145/322906041:1(1-38)Online publication date: 11-Dec-2018
https://dl.acm.org/doi/10.1145/3229060
Bonsma PLokshtanov D(2011)Feedback vertex set in mixed graphsProceedings of the 12th international conference on Algorithms and data structures10.5555/2033190.2033201(122-133)Online publication date: 15-Aug-2011
https://dl.acm.org/doi/10.5555/2033190.2033201

View Options

View options

Media

Figures

Other

Tables

View Table of Contents