A framework algorithm for dynamic, centralized dimension-bounded timestamps

ABSTRACT

Vector timestamps can be used to characterize causality in a distributed computation. This is essential in an observation context where we wish to reason about the partial order of execution. Unfortunately, all current dynamic vector-timestamp algorithms require a vector of size equal to the number of processes in the computation. This fundamentally limits the scalability of such observation systems. In this paper we present a framework algorithm for dynamic vector timestamps whose size can be as small as the dimension of the partial order of execution. While the dimension can be as large as the number of processes, in general it is much smaller.The algorithm consists of three interleaved phases: computing the critical pairs, creating extensions that reverse those critical pairs, and assigning vectors to each event based on the extensions created. We present complete solutions for the first two phases and a partial solution for the third phase.

REFERENCES

• 1: 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]
• 2: Colin Fidge, Logical Time in Distributed Computing Systems, Computer, v.24 n.8, p.28-33, August 1991 [doi>10.1109/2.84874]
• 3: {3} Colin Fidge. Fundamentals of distributed systems observation. Technical Report 93-15, Software Verification Research Centre, Department of Computer Science, The University of Queensland, St. Lucia, QLD 4072, Australia, November 1993.
• 4: {4} Jerry Fowler and Willy Zwaenepoel. Causal distributed breakpoints. In Proceedings of the 10th IEEE International Conference on Distributed Computing Systems, pages 134-141. IEEE Computer Society Press, 1990.
• 5: {5} Claude Jard and Guy-Vincent Jourdan. Dependency tracking and filtering in distributed computations. Technical Report 851, IRISA, Campus de Beaulieu - 35042 Rennes Cedex - France, August 1994.
• 6: {6} Thomas Kunz, James P. Black, David J. Taylor, and Twan Basten. POET: Targetsystem independent visualisations of complex distributed-application executions. The Computer Journal, 40(8):499-512, 1997.
• 7: 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]
• 8: {8} 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, Chateau de Bonas, France, December 1988. Elsevier Science Publishers B. V. (North Holland).
• 9: {9} Oystein Ore. Theory of Graphs, volume 38. Amer. Math. Soc. Colloq. Publ., Providence, R.I., 1962.
• 10: Darrell Ronald Raymond , W. M. Tompa, Partial-order databases, 1996
• 11: Michel Raynal , Mukesh Singhal, Logical Time: Capturing Causality in Distributed Systems, Computer, v.29 n.2, p.49-56, February 1996 [doi>10.1109/2.485846]
• 12: Reinhard Schwarz , Friedemann Mattern, Detecting causal relationships in distributed computations: in search of the holy grail, Distributed Computing, v.7 n.3, p.149-174, March 1994 [doi>10.1007/BF02277859]
• 13: 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]
• 14: {14} James Alexander Summers. Precedence-Preserving Abstraction for Distributed Debugging. Master's thesis, University of Waterloo, Waterloo, Ontario, 1992.
• 15: {15} David J. Taylor. Event displays for debugging and managing distributed systems. In Proceedings of the International Workshop on Network and Systems Management, pages 112-124, August 1995.
• 16: {16} William T. Trotter. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore, MD, 1992.
• 17: {17} Paul Ward. On the scalability of distributed debugging: Vector clock size. Technical Report CS98-29, Shoshin Distributed Systems Group, Department of Computer Science, The University of Waterloo, Waterloo, Ontario, Canada N2L 3G1, December 1998. Available at ftp://cs-archive.uwaterloo.ca/csarchive/CS-98-29/CS-98-29.ps.Z.
• 18: Paul A. S. Ward, An Offline Algorithm for Dimension-Bound Analysis, Proceedings of the 1999 International Conference on Parallel Processing, p.128, September 21-24, 1999
• 19: Paul A. S. Ward, An Online Algorithm for Dimension-Bound Analysis, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.144-153, August 31-September 03, 1999
• 20: {20} Mihalis Yannakakis. The complexity of the partial order dimension problem. SIAM Journal on Algebraic and Discrete Methods, 3(3):351-358, September 1982.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Formal methods

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Distributed debugging

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Algorithms, Design, Experimentation, Theory, Verification

Keywords:
Ore timestamp, dimension, distributed computation, distributed-system observation, partial order, scalability, vector timestamp