More Web Proxy on the site http://driver.im/

Article

Computation Slicing: Techniques and Theory

Authors:

Vijay K. GargAuthors Info & Claims

DISC '01: Proceedings of the 15th International Conference on Distributed Computing

Pages 78 - 92

Published: 03 October 2001 Publication History

Abstract

We generalize the notion of slice introduced in our earlier paper [6]. A slice of a distributed computation with respect to a global predicate is the smallest computation that contains all consistent cuts of the original computation that satisfy the predicate. We prove that slice exists for all global predicates. We also establish that it is, in general, NP-complete to compute the slice. An optimal algorithm to compute slices for special cases of predicates is provided. Further, we present an efficient algorithm to graft two slices, that is, given two slices, either compute the smallest slice that contains all consistent cuts that are common to both slices or compute the smallest slice that contains all consistent cuts that belong to at least one of the slices. We give application of slicing in general and grafting in particular to global property evaluation of distributed programs. Finally, we show that the results pertaining to consistent global checkpoints [14,18] can be derived as special cases of computation slicing.

References

[1]

K. M. Chandy and L. Lamport. Distributed Snapshots: Determining Global States of Distributed Systems. ACM Transactions on Computer Systems , 3(1):63-75, February 1985.

[2]

C. Chase and V. K. Garg. Detection of Global Predicates: Techniques and their Limitations. Distributed Computing , 11(4):191-201, 1998.

[3]

R. Cooper and K. Marzullo. Consistent Detection of Global Predicates. In Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging , pages 163-173, Santa Cruz, California, 1991.

[4]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms . The MIT Press, Cambridge, Massachusetts, 1990.

[5]

B. A. Davey and H. A. Priestley. Introduction to Lattices and Order . Cambridge University Press, Cambridge, UK, 1990.

[6]

V. K. Garg and N. Mittal. On Slicing a Distributed Computation. In Proceedings of the 21st IEEE International Conference on Distributed Computing Systems (ICDCS) , pages 322-329, Phoenix, Arizona, April 2001.

[7]

V. K. Garg and B. Waldecker. Detection of Unstable Predicates. In Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging , Santa Cruz, California, May 1991.

[8]

B. Korel and R. Ferguson. Dynamic Slicing of Distributed Programs. Applied Mathematics and Computer Science Journal , 2(2):199-215, 1992.

[9]

B. Korel and J. Rilling. Application of Dynamic Slicing in Program Debugging. In Mariam Kamkar, editor, Proceedings of the 3rd International Workshop on Automated Debugging (AADEBUG) , pages 43-57, Linköping, Sweden, May 1997.

[10]

L. Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM (CACM) , 21(7):558-565, July 1978.

[11]

N. Mittal and V. K. Garg. Debugging Distributed Programs Using Controlled Reexecution. In Proceedings of the 19th ACM Symposium on Principles of Distributed Computing (PODC) , pages 239-248, Portland, Oregon, July 2000.

[12]

N. Mittal and V. K. Garg. Computation Slicing: Techniques and Theory . Technical Report TR-PDS-2001-002, The Parallel and Distributed Systems Laboratory, Department of Electrical and Computer Engineering, The University of Texas at Austin, April 2001. Available at http://www.cs.utexas.edu/users/neerajm.

[13]

N. Mittal and V. K. Garg. On Detecting Global Predicates in Distributed Computations. In Proceedings of the 21st IEEE International Conference on Distributed Computing Systems (ICDCS) , pages 3-10, Phoenix, Arizona, April 2001.

[14]

R. H. B. Netzer and J. Xu. Necessary and Sufficient Conditions for Consistent Global Snapshots. IEEE Transactions on Parallel and Distributed Systems , 6(2):165-169, February 1995.

[15]

S. D. Stoller and F. Schnieder. Faster Possibility Detection by Combining Two Approaches. In Proceedings of the Workshop on Distributed Algorithms (WDAG) , France, September 1995.

[16]

A. Tarafdar and V. K. Garg. Predicate Control for Active Debugging of Distributed Programs. In Proceedings of the 9th IEEE Symposium on Parallel and Distributed Processing (SPDP) , Orlando, 1998.

[17]

A. Tarafdar and V. K. Garg. Software Fault Tolerance of Concurrent Programs Using Controlled Re-execution. In Proceedings of the 13th Symposium on Distributed Computing (DISC) , pages 210-224, Bratislava, Slovak Republic, September 1999.

[18]

Yi-Min Wang. Consistent Global Checkpoints that Contain a Given Set of Local Checkpoints. IEEE Transactions on Computers , 46(4):456-468, April 1997.

