Distributed Algorithms

Distributed Simulation

    We have developed a new optimistic distributed simulation algorithm. This algorithm does not use anti-messages and thus not only reduces the overhead of anti-messages but also eliminates the need for output queues.
  1. O. Damani, Y. M. Wang, V. K. Garg,``Optimistic Distributed Simulation Based on Transitive Dependancy Tracking,''Proc. ACM Workshop on Parallel and Distributed Simulation (PADS), Lockenhaus,Austria, June 1997, pp. 90 - 97.Abstract ...........Postscript ...........Tech Report

    2. We have also developed an algorithm to tolerate hardware faults in optimistic distributed simulation. Our algorithm treats the hardware faults and causality errors in distributed simulation in a unifrom manner.
  2. O. Damani, V. K. Garg,``Fault-tolerant Optimistic Distributed Simulation ''Proc. ACM Workshop on Parallel and Distributed Simulation (PADS), Canada, May 1998, pp. 38 - 45.PDF

    3. We have also developed an efficient algorithm for bounding global virtual time which is useful for interactive simulation.
  3. A. I. Tomlinson, V. K. Garg, ``An Algorithm for Minimally Latent Global Virtual Time,''Proc. 7th Workshop on Parallel and Distributed Simulation,San Diego, California, May 1993, pp. 35-42.Abstract ...........Postscript ...........Tech Report

    4. Vector 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$.
  4. Anurag Agarwal, Vijay K. Garg, Efficient Dependency Tracking for Relevant Events in Concurrent Systems, Distributed Computing (DC) accepted pdf ... springer
    5. A preliminary version appeared as
  5. Anurag Agarwal, Vijay K. Garg, Chain Clock: Efficient Causality Tracking for Shared Memory Systems, ACM Symposium on Principles of Distributed Computing (PODC'2005) Las Vegas, July 2005, pp. 19-28. pdf .... slides
    6. For synchronous computations, we have developed a topology based clocks. In the following paper, 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.
  6. Vijay K. Garg, C. Skawratananond, On Timestamping Synchronous Computations, Proc. IEEE International Conference on Distributed Computing Systems (ICDCS), Vienna, July 2002.Abstract ...........Postscript

    7. Finally, we have also introduces 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.
  7. Vijay K. Garg, C. Skawratananond, String Realizers of Posets with Applications to Distributed Computing, ACM Symposium on Principles of Distributed Computing (PODC'01), August 26-29, 2001, Newport, Rhode Island, pp. 72 - 80.Abstract ...........Postscript ...........journal version

    8. Consistency Conditions

    The traditional Distributed Shared Memory (DSM) model provides atomicity at levels of read and write on single objects. Therefore, multi-object operations such as double compare and swap, and atomic m-register assignment cannot be efficiently expressed in this model. We extend the traditional DSM model to allow operations to span multiple objects. We show that memory consistency conditions such as sequential consistency and linearizability can be extended to this general model. We also provide algorithms to implement these consistency conditions in a distributed system.
  8. N. Mittal and V. K. Garg,Consistency Conditions for Multi-Object Distributed Operations,Proc. IEEE International Conference on Distributed Computing Systems, Amsterdam, Netherlands, May 1998, pp. 582 - 589.Abstract ...........Postscript ...........Technical Report

    9. We propose a new memory consistency condition called Normality that is equivalent to linearizability for single object operations but weaker than linearizability for multi-object operations. Normality is better suited for distributed systems because it does not refer to global-time. Normality also satisfies locality and non-blocking.
  9. Vijay K. Garg and Michel Raynal. Normality: A consistency condition for concurrent objects. Parallel Processing Letters, 9(1):123-134, 1999.
    Abstract ...........Postscript

    10. Global Functions

    Many tasks in distributed systems consists of repeatedlt computing a global function. Imposing a tree-like structure is natural to gather the arguments of the function and broadcast the result. Can we get symmetry in spite of the hierarchy. The following paper show how. The technique is illustrated for distributed branch-and-bound problem, and for asynchronous computation of fixed points.
  10. V.K. Garg, and J. Ghosh,``Repeated Computation of Global Functions in a Distributed Environment'',IEEE Transactions on Parallel and Distributed Systems,Vol. 5, No. 8, August 1994, pp. 823-834.Abstract ...........pdf

    11. This paper develops a method for maintaining global assertions on a network of distributed processes. The global assertions are assumed to be in sum-of-product form. This research has applications in distributed software development, and as a general synchronization mechanism. Many classical synchronization problems (mutual exclusion, dining philosophers, readers/writers) can be solved with the results of this work.
  11. A. I. Tomlinson, V. K. Garg, ``Maintenance of Global Assertions in Distributed Systems,'' Proc. International Conference on ComputerScience and Education, Bangalore, India, June 1994, Tata McGraw-HillPublishing Company Limited, pp. 257 -- 272.Abstract ...........Postscript ...........Tech Report