Efficient dependency tracking for relevant events in shared-memory systems

ABSTRACT

In a concurrent system with N processes, vector clocks of size N are used for tracking dependencies between the events. Using vectors of size N leads to scalability problems. Moreover, association of components with processes makes vector clocks cumbersome and inefficient for systems with a dynamic number of processes. We present a class of logical clock algorithms, called chain clock, for tracking dependencies between relevant events based on generalizing a process to any chain in the computation poset. Chain clocks are generally able to track dependencies using fewer than N components and also adapt automatically to systems with dynamic number of processes. We compared the performance of Dynamic Chain Clock (DCC) with vector clock for multithreaded programs in Java. With 1% of total events being relevant events, DCC requires 10 times fewer components than vector clock and the timestamp traces are smaller by a factor of 100. Although DCC requires shared data structures, it is still 10 times faster than vector clock in our experiments.

REFERENCES

• 1: A. Agarwal and V. K. Garg. Chain clocks: Efficient dependency tracking for shared-memory systems. Technical report, University of Texas at Austin, 2004. Available as "http://maple.ece.utexas.edu/TechReports/2004/TR-PDS-2004-005.ps".
• 2: Sridhar Alagar , Subbarayan Venkatesan, Techniques to Tackle State Explosion in Global Predicate Detection, IEEE Transactions on Software Engineering, v.27 n.8, p.704-714, August 2001 [doi>10.1109/32.940566 ]
• 3: Koenraad Audenaert, Clock Trees: Logical Clocks for Programs with Nested Parallelism, IEEE Transactions on Software Engineering, v.23 n.10, p.646-658, October 1997 [doi>10.1109/32.637147 ]
• 4: Özalp Babaoğlu , Keith Marzullo, Consistent global states of distributed systems: fundamental concepts and mechanisms, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 5: R. Baldoni and G. Melideo. Tradeoffs in message overhead versus detection time in causality tracking. Technical Report 06-01, Dipartimento di Informatica e Sistemistica, Univ. of Rome, 2000.
• 6: Bernadette Charron-Bost, Concerning the size of logical clocks in distributed systems, Information Processing Letters, v.39 n.1, p.11-16, July 12, 1991 [doi>10.1016/0020-0190(91)90055-M ]
• 7: Robert Cooper , Keith Marzullo, Consistent detection of global predicates, Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, p.167-174, May 20-21, 1991, Santa Cruz, California, United States
• 8: B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, 1990.
• 9: Stefan Felsner, On-line chain partitions of orders, Theoretical Computer Science, v.175 n.2, p.283-292, April 10, 1997
• 10: C. J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. Proc. of the 11th Australian Computer Science Conference, 10(1):56--66, Feb 1988.
• 11: Vijay K. Garg , Chakarat Skawratananond, String realizers of posets with applications to distributed computing, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.72-80, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383988]
• 12: Vijay K. Garg , Chakarat Skawratananond, Timestamping Messages in Synchronous Computations, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.552, July 02-05, 2002
• 13: V. K. Garg and B. Waldecker. Detection of unstable predicates. In Proc. of the Workshop on Parallel and Distributed Debugging, Santa Cruz, CA, May 1991. ACM/ONR.
• 14: H. A. Kierstead. Recursive colorings of highly recursive graphs. Canad. J. Math, 33(6):1279--1290, 1981.
• 15: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 16: Keith Marzullo , Laura S. Sabel, Efficient detection of a class of stable properties, Distributed Computing, v.8 n.2, p.81-91, October 1994 [doi>10.1007/BF02280830]
• 17: F. Mattern. Virtual time and global states of distributed systems. In Parallel and Distributed Algorithms: Proc. of the Int'l Workshop on Parallel and Distributed Algorithms, pages 215--226, 1989.
• 18: Koushik Sen , Grigore Rosu , Gul Agha, Runtime safety analysis of multithreaded programs, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 19: Mukesh Singhal , Ajay Kshemkalyani, An efficient implementation of vector clocks, Information Processing Letters, v.43 n.1, p.47-52, Aug. 10, 1992 [doi>10.1016/0020-0190(92)90028-T ]
• 20: Rob Strom , Shaula Yemini, Optimistic recovery in distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.204-226, Aug. 1985 [doi>10.1145/3959.3962]
• 21: Francisco J. Torres-Rojas , Mustaque Ahamad, Plausible Clocks: Constant Size Logical Clocks for Distributed Systems, Proceedings of the 10th International Workshop on Distributed Algorithms, p.71-88, October 09-11, 1996
• 22: Paul A. S. Ward, A framework algorithm for dynamic, centralized dimension-bounded timestamps, Proceedings of the 2000 conference of the Centre for Advanced Studies on Collaborative research, p.14, November 13-16, 2000, Mississauga, Ontario, Canada
• 23: D. B. West. The Art of Combinatorics Volume III: Order and Optimization. Preprint edition.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation

General Terms:
Algorithms, Performance

Keywords:
predicate detection, shared-memory, vector clock