Fault Tolerance in Finite State Machines using Fusion (2009)
Bharath Balasubramanian, Vinit Ogale, Vijay K. Garg
Abstract. Given a set of n different deterministic finite state machines (DFSMs), we examine the problem of tolerating k faults among them. The traditional approach to this problem involves...
Abstract. Correct distributed programs are hard to write. Not surprisingly, distributed systems are especially vulnerable to software faults. Testing and debugging is an important way to improve the...
Abstract. Correct distributed programs are hard to write. Not surprisingly, distributed systems are especially vulnerable to software faults. Testing and debugging is an important way to improve the...
We illustrate the effectiveness of our techniques in POTA on test cases such as the General Inter-ORB Protocol (GIOP) [18]. POTA also contains a module that translates execution traces to Promela...
c ○ Springer-Verlag 1998 Detection of global predicates: Techniques and their limitations ⋆ (2009)
Summary. We show that the problem of predicate detection in distributed systems is NP-complete. In the past, efficient algorithms have been developed for special classes of predicates such as stable...
Vijay K. Garg, Neeraj Mittal, Alper Sen
In this note, we discuss the applications of lattice theory to solving problems in distributed systems. The first problem we consider is that of detecting a predicate in a computation, i.e.,...
Online Algorithms for Dilworth’s Chain Partition (2008)
There are many interesting applications of partial order theory in distributed and parallel systems. These include testing and monitoring the concurrent behaviour of the system. Dilworth’s chain...
Detecting Temporal Logic Predicates on the Happened-Before Model (2008)
Detection of a global predicate is a fundamental problem in distributed computing. In this paper we describe new predicate detection algorithms for certain temporal logic predicates. We use a...
Solving Computation Slicing Using Predicate Detection (2008)
Neeraj Mittal, Alper Sen, Vijay K. Garg
Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies...
We illustrate the effectiveness of our techniques in POTA on test cases such as the General Inter-ORB Protocol (GIOP) [18]. POTA also contains a module that translates execution traces to Promela...
Finding Satisfying Global States: All for One and One (2008)
For All, Neeraj Mittal, Alper Sen, Vijay K. Garg
z\Lambda
Vijay K. Garg, Craig Chase, J. Roger, Mitchell Richard Kilgore
Previous work in efficient detection of global predi-cates was restricted to predicates that could be specified as a boolean formula of local predicates. Many prop-erties in distributed systems,...
Vijay K. Garg, Neeraj Mittal, Alper Sen
We survey applications of the theory of partial orders to distributed computing. A distributed computation is a poset on the set of events based on the observable happened-before relation. Online...
Distributed Maintenance of a Spanning Tree using Labeled Tree Encoding (2008)
Maintaining spanning trees in a distributed fashion is central to many networking applications and selfstabilizing algorithms provide an elegant way of doing it in fault-prone environments. In this...
Formal verification of a system-on-chip using computation slicing (2008)
Alper Sen, Jayanta Bhadra, Vijay K. Garg, Jacob A. Abraham
Formal verification of Systems-on-Chips (SoCs) is an immense challenge to current industrial practice. Most existent formal verification techniques are extremely computation intensive and produce...
Formal verification of a system-on-chip using computation slicing (2008)
Alper Sen, Jayanta Bhadra, Vijay K. Garg, Jacob A. Abraham
Formal verification of Systems-on-Chips (SoCs) is an immense challenge to current industrial practice. Most existent formal verification techniques are extremely computation intensive and produce...
Sujatha Kashyap, Vijay K. Garg
It has been shown that global predicate detection in a distributed computation is an NP-complete problem in general. However, polynomial-time predicate detection algorithms exist for some classes of...
dency Tracking for Relevant Events in Shared Memory System ” which (2008)
Anurag Agarwal, Vijay K. Garg, Anurag Agarwal, Vijay K. Garg
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 prob-lems. Moreover,...
Predicate Detection on Infinite Computations (2008)
Earlier work on predicate detection has assumed that the given computation is finite. Detecting violation of a liveness predicate requires that the predicate be evaluated on an infinite computation....
Distributed Maintenance of a Spanning Tree using Labeled Tree Encoding (2008)
Abstract. Maintaining spanning trees in a distributed fashion is central to many networking applications. In this paper, we propose a self-stabilizing algorithm for maintaining a spanning tree in a...
We discuss two fundamental problems that arise in distributed systems. First, how to determine the order in which various events were executed. Second, how to obtain a consistent view of the system....
Fusible Data Structures for Fault-Tolerance (2008)
We introduce the concept of fusible data structures to maintain fault-tolerant data in distrib-uted programs. Given a fusible data structure it is possible to combine a set of such structures into a...
Vijay K. Garg, Neeraj Mittal, Alper Sen
We survey applications of the theory of partial orders to distributed computing. A distributed computation is a poset on the set of events based on the observable happened-before relation. Online...
Summary. Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems should be able...
Vijay K. Garg, Neeraj Mittal, Chakarat Skawratananond
Determining order relationship between events of a distributed computation is a fundamen-tal problem in distributed systems which has applications in many areas including debugging, visualization,...
Hemphill Park Austin, Ashis Tarafdar, Advisor Prof, Vijay K. Garg
48> ffl Software Engineer Intern, SNA Server Group, Microsoft Corporation, Seattle, Washington, Summer 1995. Designed and implemented an FTP-AFTP Gateway Service for Windows NT allowing FTP...
An Algebra for Probabilistic Processes (2007)
We define probabilistic languages and probabilistic automata over a finite set of events. We also define operators under which the set of probabilistic languages(p-languages) is closed, thus forming...
Modeling Stochastic Discrete Event Systems Using Probabilistic Languages (2007)
Vijay K. Garg, Ratnesh Kumar, Steven I. Marcus
The formalism of probabilistic languages has been introduced for modeling the qualitative behavior of stochastic discrete event systems. A probabilistic language is a unit interval valued map over...
Corrections to "Finite Buffer Realization of Input-Output Discrete Event Systems" (2007)
Ratnesh Kumar, Vijay K. Garg, Steven I. Marcus
This note presents a correction to [1, Theorem 4] which provides a necessary and sufficient condition for dispatchability. 1 Notation The following additional notation is introduced: The notation s...
Ashis Tarafdar, Advisor Prof, Vijay K. Garg
re Engineer Intern, SNA Server Group, Microsoft Corporation, Seattle, Washington, Summer 1995. Designed and implemented an FTP-AFTP Gateway Service for Windows NT allowing FTP clients to access IBM...
Exploiting Symmetry for Analysis of Distributed Systems (2007)
Distributed systems are difficult to design and the simplest of them can have subtle errors. Conventional automatic analysis techniques to catch these errors may be infeasible because the system may...
Control of Event Separation Times in Discrete Event Systems (2007)
The class of timed discrete event systems which can be modelled by automata known as timed event graphs are structurally related to finite state machines. Consequently, supervisory control problems...
Chakarat Skawratananond, Vijay K. Garg
Abstract- Since radio spectrum is a scarce resource, efficient allocation of frequency channels is critical for the performance of mobile systems. The update approach is a way to allocate radio...
Algorithmic Combinatorics based on Slicing (2007)
Abstract. We show that some recent results in slicing of a distributed computation can be applied to developing algorithms to solve problems in combinatorics. A combinatorial problem usually requires...
Causality for Time: How to Specify and Verify Distributed Algorithms (2007)
Vijay K. Garg, Alexander I. Tomlinson
We illustrate a technique for proving properties of distributed programs. Our technique avoids the notion of global time or global state. Furthermore, it does not require any use of temporal logic....
Detecting Conjunctions of Global Predicates (2007)
Vijay K. Garg, J. Roger Mitchell
We present an efficient algorithm to detect if the conjunction of two nonlocal predicates is possibly true in a distributed computation. For offline detection of such global predicates, our algorithm...
Debugging in a Distributed World: Observation and Control (2007)
Debugging distributed programs is considerably more difficult than debugging sequential programs. We address issues in debugging distributed programs and provide a general framework for observing and...
An Efficient Deterministic Algorithm for the Resource Discovery Problem (2007)
We address the problem of how best to get a group of machines on a network to learn of each others existence; this is referred to as the Resource Discovery Problem (RDP). Straightforward algorithms...
Abstract. We generalize the notion of slice introduced in our earlier paper [6]. A slice of a distributed computation with respect to a global predicate is the smallest computation that contains all...
Neeraj Mittal, Neeraj Mittal, Vijay K. Garg, Vijay K. Garg
We generalize the notion of slice introduced in our earlier paper [8]. A slice of a distributed computation with respect to a global predicate is the smallest computation that contains all consistent...
Neeraj Mittal, Neeraj Mittal, Vijay K. Garg, Vijay K. Garg
We generalize the notion of slice introduced in our earlier paper [6]. A slice of a distributed computation with respect to a global predicate is the smallest computation that contains all consistent...
Ashis Tarafdar, Ashis Tarafdar, Vijay K. Garg, Vijay K. Garg
The happened before model has been widely used to model distributed computations. In particular, it has been used to model the logical time and the potential causality aspects of a distributed...
Abstract. We generalize the notion of slice introduced in our earlier paper [6]. A slice of a distributed computation with respect to a global predicate is the smallest computation that contains all...
R. Kumar, V. K. Garg, S. I. Marcus, Ratnesh Kumar, Vijay K. Garg, Steven I. Marcus
This note presents a correction to [1, Theorem 4] which provides a necessary and su cient condition for dispatchability. 1 Notation The following additional notation is introduced: The notation s L s...
Formal Verification of Simulation Traces Using Computation Slicing (2007)
Abstract—Concurrent and distributed systems, such as System-on-Chips (SoCs), present an immense challenge for verification due to their complexity and inherent concurrency. Traditional approaches...
Testing Concurrent Software Systems Publication No. (2006)
Richard Brian Kilgore, Craig M Chase, Jacob A Abraham, Vijay K Garg, Aleta M Ricciardi, ...
Two approaches to testing concurrent software are presented. In the first, a system is assumed to contain a deterministic computation when correct, and I describe two testing algorithms to optimally...
Gustavo De Veciana, Vijay K. Garg, Harrick Vin, Sanjay Shakkottai, Sriram Vishwanath, Shailesh Patil, ...
Dedicated to my parents, who have always encouraged me.
A Critique of Java for Concurrent Programming (2005)
been increasing by a factor of two every year, so your desktop has at least a thousand processors. Furthermore, your desktop is connected to millions of other processors whose power you can tap into....
Rectangles are Better than Chains for Encoding Partially Ordered Sets (2005)
Partial orders have applications in various areas in computer science such as distributed systems, object oriented languages, knowledge representation systems and databases. In this paper we present...
Designing a Resilient Routing Infrastructure for Peer-to-Peer Networks (2005)
Huaiyu Liu, Simon S. Lam, James C. Browne, Vijay K. Garg, Mohamed G. Gouda, Aloysius K. Mok, ...
To my parents, Hanting and Xueqin To my husband, Fei Acknowledgments This dissertation would not become a reality without the generous help from many people and the love and support from my family. I...
Finding Satisfying Global States: All for One and One for All (2004)
Neeraj Mittal, Alper Sen, Vijay K. Garg, Ranganath Atreya
Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies...
Finding Satisfying Global States: All for One and One for All (2004)
Neeraj Mittal, Alper Sen, Vijay K. Garg, Ranganath Atreya
Abstract. Given a distributed computation and a global predicate, predicate detection is concerned with determining whether there exists at least one consistent cut (or global state) of the...
On reducing the global state graph for verification of distributed computations (2004)
Arindam Chakraborty, Vijay K. Garg
Correct distributed programs are very hard to write and reason about. Verification of distributed programs with respect to their specifications is thus very important to ensure that a distributed...
Self-stabilizing spanning tree algorithm with a new design methodology (2004)
Maintaining spanning trees in a distributed fashion is central to many networking applications. In this paper, we propose a self-stabilizing algorithm for maintaining a spanning tree in a distributed...
Finding Satisfying Global States: All for One and One for All (2004)
Neeraj Mittal, Alper Sen, Vijay K. Garg, Ranganath Atreya
Given a distributed computation and a global predicate, predicate detection is concerned with determining whether there exists at least one consistent cut (or global state) of the computation that...
Techniques and Applications of Computation Slicing (2003)
Mittal, Neeraj, Garg, Vijay K.
Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems, especially those...
Applications of lattice theory to distributed computing (2003)
Sergio Rajsbaum, Vijay K. Garg, Neeraj Mittal, Alper Sen
The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases,...
Detecting Locally Stable Predicates without Modifying Application Messages (2003)
Ranganath Atreya, Neeraj Mittal, Vijay K. Garg
Abstract. In this paper, we give an ecient algorithm to determine whether a locally stable predicate has become true in an underlying computation. Examples of locally stable predicates include...
Partial Order Trace Analyzer (POTA) for Distributed Programs (2003)
Checking the correctness of software is a growing challenge. In this paper, we present a prototype implementation of Partial Order Trace Analyzer (POTA), a tool for checking execution traces of both...
Detecting Locally Stable Predicates without Modifying Application Messages (2003)
Ranganath Atreya, Neeraj Mittal, Vijay K. Garg
Abstract In this paper, we give an efficient algorithm to determine whether a locally stable predicate has become true in an underlying computation. Our algorithm uses only O(n) control messages to...
Applications of lattice theory to distributed computing (2003)
Vijay K. Garg, Neeraj Mittal, Alper Sen
In this note, we discuss the applications of lattice theory to solving problems in distributed systems. The rst problem we consider is that of detecting a predicate in a computation, i.e.,...
On checking whether a predicate definitely holds (2003)
Predicate detection is an important problem in testing and debugging distributed programs. Cooper and Marzullo introduced two modalities possibly and definitely as a solution to this problem. Given a...
Enumerating Global States of a Distributed Computation (2003)
Global predicate detection is a fundamental problem in distributed computing in the areas of distributed debugging and software fault-tolerance. It requires searching the global state lattice of a...
Predicate Control: Synchronization in Distributed Computations with Look-ahead (2003)
The predicate control problem involves synchronizing a distributed computation to maintain a given global predicate. In contrast with many popular distributed synchronization problems such as mutual...
Detecting Temporal Logic Predicates in Distributed Programs Using Computation Slicing (2003)
Detecting whether a finite execution trace (or a computation) of a distributed program satisfies a given predicate, called predicate detection, is a fundamental problem in distributed systems. It...
Dedicated to my parents, (2003)
Jangwon Lee, Gustavo De Veciana, Vijay K. Garg, Edward J. Powers, Scott M. Nettles, Harrick M. Vin, ...
I owe a special gratitude to my advisor; Professor Gustavo de Veciana. His invaluable advice and feedback made me advance throughout my research career at UT-AUSTIN. Furthermore, he always found time...
Partial Order Trace Analyzer (POTA) for Distributed Programs (2003)
Checking the correctness of software is a growing challenge. In this paper, we present a prototype implementation of Partial Order Trace Analyzer (POTA), a tool for checking execution traces of both...
Detecting temporal logic predicates in distributed programs using computation slicing (2003)
Detecting whether a finite execution trace (or a computation) of a distributed program satisfies a given predicate, called predicate detection, is a fundamental problem in distributed systems. It...
Software Fault Tolerance of Distributed Programs Using Computation Slicing (2003)
Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems, especially those...
Predicate control: Synchronization in distributed computations with look-ahead (2003)
The predicate control problem involves synchronizing a distributed com-putation to maintain a given global predicate. In contrast with many popular distributed synchronization problems such as mutual...
Detecting Locally Stable Predicates without Modifying Application Messages (2003)
Ranganath Atreya, Neeraj Mittal, Vijay K. Garg
Abstract. In this paper, we give an efficient algorithm to determine whether a locally stable predicate has become true in an underlying computation. Examples of locally stable predicates include...
Neeraj Mittal, Vijay K. Garg, Anish Arora, Craig M. Chase, Mohamed G. Gouda, Aloysius K. Mok, ...
To my parents
Algorithmic Combinatorics based on Slicing Posets (2002)
We show that some recent results in slicing of a distributed computation can be applied to developing algorithms to solve problems in combinatorics. A combinatorial problem usually requires...
Detecting Temporal Logic Predicates on the Happened-Before Model (2002)
Detection of a global predicate is a fundamental problem in distributed computing. In this paper we describe new predicate detection algorithms for certain temporal logic predicates. We use a...
Vijay K. Garg, Chakarat Skawratananond
Determining order relationship between events in distributed computations is a fundamental problem with applications in distributed monitoring systems and faulttolerance. Fidge and Mattern's...
Detecting Temporal Logic Predicates on the Happened-Before Model (2002)
sen,garg¢ Detection of a global predicate is a fundamental problem in distributed computing. In this paper we describe new predicate detection algorithms for certain temporal logic predicates. We...
Computation Slicing: Techniques and Theory (2001)
Abstract. We generalize the notion of slice introduced in our earlier paper [6]. A slice of a distributed computation with respect to a global predicate is the smallest computation that contains all...
On slicing a distributed computation (2001)
We introduce the notion of a slice of a distributed computation. A slice of a distributed computation with respect to a global predicate is a computation which captures those and only those...
On detecting global predicates in distributed computations (2001)
Monitoring of global predicates is a fundamental problem in asynchronous distributed systems. This problem arises in various contexts such as design, testing and debugging, and fault-tolerance of...
On slicing a distributed computation (2001)
We introduce the notion of a slice of a distributed computation. A slice of a distributed computation with respect to a global predicate is a computation which captures those and only those...
String Realizers of Posets with Applications to Distributed Computing (2001)
Vijay K. Garg, Chakarat Skawratananond
In this paper, 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...
Control of Stochastic Discrete Event Systems Modeled by Probabilistic Languages (2001)
In earlier papers [7, 6, 5] we introduced the formalism of probabilistic languages for modeling the stochastic qualitative behavior of discrete event systems (DESs). In this paper we study their...
Debugging distributed programs using controlled re-execution (2000)
Distributed programs are hard to write. A distributed debugger equipped with the mechanism to re-execute the traced computation in a controlled fashion can greatly facilitate the detection and...
Debugging distributed programs using controlled re-execution (2000)
Distributed programs are hard to write. A distributed debugger equipped with the mechanism to re-execute the traced computation in a controlled fashion can greatly facilitate the detection and...
Debugging distributed programs using controlled re-execution (2000)
Neeraj Mittal, Neeraj Mittal, Vijay K. Garg, Vijay K. Garg
Distributed programs are hard to write. A distributed debugger equipped with the mechanism to re-execute the traced computation in a controlled fashion can greatly facilitate the detection and...
Optimistic Recovery in Multi-threaded Distributed Systems (1999)
Om P. Damani, Ashis Tarafdar, Vijay K. Garg
The problem of recovering distributed systems from crash failures has been widely studied in the context of traditional non-threaded processes. However, extending those solutions to the...
Software Fault Tolerance of Concurrent Programs Using Controlled Re-execution (1999)
Abstract. Concurrent programs often encounter failures, such as races, owing to the presence of synchronization faults (bugs). One existing technique to tolerate synchronization faults is to roll...
A max-plus algebra of signals for the supervisory control of real-time discrete event systems (1998)
In this paper, we define a max-plus algebra of signals for the evaluation of timing behavior of discrete event systems modeled by timed event graphs. We restrict ourselves to infinite, periodic...
Consistency Conditions for Multi-Object Distributed Operations (1998)
Neeraj Mittal, Neeraj Mittal, Vijay K. Garg, Vijay K. Garg
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...
Implementable failure detectors in asynchronous systems (1998)
Vijay K. Garg, Vijay K. Garg, J. Roger Mitchell, J. Roger Mitchell
Failure detection is one of the most fundamental modules of any fault-tolerant distributed system. The failure detectors discussed in the literature so far are either impossible to implement in an...
A Lightweight Algorithm for Causal Message Ordering in Mobile Computing Systems (1998)
Chakarat Skawratananond, Chakarat Skawratananond, Neeraj Mittal, Neeraj Mittal, Vijay K. Garg, Vijay K. Garg
With the popularity of portable computers and the improvements of wireless networking, there is a great deal of interest in developing applications for mobile computing systems. Causally ordered...
Detection of global predicates: Techniques and their limitations (1998)
We show that the problem of predicate detection in distributed systems is NP-complete. In the past, efficient algorithms have been developed for special classes of predicates such as stable...
Detection of global predicates: Techniques and their limitations (1998)
We show that the problem of predicate detection in distributed systems is NP-complete. In the past, efficient algorithms have been developed for special classes of predicates such as stable...
A Lightweight Algorithm for Causal Message Ordering in Mobile Computing Systems (1998)
Chakarat Skawratananond, Neeraj Mittal, Vijay K. Garg
Causally ordered message delivery is a required property for several distributed applications particularly those that involve human interactions (such as teleconferencing and collaborative work). In...
Analyzing non-deterministic real-time systems with (max,+) algebra (1998)
Guillaume P. Brat, Vijay K. Garg
We describe a hierarchical technique that allows a class of non-deterministic timed Petri nets to be analyzed using the (max,+) algebra of periodic signals. We show that the timing and...
Consistency Conditions for Multi-Object Distributed Operations (1998)
Neeraj Mittal, Neeraj Mittal, Vijay K. Garg, Vijay K. Garg
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...
Predicate control for active debugging of distributed programs (1998)
Existing approaches to debugging distributed systems involve a cycle of passive observation followed by computation replaying. We propose predicate control as an active approach to debugging such...
A non-blocking recovery algorithm for causal message logging (1998)
J. Roger Mitchell, Vijay K. Garg
In the recovery of failed processes in a distributed program, causal logging schemes offer several benefits. These benefits include no rollback of unfailedprocesses and simple approaches to output...
A Lightweight Algorithm for Causal Message Ordering in Mobile Computing Systems (1998)
Chakarat Skawratananond, Neeraj Mittal, Vijay K. Garg
Causally ordered message delivery is a required property for several distributed applications particularly those that involve human interactions (such as teleconferencing and collaborative work). In...
Consistency Conditions for Multi-Object Distributed Operations (1998)
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...
A Lightweight Algorithm for Causal Message Ordering in Mobile Computing Systems (1998)
Chakarat Skawratananond, Chakarat Skawratananond, Neeraj Mittal, Neeraj Mittal, Vijay K. Garg, Vijay K. Garg
With the popularity of portable computers and the improvements of wireless networking, there is a great deal of interest in developing applications for mobile computing systems. Causally ordered...
Predicate Control for Active Debugging of Distributed Programs (1998)
Existing approaches to debugging distributed systems involve a cycle of passive observation followed by computation replaying. We propose predicate control as an active approach to debugging such...
Control of Stochastic Discrete Event Systems: Synthesis (1998)
In our earlier papers [7, 6, 5] we introduced the formalism of probabilistic languages for modeling the stochastic qualitative behavior of discrete event systems (DESs). We presented a framework for...
A (max,+) Algebra for Non-Stationary and Non-Deterministic Periodic Discrete Event Systems (1998)
Guillaume Philippe Brat, Dipl D'ing'enieur, Vijay K. Garg, Miroslaw Malek, Aristotle Arapostathis, Aloysius K. Mok, ...
vii List of Figures xiii Chapter 1
Addressing False Causality while Detecting Predicates in Distributed Programs (1998)
The partial-order model of distributed computations based on the happened before relation has been criticized for allowing false causality between events. Our strong causality model addresses this...
Distributed predicate detection in a faulty environment (1998)
Vijay K. Garg, J. Roger Mitchell
There has been very little research in distributed predicate detection for faulty, asynchronous environments. In this paper we define a class of predicates called set decreasing predicates which can...
Control Of Stochastic Discrete Event Systems: Existence (1998)
Ratnesh Kumar Vijay, Vijay K. Garg
In earlier papers [3, 2, 1] we introduced the formalism of probabilistic languages for modeling the stochastic qualitative behavior of discrete event systems (DESs). In this paper we present a...
Detection of Global Predicates: Techniques and their Limitations (1998)
We show that the problem of predicate detection in distributed systems is NP-complete. In the past, efficient algorithms have been developed for special classes of predicates such as stable...
Fault-tolerant distributed simulation (1998)
In traditional distributed simulation schemes, entire simulation needs to be restarted if any of the participating LP crashes. This is highly undesirable for long running simulations. Some form of...
A (max,+) Algebra for Non-Stationary Periodic Timed Discrete Event Systems (1998)
Guillaume P. Brat, Vijay K. Garg
We define and implement a (max,+) algebra of signals for the timing analysis of discrete event systems expressed as timed event graphs. A system is defined by the infinite, periodic time sequences of...
Heat Transfer on a Film-Cooled Rotating Blade Using a Two-Equation Turbulence Model (1998)
A three-dimensional Navier–Stokes code has been used to compare the heat transfer coefficient on a film-cooled, rotating turbine blade. The blade chosen is the ACE rotor with five rows containing...
Optimistic distributed simulation based on transitive dependency tracking (1997)
Om P. Damani, Yi-min Wang, Vijay K. Garg
In traditional optimistic distributed simulation protocols, a logical process(LP) receiving a straggler rolls back and sends out anti-messages. Receiver of an anti-message may also roll back and send...
Monitoring Functions on Global States of Distributed Programs (1997)
Alexander I. Tomlinson, Vijay K. Garg
The domain of a global function is the set of all global states of an execution of a distributed program. We show how to monitor a program in order to determine if there exists a global state in...
Distributed recovery with K-optimistic logging (1997)
Yi-min Wang, Om P. Damani, Vijay K. Garg
Fault-tolerance techniques based on checkpointing and message logging have been increasingly used in real-world applications to reduce service downtime. Most industrial applications have chosen...
Observation and Control for Debugging Distributed Computations (1997)
Vijay Garg Parallel, Vijay K. Garg
I present a general framework for observing and controlling a distributed computation and its applications to distributed debugging. Algorithms for observation are useful in distributed debugging to...
Observation and Control for Debugging Distributed Computations (1997)
I present a general framework for observing and controlling a distributed computation and its applications to distributed debugging. Algorithms for observation are useful in distributed debugging to...
Predicate Control in Distributed Systems (1997)
A number of important problems in asynchronous distributed systems can be formulated as special cases of the notion of controlling a distributed system to maintain global properties. We formalize...
Optimistic Distributed Simulation Based on Transitive Dependency Tracking (1997)
Om P. Damani, Yi-min Wang, Vijay K. Garg
In traditional optimistic distributed simulation protocols, a logical process(LP) receiving a straggler rolls back and sends out anti-messages. Receiver of an anti-message may also roll back and send...
A Quorum-based Distributed Channel Allocation Algorithm for Mobile Computing Systems (1997)
Chakarat Skawratananond, Chakarat Skawratananond, Vijay K. Garg, Vijay K. Garg
Since radio spectrum is a scarce resource, efficient allocation of frequency channels is critical for the performance of mobile computing systems. The update approach is a way to allocate radio...
Distributed Recovery with (1997)
Optimistic Logging, Yi-min Wang, Om P. Damani, Vijay K. Garg
Fault-tolerance techniques based on checkpointing and message logging have been increasingly used in real-world applications to reduce service downtime. Most industrial applications have chosen...
Distributed Recovery with (1997)
Optimistic Logging, Yi-min Wang, Om P. Damani, Vijay K. Garg
Fault-tolerance techniques based on checkpointing and message logging have been increasingly used in real-world applications to reduce service downtime. Most industrial applications have chosen...
Observation and Control for Debugging Distributed Computations (1997)
Ipresent a general framework for observing and controlling a distributedcomputation and its applications to distributed debugging. Algorithms for observation are useful in distributed debugging to...
Wireless and personal communications systems / V.K. Garg, J.E. Wilkes. (1996)
Garg, Vijay K., Wilkes, Joseph E.
Incluye índice
Probabilistic Language Framework for Stochastic Discrete Event Systems (1996)
Garg, Vijay K., Kumar, Ratnesh, Marcus, Steven I.
We introduce the notion of probabilistic languages to describe the qualitative behavior of stochastic discrete event systems. Regular language operators such as choice, concatenation, and...
Observation of global properties in distributed systems (1996)
Observation of global properties of a distributed program is required in many applications such as debugging of programs and fault-tolerance in distributed systems. I present a survey of algorithms...
How to recover efficiently and asynchronously when optimism fails (1996)
We propose a new algorithm for recovering asynchronously from failures in a distributed computation. Our algorithm is based on two novel concepts- a fault-tolerant vector clock to maintain causality...
Normality: A Consistency Condition for Concurrent Objects (1996)
Michel Raynal, Vijay K. Garg, Vijay K. Garg, Projet Adp
: Linearizability is a consistency condition for concurrent objects (objects shared by concurrent processes) that exploits the semantics of abstract data types. It provides the illusion that each...
Observation of Global Properties in Distributed Systems (1996)
Observation of global properties of a distributed program is required in many applications such as debugging of programs and fault-tolerance in distributed systems. I present a survey of algorithms...
Normality: A Consistency Condition for Concurrent Objects (1996)
Linearizability is a consistency condition for concurrent objects (objects shared by concurrent processes) that exploits the semantics of abstract data types. It provides the illusion that each...
Detection of Strong Unstable Predicates in Distributed Programs (1996)
Vijay K. Garg, Brian Waldecker
This paper discusses detection of global predicates in a distributed program. A run of a distributed program results in a set of sequential traces, one for each process. These traces may be combined...
An Efficient Algorithm for Detecting Conjunctions of General Global Predicate (1996)
V. K. Garg, J. Roger Mitchel, Vijay K. Garg, J. Roger Mitchell
The ability to detect global predicates is important for distributed fault monitoring systems as well as distributed debugging. In this paper, we present an efficient algorithm to detect if the...
How to Recover Efficiently and Asynchronously when Optimism Fails (1996)
We propose a new algorithm for recovering asynchronously from failures in a distributed computation. Our algorithm is based on two novel concepts - a fault-tolerant vector clock to maintain causality...
Expressing and detecting general control flow properties of distributed computations (1995)
Vijay K Garg, Eddy Fromentin, Alex Tomlinson, Michel Raynal
Properties of distributed computations can be either on their global states or on their control flows. This paper addresses control flow properties. It first presents a simple yet powerful logic for...
Deriving Distributed Algorithms from a General Predicate Detector (1995)
J. Roger Mitchell, Vijay K. Garg
Designing and debugging distributed systems requires the detection of conditions across the entire system. As an illustration, monitoring the status of an application requires detection of...
Optimal Supervisory Control of Discrete Event Dynamical Systems (1995)
We formalize the notion of optimal supervisory control of discrete event dynamical systems (DEDS's) in the framework of Ramadge and Wonham. A DEDS is modeled as a state machine, and is...
In this paper we study supervisory control of discrete event systems using state variables for representation and specification. The motivation is two fold: firstly, a state variable representation...
In this paper we study supervisory control of discrete event systems using state variables for representation and specification. The motivation is two fold: firstly, a state variable representation...
Finite Buffer Realization of Input-Output Discrete Event Systems (1995)
Ratnesh Kumar, Vijay K. Garg, Steven I. Marcus
Many discrete event systems (DESs) such as manufacturing systems, database management systems, communication networks, traffic systems, etc., can be modeled as input-output discrete event systems...
Observation of Software for Distributed Systems with RCL (1995)
Alexander Tomlinson, Er I. Tomlinson, Vijay K. Garg
. Program observation involves formulating a query about the behavior of a program and then observing the program as it executes in order to determine the result of the query. Observation is used in...
Efficient Detection of Restricted Classes of Global Predicates (1995)
We show that the problem of predicate detection in distributed systems is NP-complete. We introduce a class of predicates, linear predicates, such that for any linear predicate B there exists an...
How to Recover Efficiently and Asynchronously when Optimism Fails (1995)
Om P. Damani, Om P. Damani, Vijay K. Garg, Vijay K. Garg
We propose a new algorithm for recovering asynchronously from failures in a distributed computation. Our algorithm is based on two novel concepts - a fault-tolerant vector clock to maintain causality...
State Avoidance Control for Infinite State Systems using Assignment Program Model (1995)
In this paper we study supervisory control of discrete event systems using state variables for representation and specification. The motivation is two fold: firstly, a state variable representation...
Model Uncertainty in Discrete Event Systems (1995)
Earlier work concerning control of discrete event systems usually assumed that a correct model of the system to be controlled was available. A goal of this wok is to provide an algorithm for...
Finite Buffer Realization of Input-Output Discrete Event Systems (1995)
Ratnesh Kumar, Vijay K. Garg, Steven I. Marcus
Many discrete event systems (DESs) such as manufacturing systems, data base management systems, communication networks, traffic systems, etc., can be modeled as input-output discrete event systems...
Efficient Detection of Restricted Classes of Global Predicates (1995)
. We show that the problem of predicate detection in distributed systems is NP-complete. We introduce a class of predicates, linear predicates, such that for any linear predicate B there exists an...
Conjunctive Predicate Detection (1995)
Vijay K. Garg, Craig M. Chase, J. Roger Mitchell, Richard Kilgore
This paper discusses efficient detection of global predicates in a distributed program. Previous work in detection of global predicates was restricted to predicates that could be specified as a...
Detecting Conjunctive Channel Predicates in a Distributed Programming Environment (1995)
J. Roger, Mitchell Richard Kilgore, Vijay Garg, Vijay K. Garg, Craig Chase, Craig Chase, ...
This paper discusses efficient detection of global predicates in a distributed program. Previous work in efficient detection of global predicates was restricted to predicates that could be specified...
Finite Buffer Realization of Input-Output Discrete Event Systems (1994)
Kumar, R., Garg, Vijay K., Marcus, S.I.
Many discrete event systems (DESs) such as manufacturing systems, data base management systems, communication networks, traffic systems, etc., can be modeled as input-output discrete event systems...
Maintaining global assertions on distributed sytems (1994)
Alexander I. Tomlinson, Vijay K. Garg
This paper develops a method for maintaining global assertions on a network of distributed processes. The global assertion has the form (X 1
On The Fly Testing Of Regular Patterns In Distributed Computations (1994)
Eddy Fromentin Michel, Eddy Fromentin, Michel Raynal, Michel Raynal, Vijay K Garg, Vijay K Garg, ...
: A class of properties of distributed computations is described and an algorithm which detects them is presented. This class of properties called regular patterns allows the user to specify an...
Alex Tomlinson, Eddy Fromentin, Michel Raynal, Vijay K Garg, Vijay K Garg
: Properties of distributed computations can be either on their global states or on their control flows. This paper addresses control flow properties. It first presents a simple yet powerful logic...
Eddy Fromentin, Michel Raynal, Vijay K Garg, Alex Tomlinson
: A class of properties of distributed computations is described and an algorithm which detects them is presented. This class of properties called regular patterns allows the user to specify an...
Repeated Computation of Global Functions in a Distributed Environment (1994)
In a distributed system, many algorithms need repeated computation of a global function. These algorithms generally use a static hierarchy for gathering necessary data from all processes. As a...
Detection of Weak Unstable Predicates in Distributed Programs (1994)
Vijay K. Garg, Brian Waldecker
This paper discusses detection of global predicates in a distributed program. Earlier algorithms for detection of global predicates proposed by Chandy and Lamport work only for stable predicates. A...
Distributed Algorithms for Detecting Conjunctive Predicates (1994)
This paper discusses efficient distributed detection of global conjunctive predicates in a distributed program. Previous work in detection of such predicates is based on a checker process. The...
Supervisory Control of Real-time Discrete Event Systems Using Lattice Theory (1994)
Darren D. Cofer, Vijay K. Garg
The behavior of timed DES can be described by sequences of event occurrence times. These sequences can be ordered to form a lattice. Since logical (untimed) DES behaviors described by regular...
Optimal Sensor and Actuator Choices for Discrete Event Systems (1994)
Stanley D. Young, Vijay K. Garg
We present algorithms to optimally choose sensors and actuators to control a given discrete event system so that the closed loop behavior satisfies a specified constraint. The main results of this...
Expressing and Detecting Control Flow Properties of Distributed Computations (1994)
Vijay K. Garg, Vijay K Garg, Alex Tomlinson, Alex Tomlinson, Eddy Fromentin, Eddy Fromentin, ...
: Properties of distributed computations can be either on their global states or on their control flows. This paper addresses control flow properties. It first presents a simple yet powerful logic...
On the Fly Testing of Regular Patterns in Distributed Computations (1994)
Eddy Fromentin, Michel Raynal, Vijay K Garg, Alex Tomlinson
: A class of properties of distributed computations is described and an algorithm which detects them is presented. This class of properties called regular patterns allows the user to specify an...
Supervisory Control of Real-time Discrete Event Systems using Lattice Theory (1994)
Darren D. Cofer, Vijay K. Garg
The behavior of timed DES can be described by sequences of event occurrence times. These sequences can be ordered to form a lattice. Since logical (untimed) DES behaviors described by regular...
Repeated computation of global functions in a distributed environment (1994)
Abstract- In a distributed system, many algorithms need repeated computation of a global function. These algorithms generally use a static hierarchy for gathering necessary data from all processes....
Using Induction to Prove Properties of Distributed Programs (1993)
Vijay K. Garg, Alexander I. Tomlinson
Proofs of distributed programs are often informal due to the difficulty of developing formal proofs. Properties of distributed programs are often stated using Lamport's causally-precedes...
An Algorithm for Minimally Latent Global Virtual Time (1993)
Alexander I. Tomlinson, Vijay K. Garg
Global virtual time (GVT) is used in distributed simulations to reclaim memory, commit output, detect termination, and handle errors. It is a global function that is computed many times during the...
A self-stabilizing system is one which can recover from transient faults in a finite number of steps. We present a theory for determining if a behavior specification can be satisfied with a...
Control of Discrete Event Systems Modeled with Deterministic Buchi Automata (1992)
Stanley Young, Damir Spanjol, Vijay K. Garg
A discrete event system (DES) is a dynamic system which evolves in response to the occurrence of specific events at discrete points in time. Ramadge and Wonham have established a control theory of...
On Supervisory Control of Sequential Behaviors (1992)
Ratnesh Kumar, Vijay K. Garg, Steven I. Marcus
We address the supervisory synthesis problem for controlling the sequential behaviors of Discrete Event Dynamical Systems (DEDS's) under complete as well as partial information through the use...
Concurrent Regular Expressions and their Relationship to Petri Nets (1992)
We define algebraic systems called concurrent regular expressions which provide a modular description of languages of Petri nets. Concurrent regular expressions are extension of regular expressions...
Kumar, R., Garg, Vijay K., Marcus, S.I.
Most discrete event system models are based on defining the alphabet set or the set of events as a fundamental concept. In this paper, we take an alternative view of treating the state space as the...
Stable Behavior and Stabilizing Supervisor for Discrete Event Dynamical Systems (1991)
Kumar, R., Garg, Vijay K., Marcus, S.I.
The paper studies stability and stabilizability of Discrete event Dynamical Systems (DEDS's) in the framework of Ramadge and Wonham. We define stability and stabilizability in terms of the behavior...
Modeling of Distributed Systems by Concurrent Regular Expressions (1989)
We propose an algebraic model called concurrent regular expressions for modeling and analysis of distributed systems. These expressions extend regular expressions with four operators- interleaving,...
Evaluating the Performance (1989)
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...
Extremal Solutions of Inequations over Lattices with Applications to Supervisory Control
We study the existence and computation of extremal solutions of a system of inequations defined over lattices. Using the Knaster-Tarski fixed point theorem, we obtain sufficient conditions for the...
Implementable Failure Detectors in Asynchronous Systems
Vijay K. Garg, J. Roger Mitchell
The failure detectors discussed in the literature so far are impossible to implement in an asynchronous system. We introduce a failure detector called infinitely often accurate failure detector which...
Extremal Solutions of Inequations over Lattices with Applications to Supervisory Control
We study the existence and computation of extremal solutions of a system of inequations defined over lattices. Using the Knaster-Tarski fixed point theorem, we obtain sufficient conditions for the...