Document Open Access Logo

Fast Detection of Stable and Count Predicates in Parallel Computations

Authors Himanshu Chauhan, Vijay K. Garg

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.20.pdf
  • Filesize: 0.59 MB
  • 21 pages

Document Identifiers

Author Details

Himanshu Chauhan
Vijay K. Garg

Cite As Get BibTex

Himanshu Chauhan and Vijay K. Garg. Fast Detection of Stable and Count Predicates in Parallel Computations. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.OPODIS.2017.20

Abstract

Enumerating all consistent states of a parallel computation that satisfy a given predicate is an important problem in debugging and verification of parallel programs. We give a fast algorithm to enumerate all consistent states of a parallel computation that satisfy a stable predicate. In addi- tion, we define a new category of global predicates called count predicates and give an algorithm to enumerate all consistent states (of the computation) that satisfy it. All existing predicate detection algorithms, such as BFS, DFS and Lex algorithms, do not exploit the knowledge about the nature of the predicates, and thus may visit all global states of the computation in the worst case. In comparison, our algorithms only visit the states that satisfy the given predicate, and thus take time and space that is a polynomial function of the number of states of interest. In doing so, they provide a significant reduction — exponential in many cases — in time complexities in comparison to existing algorithms.

Subject Classification

Keywords
  • Algorithms
  • Theory
  • Predicate Detection
  • Parallel Programs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Alagar and S. Venkatesan. Techniques to Tackle State Explosion in Global Predicate Detection. IEEE Transactions on Software Engineering (TSE), 27(8):704-714, AUG 2001. Google Scholar
  2. Lucio Bianco, Paolo Dell ‘Olmo, and Stefano Giordani. An optimal algorithm to find the jump number of partially ordered sets. Computational Optimization and Applications, 8(2):197-210, 1997. Google Scholar
  3. K. M. Chandy and L. Lamport. Distributed Snapshots: Determining Global States of Distributed Systems. ACM Transactions on Computer Systems, 3(1):63-75, FEB 1985. Google Scholar
  4. Yen-Jung Chang and Vijay K. Garg. A parallel algorithm for global states enumeration in concurrent systems. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015, pages 140-149. ACM, 2015. Google Scholar
  5. Yen-Jung Chang and Vijay K. Garg. Quicklex: A fast algorithm for consistent global states enumeration of distributed computations. In 19th International Conference on Principles of Distributed Systems, OPODIS 2015, December 14-17, 2015, Rennes, France, pages 25:1-25:17, 2015. Google Scholar
  6. Himanshu Chauhan and Vijay K. Garg. Fast detection of stable and counting predicates in parallel computations. Extended Version, 2017. URL: http://users.ece.utexas.edu/~garg/dist/opodis17.pdf.
  7. Himanshu Chauhan and Vijay K. Garg. Space efficient breadth-first and level traversals of consistent global states of parallel programs. In 17th International Conference on Runtime Verification (RV 2017), pages 138-154, 2017. Google Scholar
  8. Himanshu Chauhan, Vijay K Garg, Aravind Natarajan, and Neeraj Mittal. A distributed abstraction algorithm for online predicate detection. In Reliable Distributed Systems (SRDS), 2013 IEEE 32nd International Symposium on, pages 101-110. IEEE, 2013. Google Scholar
  9. M Chein and M Habib. The jump number of dags and posets: an introduction. Annals of Discrete Mathematics, 9:189-194, 1980. Google Scholar
  10. Feng Chen, Traian Florin Serbanuta, and Grigore Roşu. jPredictor: a predictive runtime analysis tool for java. In Proceedings of the International Conference on Software Engineering, pages 221-230, 2008. Google Scholar
  11. R. Cooper and K. Marzullo. Consistent detection of global predicates. In Proc. of the Workshop on Parallel and Distributed Debugging, pages 163-173, 1991. Google Scholar
  12. B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, Cambridge, UK, 1990. Google Scholar
  13. C. J. Fidge. Timestamps in Message-Passing Systems that Preserve the Partial-Ordering. In K. Raymond, editor, Proceedings of the 11th Australian Computer Science Conference (ACSC), pages 56-66, FEB 1988. Google Scholar
  14. Cormac Flanagan and Stephen N. Freund. FastTrack: efficient and precise dynamic race detection. In Proceedings of the Conference on Programming Language Design and Implementation, pages 121-133, 2009. Google Scholar
  15. David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  16. Bernhard Ganter. Two basic algorithms in concept analysis. In Proceedings of the International Conference on Formal Concept Analysis, pages 312-340, 2010. Google Scholar
  17. Vijay K. Garg. Enumerating global states of a distributed computation. In Proceedings of the International Conference on Parallel and Distributed Computing Systems, pages 134-139, 2003. Google Scholar
  18. Vijay K. Garg and B. Waldecker. Detection of weak unstable predicates in distributed programs. IEEE Transactions on Parallel and Distributed Systems, 5(3):299-307, 1994. Google Scholar
  19. Dan Gusfield and Robert W Irving. The stable marriage problem: structure and algorithms. MIT press, 1989. Google Scholar
  20. Michel Habib, Raoul Medina, Lhouari Nourine, and George Steiner. Efficient algorithms on distributive lattices. Discrete Appl. Math., 110(2-3):169-187, 2001. Google Scholar
  21. Jeff Huang and Charles Zhang. Persuasive prediction of concurrency access anomalies. In Proceedings of the International Symposium on Software Testing and Analysis, pages 144-154, 2011. Google Scholar
  22. Roland Jegou, Raoul Medina, and Lhouari Nourine. Linear space algorithm for on-line detection of global predicates. In Proc. of the International Workshop on Structures in Concurrency Theory, pages 175-189, 1995. Google Scholar
  23. L. Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM (CACM), 21(7):558-565, JUL 1978. Google Scholar
  24. Leslie Lamport. Paxos made simple. ACM Sigact News, 32(4):18-25, 2001. Google Scholar
  25. Shan Lu, Joseph Tucek, Feng Qin, and Yuanyuan Zhou. AVIO: detecting atomicity violations via access interleaving invariants. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, pages 37-48, 2006. Google Scholar
  26. F. Mattern. Virtual Time and Global States of Distributed Systems. In Parallel and Distributed Algorithms: Proceedings of the Workshop on Distributed Algorithms (WDAG), pages 215-226, 1989. Google Scholar
  27. N. Mittal and V. K. Garg. Techniques and Applications of Computation Slicing. Distributed Computing (DC), 17(3):251-277, MAR 2005. Google Scholar
  28. N. Mittal, A. Sen, and V. K. Garg. Solving Computation Slicing using Predicate Detection. IEEE Transactions on Parallel and Distributed Systems (TPDS), 18(12):1700-1713, DEC 2007. Google Scholar
  29. Gara Pruesse and Frank Ruskey. Gray codes from antimatroids. Order 10, pages 239-252, 1993. Google Scholar
  30. Matthew B. Squire. Enumerating the ideals of a poset. In PhD Dissertation, Department of Computer Science, North Carolina State University, 1995. Google Scholar
  31. George Steiner. An algorithm to generate the ideals of a partial order. Oper. Res. Lett., 5(6):317-320, 1986. Google Scholar
  32. Maciej M Sysło. Minimizing the jump number for partially ordered sets: A graph-theoretic approach. Order, 1(1):7-19, 1984. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact