Quantitative causality
Abstract
Events generated by the execution of a distributed system are related by causality and concurrency. While providing a means of reasoning about the relative occurrence of events, this partial order fails to represent the timeliness of occurrence. In this paper, we develop a novel means of assigning weights to events where the weights are reduced as the temporal proximity to an anchor event decreases. This weight quantifies the strength of the causal or concurrent relationship with respect to an anchor event. Those events that causally succeed the anchor are the focus of this paper with concurrency and causally preceding being part of future work plans. Three methods of computing event weights for causally succeeding events are defined. Each contains a tunable parameter to determine the rate of weight decrease. The methods are piece-wise linear, exponential, and relevant vector difference decay. A case study has been performed that applied quantitative causality to the well-known software engineering problem of feature location. A summary of the case study results is provided to illustrate the utility of quantitative causality for succeeding events.
References
[1]
{1} Emmanuelle Anceaume, Jean-Michel Hélary, and Michel Raynal. Tracking immediate predecessors in distributed computations. In Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, pages 210-ACM Press, 2002.
[2]
{2} Anish Arora, Sandeep Kulkarni, and Murat Demirbas. Resettable vector clocks. In Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, pages 269-278. ACM Press, 2000.
[3]
{3} Ted Biggerstaff, Bharat Mitbander, and Dallas Webster. Program understanding and the concept assignment problem. Communications of the ACM, 37(5):72-83, May 1994.
[4]
{4} K. M. Chandy, J. Misra, and L. Haas. Distributed deadlock detection. ACM Transactions on Computer Systems, 1(2):144-156, 1983.
[5]
{5} Bernadette Charron-Bost. Concerning the size of logical clocks in distributed systems. Information Processing Letters, 39: 11-16, July 1991.
[6]
{6} Kumrong Chen and Vaclav Rajlich. Case study of feature location using dependence graph. In Proceedings of the 8th International Workshop on Program Comprehension - IWPC 2000, pages 241-249, Los Alamitos, California, June 2000. IEEE Computer Society.
[7]
{7} R. Cooper and K. Marzulo. Consistent detection of global predicates. In Proceedings of the ACM SIGPLAN and SIGOPS Workshop on Parallel and Distributed Debugging, pages 163-173, 1991.
[8]
{8} J. Deprez and A. Lakhotia. A formalism to automate mapping from program features to code. In Proceedings of the 8th International Workshop on Program Comprehension - IWPC 2000, pages 69-78, Los Alamitos, California, June 2000. IEEE Computer Society.
[9]
{9} E. Dijkstra, W. Feijen, and A. van Gasteren. Derivation of a termination detection algorithm for distributed computations. Information Processing Letters, 16: 217-219, 1983.
[10]
{10} P. S. Dodd and C. V. Ravishankar. Monitoring and debugging distributed real-time programs. Software Practice and Experience, 22(10):863-877, October 1992.
[11]
{11} Dennis Edwards, Sharon Simmons, and Norman Wilde. An approach to feature location in distributed systems. Journal of Systems and Software, 79(1):57-68, January 2006.
[12]
{12} C. J. Fidge. Partial orders for parallel debugging. In Proceedings of the ACM SIGPLAN and SIGOPS Workshop on Parallel and Distributed Debugging, pages 183-194, University of Queensland, May 1988.
[13]
{13} K. K. Garg and C. Chase. Distributed algorithms for detecting conjunctive predicates. In International Conference of Distributed Computing Systems, pages 423-430, June 1995.
[14]
{14} A. Gravey and A. Dupuis. Performance evaluation of two mutual exclusion distributed protocols via markovian modeling. In Proceedings of the Sixth IFIP Workshop on Protocol Specification, Testing, and Verification, pages 335-346, 1987.
[15]
{15} Mehdi Hashemzadeh, Nacer Farajzadeh, and Abolfazl T. Haghighat. Optimal detection and resolution of distributed deadlocks in the generalized model. In 14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, pages 133-136, Feb 2006.
[16]
{16} Curtis E. Hrischuk and C. Murray Woodside. Logical clock requirements for reverse engineering scenarions from a distributed system. IEEE Transactions on Software Engineering, 28(4):321-339, Apr 2002.
[17]
{17} J. Janb. Performance features of global states based application control. In 14th Euramicro International Conference on Parallel, Distributed, and Network-based Processing, pages 276-279, Feb 2006.
[18]
{18} Ahmed Khoumsi. A temporal approach for testing distributed systems. IEEE Transactions on Software Engineering, 28(11):1085-1103, Nov 2002.
[19]
{19} L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7): 558-565, 1978.
[20]
{20} Friedemann Mattern. Virtual time and global states of distributed systems. In M. Cosnard et. al., editor, Proceedings of the International Workshop on Parallel and Distributed Algorithms, pages 215-226. Elsevier Science Publishers B. V., 1989.
[21]
{21} Message Passing Interface Forum. MPI: A message-passing interface standard (version 1.1). Technical report, MPI-Forum, http://www.mpi-forum.org, 1995.
[22]
{22} Message Passing Interface Forum. MPI-2: Extensions to the message-passing interface. Technical report, MPI-Forum, http://www.mpi-forum.org, July 1997.
[23]
{23} S. Rana. A distributed solution of the distributed termination problem. Information Processing Letters, 17: 43-46, 1983.
[24]
{24} B. A. Sanders and P. A. Heuberger. Distributed deadlock detection and resolution with probes. In J-C. Bermond and M. Raynal, editors, Proceedings of the Third International Workshop on Distributed Algorithms, number 392 in Lecture Notes in Computer Science, pages 207-218. Springer-Verlag, 1989.
[25]
{25} Werner Schutz. Fundamental issues in testing distributed real-time systems. Real- Time Systems, 7(2): 129-157, September 1994.
[26]
{26} Sharon Simmons and Dennis Edwards. Convergence of time decay for event weights. In The 2006 International Conference on Parallel & Distributed Processing Techniques & Applications, Las Vegas, Nevada, June 2006. World Academy of Science. To appear.
[27]
{27} Sharon Simmons and Phil Kearns. A causal assert statement for distributed systems. In M. H. Hamza, editor, Proceedings of the Seventh IASTED/ISMM International Conference on Parallel and Distributed Computing and Systems, pages 495-498. IASTED/ISMM, IASTED-ACTA Press, October 1995.
[28]
{28} R. Strom and S. Yemini. Optimistic recovery in distributed systems. ACM Transactions on Computer Systems, 3(3): 204-226, 1985.
[29]
{29} Tongchit Tantikul and D. Manivannan. A communication-induced checkpointing and asynchronous recovery protocol for mobile computing systems. In Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies, pages 70-74, Dec 2005.
[30]
{30} S. Venkatesan and Tony T-Y. Juang. Efficient algorithms for optimistic crash recovery. Distributed Computing, 8: 105-114, 1994.
[31]
{31} Xinli Wang and Jean Mayo. A general model for detecting distributed termination in dynamic systems. In Proceedings of the 18th International Parallel and Distributed Processing Symposium, page 84, Apr 2004.
[32]
{32} Norman Wilde and Michael Scully. Software reconnaissance: Mapping program features to code. Journal of Software Maintenance: Research and Practice, 7: 49-62, January 1995.
Index Terms
- Quantitative causality
Recommendations
Vector time and causality among abstract events in distributed computations
An important problem in analyzing distributed computations is the amount of information. In event-based models, even for simple applications, the number of events is large and the causal structure is complex. Event abstraction can be used to reduce the ...
Causality and atomicity in distributed computations
In a distributed system, high-level actions can be modeled by nonatomic events. This paper proposes causality relations between distributed nonatomic events and provides efficient testing conditions for the relations. The relations provide a fine-...
Detecting causal relationships in distributed computations: in search of the holy grail
The paper shows that characterizing the causal relationship between significant events is an important but non-trivial aspect for understanding the behavior of distributed programs. An introduction to the notion of causality and its relation to logical ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Dynamic Publishers, Inc.
United States
Publication History
Published: 01 March 2007
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
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.
Sign in