[19]

M. Weiser. Programmers Use Slices when Debugging. Communications of the ACM (CACM) , 25(7):446-452, 1982.

Cited By

Garg VGarg RHansdah RKrishnaswamy DVaidya N(2019)Parallel algorithms for predicate detectionProceedings of the 20th International Conference on Distributed Computing and Networking10.1145/3288599.3288604(51-60)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1145/3288599.3288604
Sen A(2011)Concurrency-oriented verification and coverage of system-level designsACM Transactions on Design Automation of Electronic Systems10.1145/2003695.200369716:4(1-25)Online publication date: 27-Oct-2011
https://dl.acm.org/doi/10.1145/2003695.2003697
Agarwal AGarg VOgale V(2010)Modeling and analyzing periodic distributed computationsProceedings of the 12th international conference on Stabilization, safety, and security of distributed systems10.5555/1926829.1926848(191-205)Online publication date: 20-Sep-2010
https://dl.acm.org/doi/10.5555/1926829.1926848
Show More Cited By

Computation Slicing: Techniques and Theory
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis

Recommendations

Solving Computation Slicing Using Predicate Detection

Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies the predicate. On the other hand, computation slicing ...
Techniques and applications of computation slicing

Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems should be able to operate properly even in the presence of software faults. ...
On Slicing a Distributed Computation
ICDCS '01: Proceedings of the The 21st International Conference on Distributed Computing Systems

Abstract: We introduce the notion of a slice of a distributed computation. A slice of a distributed computation with respect to a global predicate is a computation which captures those and only those consistent cuts of the original computation which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

DISC '01: Proceedings of the 15th International Conference on Distributed Computing

October 2001

341 pages

ISBN:3540426051

Editor:
Jennifer L. Welch

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 03 October 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Garg VGarg RHansdah RKrishnaswamy DVaidya N(2019)Parallel algorithms for predicate detectionProceedings of the 20th International Conference on Distributed Computing and Networking10.1145/3288599.3288604(51-60)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1145/3288599.3288604
Sen A(2011)Concurrency-oriented verification and coverage of system-level designsACM Transactions on Design Automation of Electronic Systems10.1145/2003695.200369716:4(1-25)Online publication date: 27-Oct-2011
https://dl.acm.org/doi/10.1145/2003695.2003697
Agarwal AGarg VOgale V(2010)Modeling and analyzing periodic distributed computationsProceedings of the 12th international conference on Stabilization, safety, and security of distributed systems10.5555/1926829.1926848(191-205)Online publication date: 20-Sep-2010
https://dl.acm.org/doi/10.5555/1926829.1926848
Sen AGarg V(2007)Formal Verification of Simulation Traces Using Computation SlicingIEEE Transactions on Computers10.1109/TC.2007.101156:4(511-527)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1109/TC.2007.1011
Garg V(2006)Algorithmic combinatorics based on slicing posetsTheoretical Computer Science10.1016/j.tcs.2006.03.005359:1(200-213)Online publication date: 14-Aug-2006
https://dl.acm.org/doi/10.1016/j.tcs.2006.03.005
Malek MFrank A(2006)A mobile computing approach for navigation purposesProceedings of the 6th international conference on Web and Wireless Geographical Information Systems10.1007/11935148_12(123-134)Online publication date: 4-Dec-2006
https://dl.acm.org/doi/10.1007/11935148_12
Ogale VGarg V(2006)Brief announcementProceedings of the 20th international conference on Distributed Computing10.1007/11864219_41(548-550)Online publication date: 18-Sep-2006
https://dl.acm.org/doi/10.1007/11864219_41
Xu BQian JZhang XWu ZChen L(2005)A brief survey of program slicingACM SIGSOFT Software Engineering Notes10.1145/1050849.105086530:2(1-36)Online publication date: 1-Mar-2005
https://dl.acm.org/doi/10.1145/1050849.1050865
Li HRilling JGoswami D(2004)Granularity-Driven Dynamic Predicate Slicing Algorithms for Message Passing SystemsAutomated Software Engineering10.1023/B:AUSE.0000008668.12782.6c11:1(63-89)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1023/B%3AAUSE.0000008668.12782.6c
Mittal NGarg V(2003)Software Fault Tolerance of Distributed Programs Using Computation SlicingProceedings of the 23rd International Conference on Distributed Computing Systems10.5555/850929.851965Online publication date: 19-May-2003
https://dl.acm.org/doi/10.5555/850929.851965
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents