Dependency Tracking

• Chain Clocks: The happened-before relation in used in concurrent systems to capture the order of events. This information about the ordering between events is required by many applications such as debugging and monitoring of distributed programs and fault tolerance. 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. We present a class of logical clock algorithms, called chain clock, for tracking dependencies between relevant events. 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. (PODC 2005, Distributed Computing 2006)
• Topology Based Clocks: We present a new method of timestamping messages and events in synchronous computations that capture the order relationship with vectors of size less than or equal to the size of the vertex cover of the communication topology of the system. Our method is applicable to all applications that either use programming languages which use synchronous communication such as CSP, or use synchronous remote procedure calls. Since the size of our timestamps is dependent upon the size of edge decomposition of the communication topology, we give an approximation algorithm that returns an edge decomposition which is at most twice the size of the optimal edge decomposition. (ICDCS 2002)
• String Realizers: we show the connection between vector clocks used in distributed computing and dimension theory of partially ordered sets. Based on this connection, we provide lower bounds on the number of coordinates for timestamping events in a distributed computation for capturing the happened-before relation. To this end, we introduce the notion of a string realizer and the string dimension of a poset. For distributed computing and other applications, the concept of string realizer is more natural than the chain realizer used in the classical dimension theory. We establish the relationship between the string dimension and the chain dimension of a poset. Using this relationship and Dilworth's theorem for the chain dimension of finite distributive lattices, we obtain the desired lower bound. The concept of strings also has applications in efficient encoding of partial orders because it requires fewer bits to encode a string realizer than a chain realizer. (PODC 2001)