@MISC{AgaGar06, TITLE = {Predicate Detection on Infinite Computations}, AUTHOR = {Anurag Agarwal and Vijay K. Garg}, YEAR = {2006}, LANGUAGE = {en}, PDF = {http://www.ece.utexas.edu/%7Egarg/dist/cav06.pdf} } @INPROCEEDINGS{GGS06, TITLE = {Scalable Algorithms for Global Snapshots in Distributed Systems}, AUTHOR = {Rahul Garg and Vijay K. Garg and Yogish Sabharwal}, BOOKTITLE = {PODC}, BOOKTITLE = {Proceedings of the {ACM} Conference on Supercomputing, 2006}, PUBLISHER = {ACM}, YEAR = {2006}, PDF = {http://www.ece.utexas.edu/%7Egarg/dist/snapshot.pdf}, URL = {http://www.ece.utexas.edu/%7Egarg/dist/ics06.ppt} } @ARTICLE{journals/dc/AgarwalG06, TITLE = {Efficient Dependency Tracking for Relevant Events in Concurrent Systems}, AUTHOR = {Anurag Agarwal and Vijay K. Garg}, JOURNAL = {Distributed Computing}, YEAR = {2006}, PDF = {http://www.ece.utexas.edu/%7Egarg/dist/agarwal-garg-DC.pdf}, URL = {http://dx.doi.org/10.1007/s00446-006-0004-y}, NOTE = {to appear} } @ARTICLE{journals/ipl/PatilG06, TITLE = {Adaptive general perfectly periodic scheduling}, AUTHOR = {Shailesh Patil and Vijay K. Garg}, JOURNAL = {Inf. Process. Lett}, YEAR = {2006}, NUMBER = {3}, VOLUME = {98}, BIBDATE = {2006-04-27}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/ipl/ipl98.html#PatilG06}, PAGES = {107--114}, URL = {http://dx.doi.org/10.1016/j.ipl.2005.12.009}, PDF = {http://www.ece.utexas.edu/%7Egarg/dist/adaptivegeneralPPS.pdf} } @ARTICLE{journals/tc/Garg06, TITLE = {Algorithmic Combinatorics based on Slicing Posets}, AUTHOR = {Vijay K. Garg}, JOURNAL = {Theoretical Computer Science}, YEAR = {2006}, PDF = {http://www.ece.utexas.edu/%7Egarg/dist/tcs06.pdf}, NOTE = {to appear} } @MISC{AMS, TITLE = {Using Order in Distributed Computing}, AUTHOR = {Vijay K. Garg and Neeraj Mittal and Alper Sen}, BOOKTITLE = {American Mathematical Society National Meeting}, YEAR = {2006}, MONTH = JAN, LANGUAGE = {en}, PDF = {http://www.ece.utexas.edu/%7Egarg/dist/ams06.pdf}, URL = {http://www.ece.utexas.edu/%7Egarg/dist/ams06-short.pdf}, NOTE = {invited} } @INPROCEEDINGS{conf/podc/AgarwalG05, TITLE = {Efficient dependency tracking for relevant events in shared-memory systems}, AUTHOR = {Anurag Agarwal and Vijay K. Garg}, BIBDATE = {2006-02-15}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/podc/podc2005.html#AgarwalG05}, BOOKTITLE = {Proceedings of the Twenty-Fourth Annual {ACM} Symposium on Principles of Distributed Computing, {PODC} 2005, Las Vegas, {NV}, {USA}, July 17-20, 2005}, PUBLISHER = {ACM}, YEAR = {2005}, EDITOR = {Marcos Kawazoe Aguilera and James Aspnes}, PAGES = {19--28}, URL = {http://doi.acm.org/10.1145/1073814.1073818} } @INPROCEEDINGS{conf/kbse/KashyapG05, TITLE = {Exploiting predicate structure for efficient reachability detection}, AUTHOR = {Sujatha Kashyap and Vijay K. Garg}, BIBDATE = {2006-02-13}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/kbse/ase2005.html#KashyapG05}, BOOKTITLE = {ASE}, BOOKTITLE = {20th {IEEE}/{ACM} International Conference on Automated Software Engineering ({ASE} 2005), November 7-11, 2005, Long Beach, {CA}, {USA}}, PUBLISHER = {ACM}, YEAR = {2005}, EDITOR = {David F. Redmiles and Thomas Ellman and Andrea Zisman}, PAGES = {4--13}, URL = {http://doi.acm.org/10.1145/1101908.1101913} } @INPROCEEDINGS{conf/europar/GargA05, TITLE = {Distributed Maintenance of a Spanning Tree Using Labeled Tree Encoding}, AUTHOR = {Vijay K. Garg and Anurag Agarwal}, BIBDATE = {2005-09-13}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/europar/europar2005.html#GargA05}, BOOKTITLE = {Euro-Par}, BOOKTITLE = {Euro-Par 2005, Parallel Processing, 11th International Euro-Par Conference, Lisbon, Portugal, August 30 - September 2, 2005, Proceedings}, PUBLISHER = {Springer}, YEAR = {2005}, VOLUME = {3648}, EDITOR = {Jos{\'e} C. Cunha and Pedro D. Medeiros}, ISBN = {3-540-28700-0}, PAGES = {606--616}, SERIES = {Lecture Notes in Computer Science}, URL = {http://dx.doi.org/10.1007/11549468_68} } @ARTICLE{journals/dsonline/GargM05, TITLE = {A Critique of Java for Concurrent Programming}, AUTHOR = {Vijay K. Garg and Neeraj Mittal}, JOURNAL = {IEEE Distributed Systems Online}, YEAR = {2005}, NUMBER = {9}, VOLUME = {6}, BIBDATE = {2006-05-04}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/dsonline/dsonline6.html#GargM05}, URL = {http://doi.ieeecomputersociety.org/10.1109/MDSO.2005.43} } @ARTICLE{journals/ipl/KashyapG05, TITLE = {Intractability results in predicate detection}, AUTHOR = {Sujatha Kashyap and Vijay K. Garg}, JOURNAL = {Inf. Process. Lett}, YEAR = {2005}, NUMBER = {6}, VOLUME = {94}, BIBDATE = {2006-04-26}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/ipl/ipl94.html#KashyapG05}, PAGES = {277--282}, URL = {http://dx.doi.org/10.1016/j.ipl.2005.02.008} } @ARTICLE{journals/dc/MittalG05, TITLE = {Techniques and applications of computation slicing}, AUTHOR = {Neeraj Mittal and Vijay K. Garg}, JOURNAL = {Distributed Computing}, YEAR = {2005}, NUMBER = {3}, VOLUME = {17}, BIBDATE = {2005-04-25}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/dc/dc17.html#MittalG05}, PAGES = {251--277}, URL = {http://dx.doi.org/10.1007/s00446-004-0117-0} } @INPROCEEDINGS{conf/ipps/MittalSGA04, TITLE = {Finding Satisfying Global States: All for One and One for All}, AUTHOR = {Neeraj Mittal and Alper Sen and Vijay K. Garg and Ranganath Atreya}, PUBLISHER = {IEEE Computer Society}, YEAR = {2004}, BIBDATE = {2004-07-01}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/ipps/ipdps2004-c.html#MittalSGA04}, BOOKTITLE = {IPDPS}, ISBN = {0-7695-2132-0}, URL = {http://csdl.computer.org/comp/proceedings/ipdps/2004/2132/01/213210066babs.htm} } @ARTICLE{journals/dc/MittalG04, TITLE = {Finding missing synchronization in a distributed computation using controlled re-execution}, AUTHOR = {Neeraj Mittal and Vijay K. Garg}, JOURNAL = {Distributed Computing}, YEAR = {2004}, NUMBER = {2}, VOLUME = {17}, BIBDATE = {2005-03-14}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/dc/dc17.html#MittalG04}, PAGES = {107--130}, URL = {http://www.springerlink.com/index/10.1007/s00446-003-0104-x} } @ARTICLE{journals/jpdc/TarafdarG04, TITLE = {Predicate control: synchronization in distributed computations with look-ahead}, AUTHOR = {Ashis Tarafdar and Vijay K. Garg}, JOURNAL = {J. Parallel Distrib. Comput}, YEAR = {2004}, NUMBER = {2}, VOLUME = {64}, BIBDATE = {2004-07-05}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/jpdc/jpdc64.html#TarafdarG04}, PAGES = {219--237}, URL = {http://dx.doi.org/10.1016/j.jpdc.2003.11.004} } @MISC{oai:CiteSeerPSU:636849, TITLE = {{ACM} {SIGACT} News Distributed Computing Column 12}, AUTHOR = {Vijay K. Garg and Neeraj Mittal and Alper Sen}, YEAR = {2004}, MONTH = MAY # {~10}, CITESEER-REFERENCES = {oai:CiteSeerPSU:160542; oai:CiteSeerPSU:563530; oai:CiteSeerPSU:419813; oai:CiteSeerPSU:444044; oai:CiteSeerPSU:503358; oai:CiteSeerPSU:453289; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:451880; oai:CiteSeerPSU:491537; oai:CiteSeerPSU:624514; oai:CiteSeerPSU:448922}, ANNOTE = {Vijay K. Garg (ECE Department; University of Texas); Neeraj Mittal (CS Department; University of Texas , Dallas; Richardson , TX , USA); Alper Sen (ECE Department; University of Texas);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, DESCRIPTION = {this paper do}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:636849}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/636849.html; http://theory.lcs.mit.edu/%7Erajsbaum/col12.ps} } @MISC{oai:CiteSeerPSU:639065, TITLE = {Detecting Locally Stable Predicates without Modifying Application Messages}, AUTHOR = {Ranganath Atreya and Neeraj Mittal and Vijay K. Garg}, YEAR = {2004}, MONTH = JAN # {~19}, CITESEER-REFERENCES = {oai:CiteSeerPSU:27551; oai:CiteSeerPSU:533432; oai:CiteSeerPSU:18234; oai:CiteSeerPSU:9383; oai:CiteSeerPSU:145873}, ANNOTE = {Ranganath Atreya (2?; Department of Computer Science , The University of Texas at Dallas , Richardson; TX 75083 , USA); Vijay K. Garg (2; Department of Electrical and Computer Engineering , The University of Texas at; Austin , Austin , TX 78712 , USA);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, DESCRIPTION = {In this paper, we give an ecient algorithm to determine whether a locally stable predicate has become true in an underlying computation.}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:639065}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/639065.html; http://www.ece.utexas.edu/%7Egarg/dist/stable.ps} } @MISC{oai:CiteSeerPSU:688936, TITLE = {Detecting Temporal Logic Predicates in Distributed Programs Using}, AUTHOR = {Alper Sen and Vijay K. Garg}, YEAR = {2004}, MONTH = JAN # {~15}, ABSTRACT = {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 finds applications in many domains such as testing, debugging, and monitoring of distributed programs. However predicate detection suffers from the state explosion problem -- the number of possible global states of the program increases exponentially with the number of processes.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:418597; oai:CiteSeerPSU:473928; oai:CiteSeerPSU:419813; oai:CiteSeerPSU:549841}, ANNOTE = {Alper Sen (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , TX , 78712 , USA); Vijay K. Garg (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , TX , 78712 , USA);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:688936}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/688936.html; http://www.ece.utexas.edu/%7Egarg/dist/opodis03-alper.ps} } @MISC{oai:CiteSeerPSU:698159, TITLE = {Formal Verification of a System-on-Chip Using Computation Slicing}, AUTHOR = {Alper Sen and Jayanta Bhadra and Vijay K. Garg and Jacob A. Abraham}, YEAR = {2004}, MONTH = JUL # {~12}, ABSTRACT = {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 good results only when used on individual sub-components of SoCs. Without major modifications they are of little e#ectiveness in the SoC world. We attack the problem of SoC verification using an elegant abstraction mechanism, called computation slicing, and show that it enables e#ective temporal property verification on large designs. The technique targets a set of execution sequences, that is exhaustive with respect to an intended subset of system level properties, and automatically finds counter-example execution sequences in case of errors in the design. We have obtained exponential gains in reducing the global state space using a polynomial-time algorithm, and also applied a polynomial-time algorithm for checking global liveness and safety properties. We have successfully applied the technique to verify properties on two high level transaction based designs -- the MSI cache coherence protocol and an admittedly academic SoC having a bus arbiter and a parameterizable number of devices connected to a PCI bus backbone.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:367316; oai:CiteSeerPSU:252243; oai:CiteSeerPSU:563530; oai:CiteSeerPSU:419813; oai:CiteSeerPSU:206738; oai:CiteSeerPSU:503358; oai:CiteSeerPSU:453289; oai:CiteSeerPSU:494336; oai:CiteSeerPSU:491537; oai:CiteSeerPSU:634737; oai:CiteSeerPSU:570082; oai:CiteSeerPSU:709173}, ANNOTE = {Alper Sen (1 The University of Texas at Austin 2 Motorola Inc); Jayanta Bhadra (1 The University of Texas at Austin 2 Motorola Inc); Vijay K. Garg (1 The University of Texas at Austin 2 Motorola Inc); Jacob A. Abraham (1 The University of Texas at Austin 2 Motorola Inc);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:698159}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/698159.html; http://www.ece.utexas.edu/%7Egarg/dist/itc04.ps} } @INPROCEEDINGS{conf/opodis/SenG03, TITLE = {Detecting Temporal Logic Predicates in Distributed Programs Using Computation Slicing}, AUTHOR = {Alper Sen and Vijay K. Garg}, PUBLISHER = {Springer}, YEAR = {2003}, VOLUME = {3144}, BIBDATE = {2004-07-29}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/opodis/opodis2003.html#SenG03}, BOOKTITLE = {OPODIS}, EDITOR = {Marina Papatriantafilou and Philippe Hunel}, ISBN = {3-540-22667-2}, PAGES = {171--183}, SERIES = {Lecture Notes in Computer Science}, URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3144&spage=171} } @INPROCEEDINGS{conf/fates/SenG03, TITLE = {On Checking Whether a Predicate Definitely Holds}, AUTHOR = {Alper Sen and Vijay K. Garg}, PUBLISHER = {Springer}, YEAR = {2003}, VOLUME = {2931}, BIBDATE = {2004-01-27}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/fates/fates2003.html#SenG03}, BOOKTITLE = {FATES}, EDITOR = {Alexandre Petrenko and Andreas Ulrich}, ISBN = {3-540-20894-1}, PAGES = {15--29}, SERIES = {Lecture Notes in Computer Science}, URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=2931&spage=15} } @INPROCEEDINGS{conf/icdcs/MittalG03, TITLE = {Software Fault Tolerance of Distributed Programs Using Computation Slicing}, AUTHOR = {Neeraj Mittal and Vijay K. Garg}, PUBLISHER = {IEEE Computer Society}, YEAR = {2003}, BIBDATE = {2003-06-26}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/icdcs/icdcs2003.html#MittalG03}, BOOKTITLE = {ICDCS}, ISBN = {0-7695-1920-2}, PAGES = {105}, URL = {http://csdl.computer.org/comp/proceedings/icdcs/2003/1920/00/19200105abs.htm} } @ARTICLE{journals/entcs/SenG03, TITLE = {Partial Order Trace Analyzer ({POTA}) for Distributed Programs}, AUTHOR = {Alper Sen and Vijay K. Garg}, JOURNAL = {Electr. Notes Theor. Comput. Sci}, YEAR = {2003}, NUMBER = {2}, VOLUME = {89}, BIBDATE = {2004-07-28}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/entcs/entcs89.html#SenG03}, URL = {http://www.elsevier.com/gej-ng/31/29/23/141/48/show/Products/notes/index.htt#004} } @ARTICLE{journals/jpdc/DamaniWG03, TITLE = {Distributed recovery with {K} -optimistic logging}, AUTHOR = {Om P. Damani and Yi-Min Wang and Vijay K. Garg}, JOURNAL = {J. Parallel Distrib. Comput}, YEAR = {2003}, NUMBER = {12}, VOLUME = {63}, BIBDATE = {2004-01-15}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/jpdc/jpdc63.html#DamaniWG03}, PAGES = {1193--1218}, URL = {http://dx.doi.org/10.1016/j.jpdc.2003.07.003} } @MISC{oai:CiteSeerPSU:675978, TITLE = {Predicate Control: Synchronization in Distributed}, AUTHOR = {Ashis Tarafdar and Vijay K. Garg}, YEAR = {2003}, MONTH = OCT # {~09}, ABSTRACT = {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 exclusion, readers writers, and dining philosophers, predicate control assumes a look-ahead, so that the computation is an o#-line rather than an on-line input. Predicate control is targeted towards applications such as rollback recovery, debugging, and optimistic computing, in which such computation look-ahead is natural.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:150856; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:433123; oai:CiteSeerPSU:147576; oai:CiteSeerPSU:48319; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:451880; oai:CiteSeerPSU:79749; oai:CiteSeerPSU:148916; oai:CiteSeerPSU:148916; oai:CiteSeerPSU:39645; oai:CiteSeerPSU:319202; oai:CiteSeerPSU:448922; oai:CiteSeerPSU:142554}, ANNOTE = {Ashis Tarafdar (Akamai Technologies , Inc . + Dept . of Electrical and Computer Engg.; 8 Cambridge Center University of Texas at Austin; Cambridge , MA 02142 Austin , TX 78712); Vijay K. Garg (Akamai Technologies , Inc . + Dept . of Electrical and Computer Engg.; 8 Cambridge Center University of Texas at Austin; Cambridge , MA 02142 Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:675978}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/675978.html; http://www.ece.utexas.edu/%7Egarg/dist/jpdc03-ashis.ps} } @MISC{oai:CiteSeerPSU:656367, TITLE = {Applications of Lattice Theory to Distributed}, AUTHOR = {Vijay K. Garg and Neeraj Mittal and Alper Sen}, YEAR = {2003}, MONTH = JUL # {~28}, ABSTRACT = {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., determining whether there exists a consistent cut of the computation satisfying the given predicate. The second problem involves computing the slice of a computation with respect to a predicate. A slice is a concise representation of all those global states of the computation that satisfy the given predicate. The third problem we consider is that of analyzing a partial order trace of a distributed program to determine whether it satis es the given temporal logic formula.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:160542; oai:CiteSeerPSU:563530; oai:CiteSeerPSU:419813; oai:CiteSeerPSU:444044; oai:CiteSeerPSU:503358; oai:CiteSeerPSU:453289; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:451880; oai:CiteSeerPSU:491537; oai:CiteSeerPSU:624514; oai:CiteSeerPSU:448922}, ANNOTE = {Vijay K. Garg (ECE Department; University of Texas); Neeraj Mittal (CS Department; University of Texas , Dallas; Richardson , TX , USA); Alper Sen (ECE Department; University of Texas);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:656367}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/656367.html}, PS = {http://www.ece.utexas.edu/%7Egarg/dist/sigact03.ps} } @MISC{oai:CiteSeerPSU:669327, TITLE = {Enumerating Global States of a Distributed Computation}, AUTHOR = {Vijay K. Garg}, YEAR = {2003}, MONTH = SEP # {~15}, ABSTRACT = {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 computation to determine if any consistent global state satisfies the given predicate. We give an efficient algorithm that perform the lex traversal of the lattice. We also give a space efficient algorithm for the breadth-first-search (BFS) traversal.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:160542; oai:CiteSeerPSU:451158; oai:CiteSeerPSU:563530; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:436542}, ANNOTE = {Vijay K. Garg (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , TX 78712-1084 , USA);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:669327}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/669327.html; http://www.ece.utexas.edu/%7Egarg/dist/pdcs03.ps} } @MISC{oai:CiteSeerPSU:584636, TITLE = {An Efficient Deterministic Algorithm for the}, AUTHOR = {Vijay K. Garg and Adnan Aziz}, YEAR = {2003}, MONTH = MAY # {~21}, ABSTRACT = {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 for RDP are slow or have high communication cost. Harchol et al. [3] recently presented name-dropper, a randomized distributed algorithm for RDP which has low time and communication complexity. However, name-dropper has significant limitations --- (1.) the use of randomization precludes it from providing a guaranteed bound on runtime, and, more significantly, (2.) it has no mechanism by which convergence can be detected; in order to provide a high probability of convergence, the number of machines on the network must be known a priori to all machines. We present fast-leader, a deterministic distributed algorithm for RDP which overcomes these limitations while matching name-dropper's time and communication costs.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:38148; oai:CiteSeerPSU:291592; oai:CiteSeerPSU:32756; oai:CiteSeerPSU:53634}, ANNOTE = {Vijay K. Garg (Electrical and Computer Engineering; The University of Texas at Austin); Adnan Aziz (Electrical and Computer Engineering; The University of Texas at Austin);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:584636}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/584636.html; http://www.ece.utexas.edu/~garg/dist/resource-discovery.ps} } @INPROCEEDINGS{conf/fsttcs/Garg02, TITLE = {Algorithmic Combinatorics Based on Slicing Posets}, AUTHOR = {Vijay K. Garg}, BIBDATE = {2003-01-06}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/fsttcs/fsttcs2002.html#Garg02}, BOOKTITLE = {FSTTCS}, BOOKTITLE = {{FST} {TCS} 2002: Foundations of Software Technology and Theoretical Computer Science, 22nd Conference Kanpur, India, December 12-14, 2002, Proceedings}, PUBLISHER = {Springer}, YEAR = {2002}, VOLUME = {2556}, EDITOR = {Manindra Agrawal and Anil Seth}, ISBN = {3-540-00225-1}, PAGES = {169--181}, SERIES = {Lecture Notes in Computer Science}, URL = {http://link.springer.de/link/service/series/0558/bibs/2556/25560169.htm} } @INPROCEEDINGS{conf/ipps/SenG02, TITLE = {Detecting Temporal Logic Predicates on the Happened-Before Model}, AUTHOR = {Alper Sen and Vijay K. Garg}, PUBLISHER = {IEEE Computer Society}, YEAR = {2002}, BIBDATE = {2002-10-25}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/ipps/ipdps2002.html#SenG02}, BOOKTITLE = {IPDPS}, ISBN = {0-7695-1573-8}, URL = {http://computer.org/proceedings/ipdps/1573/symposium/15730076abs.htm} } @INPROCEEDINGS{conf/icdcs/GargS02, TITLE = {Timestamping Messages in Synchronous Computations}, AUTHOR = {Vijay K. Garg and Chakarat Skawratananond}, YEAR = {2002}, BIBDATE = {2002-07-31}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/icdcs/icdcs2002.html#GargS02}, BOOKTITLE = {ICDCS}, PAGES = {552}, URL = {http://computer.org/proceedings/icdcs/1585/15850552abs.htm} } @MISC{oai:CiteSeerPSU:560106, TITLE = {A Quorum-based Distributed Channel Allocation Algorithm for Mobile Systems}, AUTHOR = {Chakarat Skawratananond and Vijay K. Garg}, YEAR = {2002}, MONTH = MAR # {~03}, 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 channels among cells in distributed fashion. In update-based algorithms, each cell maintains its local knowledge about channels available for its use by exchanging messages among cells in its interference neighborhood. The existing update algorithms suffer from high message complexity or high storage overhead. In this paper, we present a distributed update-based algorithm that imposes lower message complexity, while requiring smaller storage overhead than existing algorithms.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:95107; oai:CiteSeerPSU:316503; oai:CiteSeerPSU:346830; oai:CiteSeerPSU:430892; oai:CiteSeerPSU:370176}, ANNOTE = {Chakarat Skawratananond (Parallel and Distributed Systems Laboratory; Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , Texas 78712); Vijay K. Garg (Parallel and Distributed Systems Laboratory; Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:560106}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/560106.html; http://www.ece.utexas.edu/~garg/dist/pimrc99.ps} } @MISC{oai:CiteSeerPSU:626204, TITLE = {Vijay. {K}. Garg Craig. Chase {J}. Roger Mitchell Richard Kilgore}, AUTHOR = {J. Roger and Mitchell Richard Kilgore and Vijay K. Garg and Craig Chase and J. Roger Mitchell and Richard Kilgore}, YEAR = {2002}, MONTH = JAN # {~23}, ABSTRACT = {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 as a boolean formula of local predicates. Many properties in distributed systems, however, use the state of channels. In this paper, we introduce the concept of a channel predicate and provide an efficient algorithm to detect any boolean formula of local and channel predicates.}, ANNOTE = {Mitchell Richard Kilgore (TEXAS); Vijay K. Garg (Parallel and Distributed Systems Laboratory; Austin , Texas 78712); Richard Kilgore (Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:626204}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/626204.html; http://www.ece.utexas.edu/~garg/dist/hicss95.ps} } @MISC{oai:CiteSeerPSU:563967, TITLE = {Vijay {K}. Garg, {J}. Roger Mitchell}, AUTHOR = {Vijay K. Garg and J. Roger Mitchell}, YEAR = {2002}, MONTH = JAN # {~23}, ABSTRACT = {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 asynchronous system, or their exact guarantees have not been discussed. We introduce a failure detector called infinitely often accurate failure detector which can be implemented in an asynchronous system. We provide one such implementation and show its application to the fault-tolerant server maintenance problem. We also show that some natural timeout based failure detectors implemented on Unix are not sufficient to guarantee infinitely often accuracy.}, ANNOTE = {Vijay K. Garg (Parallel and Distributed Systems Laboratory; Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , TX 78712); J. Roger Mitchell (Parallel and Distributed Systems Laboratory; Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:563967}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/563967.html; http://www.ece.utexas.edu/~garg/dist/fsttcs98.ps} } @MISC{oai:CiteSeerPSU:560978, TITLE = {Optimistic Distributed Simulation Based on Transitive Dependency}, AUTHOR = {Om P. Damani and Yi-min Wang and Vijay K. Garg}, YEAR = {2002}, MONTH = JAN # {~24}, ABSTRACT = {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 out more anti-messages. So a single straggler may result in a large number of anti-messages and multiple rollbacks of some LPs. In our protocol, an LP receiving a straggler broadcasts its rollback. On receiving this announcement, other LPs may roll back but they do not announce their rollbacks. So each LP rolls back at most once in response to each straggler. Antimessages are not used. This eliminates the need for output queues and results in simple memory management. It also eliminates the problem of cascading rollbacks and echoing, and results in faster simulation. All this is achieved by a scheme for maintaining transitive dependency information. The cost incurred includes the tagging of each message with extra dependency information and the increased processing time upon receiving a message. We also present the similarities between the two areas of distributed simulation and distributed recovery. We show how the solutions for one area can be applied to the other area.}, ANNOTE = {Om P. Damani (Dept . of Computer Sci . ATT Labs-Research Dept . of Elect . Comp . Eng; Uni . of Texas at Austin Murray Hill , NJ Uni . of Texas at Austin); Yi-min Wang (Dept . of Computer Sci . ATT Labs-Research Dept . of Elect . Comp . Eng; Uni . of Texas at Austin Murray Hill , NJ Uni . of Texas at Austin); Vijay K. Garg (Dept . of Computer Sci . ATT Labs-Research Dept . of Elect . Comp . Eng; Uni . of Texas at Austin Murray Hill , NJ Uni . of Texas at Austin);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:560978}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/560978.html; http://www.ece.utexas.edu/~garg/dist/pads97.ps} } @MISC{oai:CiteSeerPSU:567267, TITLE = {Causality for Time:}, AUTHOR = {Vijay K. Garg and Alexander I. Tomlinson}, YEAR = {2002}, MONTH = JAN # {~24}, ABSTRACT = {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. All properties are proven using induction on the happenedbefore relation and its complement. We illustrate our technique by providing a formal proof of Lamport's algorithm for mutual exclusion.}, ANNOTE = {Vijay K. Garg (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712-1084); Alexander I. Tomlinson (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:567267}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/567267.html; http://www.ece.utexas.edu/~garg/dist/spdp94.ps} } @MISC{oai:CiteSeerPSU:570305, TITLE = {Using the Causal Domain to Specify and Verify}, AUTHOR = {Vijay K. Garg and Alexander I. Tomlinson}, YEAR = {2002}, MONTH = JUN # {~21}, ABSTRACT = {A system for specification and proof of distributed programs is presented. The method is based directly on the partial order of local states (poset) and avoids the notions of time and simultaneity. Programs are specified by documenting the relationship between local states which are adjacent to each other in the poset. Program properties are defined by stating properties of the poset. Many program properties can be expressed succinctly and elegantly using this method because poset properties inherently account for varying processor execution speeds. The system utilizes a proof technique which uses induction on the complement of the causally precedes relation and is shown to be useful in proving poset properties. We demonstrate the system on three example algorithms: vector clocks, mutual exclusion, and direct dependency clocks.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:564740; oai:CiteSeerPSU:18867; oai:CiteSeerPSU:147576; oai:CiteSeerPSU:145873}, ANNOTE = {Vijay K. Garg (Parallel and Distributed Systems Laboratory; Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , TX 78712); Alexander I. Tomlinson (Parallel and Distributed Systems Laboratory; Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:570305}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/570305.html; http://www.ece.utexas.edu/~garg/dist/acta97.ps} } @MISC{oai:CiteSeerPSU:570319, TITLE = {Expressing and Detecting General Control Flow}, AUTHOR = {Vijay K Garg and Eddy Fromentin and Alex Tomlinson and Michel Raynal}, YEAR = {2002}, MONTH = JUN # {~20}, ABSTRACT = {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 expressing general properties on control flows, seen as sequences of local states. Among other properties, we can express invariance, sequential properties (to satisfy such a property a control flow must match a pattern described as a word on some alphabet) and non-sequential properties (these properties are on several control flows at the same time).}, CITESEER-REFERENCES = {oai:CiteSeerPSU:150856; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:36395; oai:CiteSeerPSU:70961; oai:CiteSeerPSU:316657; oai:CiteSeerPSU:158563; oai:CiteSeerPSU:35789}, ANNOTE = {Vijay K Garg (Dept . of ECE IRISA; University of Texas at Austin Campus de Beaulieu; Austin , TX 35042 RENNES cedex -- FRANCE); Eddy Fromentin (Dept . of ECE IRISA; University of Texas at Austin Campus de Beaulieu; Austin , TX 35042 RENNES cedex -- FRANCE); Alex Tomlinson (Dept . of ECE IRISA; University of Texas at Austin Campus de Beaulieu; Austin , TX 35042 RENNES cedex -- FRANCE); Michel Raynal (Dept . of ECE IRISA; University of Texas at Austin Campus de Beaulieu; Austin , TX 35042 RENNES cedex -- FRANCE);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:570319}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/570319.html; http://www.ece.utexas.edu/~garg/dist/spdp95.ps} } @MISC{oai:CiteSeerPSU:572182, TITLE = {Detection of Global Predicates: Techniques and}, AUTHOR = {Craig M. Chase and Vijay K. Garg}, YEAR = {2002}, MONTH = JUN # {~20}, ABSTRACT = {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 predicates, observer-independent predicates, and conjunctive predicates. We introduce a class of predicates, semi-linear predicates, which properly contains all of the above classes.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:6613; oai:CiteSeerPSU:125627; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:36395; oai:CiteSeerPSU:570176; oai:CiteSeerPSU:18867; oai:CiteSeerPSU:70961; oai:CiteSeerPSU:436542; oai:CiteSeerPSU:1861; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:158563; oai:CiteSeerPSU:28082}, ANNOTE = {Craig M. Chase (Parallel and Distributed Systems Laboratory); Vijay K. Garg (Parallel and Distributed Systems Laboratory);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:572182}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/572182.html; http://www.ece.utexas.edu/~garg/dist/dc98.ps} } @MISC{oai:CiteSeerPSU:567662, TITLE = {Detecting Conjunctions of Global Predicates}, AUTHOR = {Vijay K. Garg and J. Roger Mitchell}, YEAR = {2002}, MONTH = JUN # {~20}, ABSTRACT = {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 is significantly more efficient than the previous algorithms by Cooper and Marzullo, and by Stoller and Schneider.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:146479; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:28082}, ANNOTE = {Vijay K. Garg (Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , TX 78712); J. Roger Mitchell (Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:567662}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/567662.html; http://www.ece.utexas.edu/~garg/dist/ipl97.ps} } @MISC{oai:CiteSeerPSU:575511, TITLE = {Timestamping Messages in Synchronous Computations}, AUTHOR = {Vijay K. Garg}, YEAR = {2002}, MONTH = FEB # {~11}, ABSTRACT = {computations is a fundamental problem with applications in distributed monitoring systems and faulttolerance. Fidge and Mattern's vector clocks capture the order relationship with vectors of size N in a system with N processes. Since many distributed applications use synchronous messages, it is natural to ask if the overhead can be reduced for these applications. In this 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. Our method is fundamentally different from that of Fidge and Mattern's technique. The timestamps in our method do not use one component per process but still guarantee that the order relationship is captured accurately. Our algorithm is online and only requires piggybacking of timestamps on program messages. It is applicable to all programs that either use programming languages which use synchronous communication such as CSP, or use synchronous remote procedure calls.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:9605; oai:CiteSeerPSU:1538; oai:CiteSeerPSU:444044; oai:CiteSeerPSU:18867; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:573685}, ANNOTE = {Vijay K. Garg (Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:575511}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/575511.html; http://www.ece.utexas.edu/~garg/dist/dcs02.ps} } @INPROCEEDINGS{conf/icdcs/GargM01, TITLE = {On Slicing a Distributed Computation}, AUTHOR = {Vijay K. Garg and Neeraj Mittal}, YEAR = {2001}, BIBDATE = {2003-03-26}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/icdcs/icdcs2001.html#GargM01}, BOOKTITLE = {ICDCS}, PAGES = {322--329}, URL = {http://www.computer.org/proceedings/icdcs/1077/10770322abs.htm} } @INPROCEEDINGS{conf/podc/GargS01, TITLE = {String realizers of posets with applications to distributed computing}, AUTHOR = {Vijay K. Garg and Chakarat Skawratananond}, YEAR = {2001}, BIBDATE = {2002-12-04}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/podc/podc2001.html#GargS01}, BOOKTITLE = {PODC}, PAGES = {72--80}, URL = {http://doi.acm.org/10.1145/383962.383988} } @INPROCEEDINGS{conf/icdcs/MittalG01, TITLE = {On Detecting Global Predicates in Distributed Computations}, AUTHOR = {Neeraj Mittal and Vijay K. Garg}, YEAR = {2001}, BIBDATE = {2002-08-29}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/icdcs/icdcs2001.html#MittalG01}, BOOKTITLE = {ICDCS}, PAGES = {3--10}, URL = {http://www.computer.org/proceedings/icdcs/1077/10770003abs.htm} } @INPROCEEDINGS{conf/wdag/MittalG01, TITLE = {Computation Slicing: Techniques and Theory}, AUTHOR = {Neeraj Mittal and Vijay K. Garg}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/wdag/disc2001.html#MittalG01}, BOOKTITLE = {DISC}, BOOKTITLE = {Distributed Computing, 15th International Conference, {DISC} 2001, Lisbon, Portugal, October 3-5, 2001, Proceedings}, PUBLISHER = {Springer}, YEAR = {2001}, VOLUME = {2180}, EDITOR = {Jennifer L. Welch}, ISBN = {3-540-42605-1}, PAGES = {78--92}, SERIES = {Lecture Notes in Computer Science}, URL = {http://link.springer.de/link/service/series/0558/bibs/2180/21800078.htm} } @INPROCEEDINGS{PODC00*239, AUTHOR = {Neeraj Mittal and Vijay K. Garg}, TITLE = {Debugging Distributed Programs Using Controlled Re-execution}, PAGES = {239--248}, BOOKTITLE = {Proceedings of the 19th Annual {ACM} Symposium on Principles of Distributed Computing ({PODC}-00)}, MONTH = JUL # { ~16--19}, PUBLISHER = {ACM Press}, ADDRESS = {NY}, YEAR = {2000} } @MISC{oai:CiteSeerPSU:649589, TITLE = {A Max-Plus Algebra of Signals for the Supervisory}, AUTHOR = {Guillaume Brat and Vijay K. Garg}, YEAR = {2000}, MONTH = MAY # {~05}, ABSTRACT = {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 sequences for which we can compute finite representations called signals. This framework allows us to implement a max-plus algebra for computing supremal controllers for real-time, discrete event systems.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:13348}, ANNOTE = {Guillaume Brat (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , TX 78712 , USA); Vijay K. Garg (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , TX 78712 , USA);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:649589}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/649589.html; http://ase.arc.nasa.gov/docs/../people/brat/incom98.ps.gz} } @MISC{oai:CiteSeerPSU:635505, TITLE = {A (max,+) Algebra For Non-Stationary Periodic Timed Discrete Event Systems}, AUTHOR = {Guillaume P. Brat and Vijay K. Garg}, YEAR = {2000}, MONTH = MAY # {~05}, ABSTRACT = {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 its events. Each sequence has a finite representations called a signal. The resulting tool can also compute supremal controllers for timed discrete event systems.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:13348}, ANNOTE = {Guillaume P. Brat (Department of Electrical and Computer Engineering , The University of Texas at Austin; Austin , Texas 78712); Vijay K. Garg (Department of Electrical and Computer Engineering , The University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:635505}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/635505.html; http://ase.arc.nasa.gov/docs/../people/brat/wodes98.ps.gz} } @INPROCEEDINGS{conf/wdag/TarafdarG99, TITLE = {Software Fault Tolerance of Concurrent Programs Using Controlled Re-execution}, AUTHOR = {Ashis Tarafdar and Vijay K. Garg}, BIBDATE = {2003-06-05}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/wdag/disc99.html#TarafdarG99}, BOOKTITLE = {DISC}, BOOKTITLE = {Distributed Computing, 13th International Symposium, Bratislava, Slavak Republic, September 27-29, 1999, Proceedings}, PUBLISHER = {Springer}, YEAR = {1999}, VOLUME = {1693}, EDITOR = {Prasad Jayanti}, ISBN = {3-540-66531-5}, PAGES = {210--224}, SERIES = {Lecture Notes in Computer Science}, URL = {http://link.springer.de/link/service/series/0558/bibs/1693/16930210.htm} } @INPROCEEDINGS{conf/srds/DamaniTG99, TITLE = {Optimistic Recovery in Multi-threaded Distributed Systems}, AUTHOR = {Om P. Damani and Ashis Tarafdar and Vijay K. Garg}, YEAR = {1999}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/srds/srds99.html#DamaniTG99}, BOOKTITLE = {Symposium on Reliable Distributed Systems}, PAGES = {234--243}, URL = {http://computer.org/proceedings/srds/0290/02900234abs.htm} } @ARTICLE{journals/ppl/GargR99, TITLE = {Normality: {A} Consistency Condition for Concurrent Objects}, AUTHOR = {Vijay K. Garg and Michel Raynal}, JOURNAL = {Parallel Processing Letters}, YEAR = {1999}, NUMBER = {1}, VOLUME = {9}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/ppl/ppl9.html#GargR99}, PAGES = {123--134} } @BOOK{KumGar:95, AUTHOR = {R. Kumar and V. K. Garg}, TITLE = {Modeling and Control of Logical Discrete Event Systems}, PUBLISHER = {Kluwer Academic Publishers}, ADDRESS = {Norwell, MA, USA}, YEAR = {1999} } @MISC{oai:CiteSeerPSU:250491, TITLE = {An Algebra for Probabilistic Processes}, AUTHOR = {Vijay K. Garg}, YEAR = {1999}, MONTH = FEB # {~12}, ABSTRACT = {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 an algebra of p-languages. We show that this set is a complete partial order and our operators are continuous in it. Hence, recursive equations may be defined in this algebra using fixpoints of continuous functions. Thus, p-languages form a suitable theoretical foundation for specifying and analyzing probabilistic systems. The model can easily be extended for performance analysis by associating timing information with each event. We define many performance indices for systems expressed using this model and derive techniques to compute them. 1 Introduction The theory for supervisory control of discrete event dynamical systems has been an active area of research since its initiation by Ramadge and Wonham [21, 22, 20]. Most research in this area has used theory of deterministic formal languag...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:94231; oai:CiteSeerPSU:46168; oai:CiteSeerPSU:572604; oai:CiteSeerPSU:107182}, ANNOTE = {Vijay K. Garg (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:250491}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/250491.html; http://www.ece.utexas.edu/~garg/des/cdc92.ps.Z} } @MISC{oai:CiteSeerPSU:254652, TITLE = {Modeling Stochastic Discrete Event Systems Using Probabilistic Languages}, AUTHOR = {Vijay K. Garg and Ratnesh Kumar and Steven I. Marcus}, YEAR = {1999}, MONTH = FEB # {~12}, ABSTRACT = {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 the set of traces of the system satisfying certain consistency constraints. Regular language operators such as choice, concatenation, and Kleene-closure have been defined in the setting of probabilistic languages to allow modeling of complex systems in terms of simpler ones. The set of probabilistic languages is closed under such operators thus forming an algebra. It also is a complete partial order under a natural ordering in which the operators are continuous. Hence recursive equations can be solved in this algebra. This is alternatively derived by using contraction mapping theorem on the set of probabilistic languages which is shown to be a complete metric space. The notion of regularity, i.e., finiteness of automata representation of probabilistic languages has been defined and shown that...}, ANNOTE = {Vijay K. Garg (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , Texas 78712-1084); Ratnesh Kumar (Department of Electrical Engineering; University of Kentucky; Lexington , KY 40506-0046); Steven I. Marcus (Department of Electrical Engineering and; Institute for Systems Research; University of Maryland at College Park; College Park , MD 20742);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:254652}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/254652.html; http://www.ece.utexas.edu/~garg/des/tac-prob.ps.Z} } @MISC{oai:CiteSeerPSU:430426, TITLE = {Yi-Min Wang Om {P}. Damani Vijay {K}. Garg}, AUTHOR = {Yi-min Wang and Om P. Damani and Vijay K. Garg}, YEAR = {1999}, MONTH = OCT # {~14}, ABSTRACT = {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 pessimistic logging because it allows fast and localized recovery. The price that they must pay, however, is the higher failure-free overhead. In this paper, we introduce the concept of K-optimistic logging where K is the degree of optimism that can be used to fine-tune the tradeoff between failure-free overhead and recovery efficiency. Traditional pessimistic logging and optimistic logging then become the two extremes in the entire spectrum spanned by K-optimistic logging. Our approach is to prove that only dependencies on those states that may be lost upon a failure need to be tracked on-line, and so transitive dependency tracking can be performed with a variable-size vector. The size of the vector piggybacked on a message then indicates the number of processes whose failures may revoke the me...}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:430426}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/430426.html; http://dcslab.snu.ac.kr/courses/dcs2/Papers/K-optimisticlogging.ps} } @MISC{oai:CiteSeerPSU:269182, TITLE = {Computation of State Avoidance Control for Infinite State Systems in Assignment Program Framework - The Expanded Version}, AUTHOR = {Ratnesh Kumar and Vijay K. Garg}, YEAR = {1999}, MONTH = DEC # {~03}, ABSTRACT = {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 allows a concise characterization of systems with infinitely many states, and secondly, state variable specification allows characterization of qualitative properties of general nondeterministic systems. An assignment program consisting of state variables and a finite set of conditional assignment statements is used for representing a discrete event system, and a set of forbidden states is used for representing a control specification. Although the state avoidance control of infinite state systems has been studied in literature, there is little work on computation of supervisors for general infinite state systems (except for certain classes of Petri nets). This is not unexpected since as we show, the control synthesis problem is undecidable in general. The contribution of this paper is to s...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:51811; oai:CiteSeerPSU:282018; oai:CiteSeerPSU:269737; oai:CiteSeerPSU:289347; oai:CiteSeerPSU:273949; oai:CiteSeerPSU:106220; oai:CiteSeerPSU:47855}, ANNOTE = {Ratnesh Kumar (Department of Electrical Engineering; University of Kentucky; Lexington , KY 40506-0046); Vijay K. Garg (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:269182}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/269182.html; http://www.engr.uky.edu/~kumar/PUBS/cstmttech.ps} } @MISC{oai:CiteSeerPSU:270753, TITLE = {Corrections to {} } @MISC{oai:CiteSeerPSU:268362, TITLE = {Computation of State Avoidance Control for Infinite State Systems in Assignment Program Framework}, AUTHOR = {Ratnesh Kumar and Vijay K. Garg}, YEAR = {1999}, MONTH = DEC # {~03}, ABSTRACT = {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 allows a concise characterization of systems with infinitely many states, and secondly, state variable specification allows characterization of qualitative properties of general nondeterministic systems. An assignment program consisting of state variables and a finite set of conditional assignment statements is used for representing a discrete event system, and a set of forbidden states is used for representing a control specification. Although the state avoidance control of infinite state systems has been studied in literature, there is little work on computation of supervisors for general infinite state systems (except for certain classes of Petri nets). The contribution of this paper is to show that the supervisory control problem in such settings reduces to that of solving arith...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:51811; oai:CiteSeerPSU:282018; oai:CiteSeerPSU:269737; oai:CiteSeerPSU:273949; oai:CiteSeerPSU:106220; oai:CiteSeerPSU:47855}, ANNOTE = {Ratnesh Kumar (Department of Electrical Engineering; University of Kentucky; Lexington , KY 40506-0046); Vijay K. Garg (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:268362}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/268362.html; http://www.engr.uky.edu/~kumar/PUBS/cstmttn.ps} } @INPROCEEDINGS{SRDS98*3, AUTHOR = {J. R. Mitchell and V. K. Garg}, TITLE = {A Non-Blocking Recovery Algorithm for Causal Message Logging}, PAGES = {3--9}, BOOKTITLE = {Seventeenth {IEEE} Symposium on Reliable Distributed Systems ({SRDS} '98)}, ISBN = {0-8186-9218-9}, MONTH = OCT, PUBLISHER = {IEEE}, ADDRESS = {Washington - Brussels - Tokyo}, YEAR = {1998} } @INPROCEEDINGS{PADS98*38, AUTHOR = {O. P. Damani and V. K. Garg}, TITLE = {Fault-Tolerant Distributed Simulation}, PAGES = {38--45}, ISBN = {0-8186-8457-7}, BOOKTITLE = {Proceedings of the 12th Workshop on Parallel and Distributed Simulation ({PADS}-98)}, MONTH = MAY # {~26--29}, PUBLISHER = {IEEE Computer Society}, ADDRESS = {Los Alamitos}, YEAR = {1998} } @INPROCEEDINGS{conf/rtss/BratG98, TITLE = {Analyzing Non-Deterministic Real-Time Systems with (max, +) Algebra}, AUTHOR = {Guillaume P. Brat and Vijay K. Garg}, YEAR = {1998}, BIBDATE = {2003-09-15}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/rtss/rtss1998.html#BratG98}, BOOKTITLE = {IEEE Real-Time Systems Symposium}, PAGES = {210--219}, URL = {http://dlib.computer.org/conferen/rtss/9212/pdf/92120210.pdf} } @INPROCEEDINGS{conf/ipps/TarafdarG98, TITLE = {Predicate Control for Active Debugging of Distributed Programs}, AUTHOR = {Ashis Tarafdar and Vijay K. Garg}, YEAR = {1998}, BIBDATE = {2003-07-29}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/ipps/ipps1998.html#TarafdarG98}, BOOKTITLE = {IPPS/SPDP}, PAGES = {763--769}, URL = {http://csdl.computer.org/dl/proceedings/ipps/1998/8403/00/84030763.pdf} } @INPROCEEDINGS{conf/fsttcs/GargM98, TITLE = {Implementable Failure Detectors in Asynchronous Systems}, AUTHOR = {Vijay K. Garg and J. Roger Mitchell}, BIBDATE = {2002-06-17}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/fsttcs/fsttcs98.html#GargM98}, BOOKTITLE = {FSTTCS}, BOOKTITLE = {Foundations of Software Technology and Theoretical Computer Science, 18th Conference, Chennai, India, December 17-19, 1998, Proceedings}, PUBLISHER = {Springer}, YEAR = {1998}, VOLUME = {1530}, EDITOR = {Vikraman Arvind and R. Ramanujam}, ISBN = {3-540-65384-8}, PAGES = {158--169}, SERIES = {Lecture Notes in Computer Science} } @INPROCEEDINGS{conf/icdcs/TarafdarG98, TITLE = {Addressing False Causality while Detecting Predicates in Distributed Programs}, AUTHOR = {Ashis Tarafdar and Vijay K. Garg}, YEAR = {1998}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/icdcs/icdcs98.html#TarafdarG98}, BOOKTITLE = {ICDCS}, PAGES = {94--101}, URL = {http://dlib.computer.org/conferen/icdcs/8292/pdf/82920094.pdf} } @INPROCEEDINGS{conf/icdcs/MittalG98, TITLE = {Consistency Conditions for Multi-Object Distributed Operations}, AUTHOR = {Neeraj Mittal and Vijay K. Garg}, YEAR = {1998}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/icdcs/icdcs98.html#MittalG98}, BOOKTITLE = {ICDCS}, PAGES = {582--599}, URL = {http://dlib.computer.org/conferen/icdcs/8292/pdf/82920582.pdf} } @INPROCEEDINGS{conf/icdcs/GargM98, TITLE = {Distributed Predicate Detection in a Faulty Environment}, AUTHOR = {Vijay K. Garg and J. Roger Mitchell}, YEAR = {1998}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/icdcs/icdcs98.html#GargM98}, BOOKTITLE = {ICDCS}, PAGES = {416--423}, URL = {http://dlib.computer.org/conferen/icdcs/8292/pdf/82920416.pdf} } @ARTICLE{journals/dc/ChaseG98, TITLE = {Detection of Global Predicates: Techniques and Their Limitations}, AUTHOR = {Craig M. Chase and Vijay K. Garg}, JOURNAL = {Distributed Computing}, YEAR = {1998}, NUMBER = {4}, VOLUME = {11}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/dc/dc11.html#ChaseG98}, PAGES = {191--201}, URL = {http://link.springer.de/link/service/journals/00446/bibs/8011004/80110191.htm} } @MISC{oai:CiteSeerPSU:97383, TITLE = {Control of Event Separation Times in Discrete Event Systems}, AUTHOR = {Darren D. Cofer and Vijay K. Garg}, YEAR = {1998}, MONTH = JUL # {~06}, ABSTRACT = {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 for these timed DES can be addressed using methods similar to those developed for their untimed counterparts. When the desired behavior takes the form of minimum separation times between events, it also can be expressed as a timed event graph. Supervised behavior is then defined by the synchronous operation of the plant and specification automata. Controllability and the existence of optimal behaviors can be evaluated in this framework. 1. Introduction Discrete event systems (DES) which are subject to synchronization constraints in time can be modelled by automata known as timed event graphs [2]. A timed event graph (TEG) is a Petri net in which a delay or processing time is associated with each place and such that forks and joins occur only at its transitions. Each transition in the graph ...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:74476; oai:CiteSeerPSU:13348}, ANNOTE = {Darren D. Cofer (Honeywell Technology Center; 3660 Techology Dr.; Minneapolis , MN 55418); Vijay K. Garg (Dept . of Elec . and Comp . Engineering; University of Texas at Austin; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:97383}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/97383.html; http://www.ece.utexas.edu/~garg/des/cdc95.ps.Z} } @MISC{oai:CiteSeerPSU:392766, TITLE = {A Lightweight Algorithm for Causal Message Ordering in Mobile Computing Systems}, AUTHOR = {Chakarat Skawratananond and Neeraj Mittal and Vijay K. Garg}, YEAR = {1998}, MONTH = JAN # {~24}, ABSTRACT = {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 this paper, we present an efficient protocol for causal ordering in mobile computing systems. This protocol requires minimal resources on mobile hosts and wireless links. The proposed protocol is scalable and can easily handle dynamic change in the number of participating mobile hosts in the system. Our protocol, when compared to previous proposals, offers a low unnecessary delay, low message overhead and optimized handoff cost. 1 Introduction The emergence of mobile computing devices, such as notebook computers and personal digital assistants with communication capabilities, has had a significant impact on distributed computing. These devices provide users the freedom to move anywhere under the service area while retaining network connection. However, mobile computing devices have limite...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:133158; oai:CiteSeerPSU:150856; oai:CiteSeerPSU:371107; oai:CiteSeerPSU:63501; oai:CiteSeerPSU:307654; oai:CiteSeerPSU:304613; oai:CiteSeerPSU:566025}, ANNOTE = {Chakarat Skawratananond (Electrical and Computer Engineering Dept . *Computer Science Dept.; The University of Texas at Austin The University of Texas at Austin; Austin , TX 78712 Austin , TX 78712); Neeraj Mittal (Electrical and Computer Engineering Dept . *Computer Science Dept.; The University of Texas at Austin The University of Texas at Austin; Austin , TX 78712 Austin , TX 78712); Vijay K. Garg (Electrical and Computer Engineering Dept . *Computer Science Dept.; The University of Texas at Austin The University of Texas at Austin; Austin , TX 78712 Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:392766}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/392766.html; http://www.cs.utexas.edu/users/neerajm/publications/3/pdcs99.ps.gz} } @MISC{oai:CiteSeerPSU:400437, TITLE = {Parallel Distributed Systems group}, AUTHOR = {Neeraj Mittal and Vijay K. Garg}, YEAR = {1998}, MONTH = JAN # {~24}, ABSTRACT = {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. 1 Introduction Applications such as distributed file systems, transaction systems and cache coherence for multiprocessors require concurrent accesses to shared data. The underlying system must provide certain guarantees about the values returned by data accesses, possibly to distinct copies of a single logical data object. A consistency condition specifies what guarantees are provided by the system. The consistency co...}, ANNOTE = {Neeraj Mittal (Department of Electrical Computer Engineering; University of Texas at Austin; Austin , Texas 78712); Vijay K. Garg (Department of Electrical Computer Engineering; University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:400437}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/400437.html; http://www.cs.utexas.edu/users/neerajm/publications/1/TR-PDS-1998-005.ps.gz} } @MISC{oai:CiteSeerPSU:573151, TITLE = {Debugging in a Distributed World: Observation and Control}, AUTHOR = {Ashis Tarafdar and Vijay K. Garg}, YEAR = {1998}, MONTH = JUN # {~15}, ABSTRACT = {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 controlling a distributed computation and its applications to distributed debugging. Observing distributed computations involves solving the predicate detection problem. We present the main ideas involved in developing efficient algorithms for predicate detection. Controlling distributed computations involves solving the predicate control problem. Predicate control may be used to restrict the behavior of the distributed program to suspicious executions. We also present an example of how predicate detection and predicate control can be used in practice to facilitate distributed debugging.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:150856; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:570176; oai:CiteSeerPSU:18867; oai:CiteSeerPSU:86181; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:562879; oai:CiteSeerPSU:216474; oai:CiteSeerPSU:319202}, ANNOTE = {Ashis Tarafdar (Department of Computer Sciences; The University of Texas at Austin; Austin , TX 78712-1188 , USA); Vijay K. Garg (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , TX 78712-1084 , USA);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:573151}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/573151.html; http://www.ece.utexas.edu/~garg/dist/asset98.ps} } @MISC{oai:CiteSeerPSU:448421, TITLE = {Happened Before is the Wrong Model for Potential Causality}, AUTHOR = {Ashis Tarafdar and Vijay K. Garg}, YEAR = {1998}, MONTH = JUN # {~15}, ABSTRACT = {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 computation. Though it is a good model for logical time, we argue that it is not a good model for potential causality. We introduce a better model for potential causality that extends happened before to allow independent local events to be partially ordered. This potential causality model has marked advantages over the happened before model in applications areas such as debugging and recovery. 1}, CITESEER-REFERENCES = {oai:CiteSeerPSU:53797; oai:CiteSeerPSU:553969; oai:CiteSeerPSU:5609; oai:CiteSeerPSU:18867; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:260722; oai:CiteSeerPSU:216474}, ANNOTE = {Ashis Tarafdar (Dept . of Computer Sciences Dept . of Electrical and Computer Engg.; University of Texas at Austin University of Texas at Austin; Austin , TX 78712 Austin , TX 78712); Vijay K. Garg (Dept . of Computer Sciences Dept . of Electrical and Computer Engg.; University of Texas at Austin University of Texas at Austin; Austin , TX 78712 Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:448421}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/448421.html; http://www.ece.utexas.edu/~garg/dist/TR0698.ps.Z} } @MISC{oai:CiteSeerPSU:249871, TITLE = {Control Of Stochastic Discrete Event Systems: Existence}, AUTHOR = {Ratnesh Kumar and Vijay K. Garg}, YEAR = {1998}, MONTH = FEB # {~12}, ABSTRACT = {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 framework for their supervisory control, where control is exercised by dynamically disabling certain controllable events. The control objective is to design a supervisor such that the controlled system never executes any illegal traces (their occurrence probability is zero), and legal traces occur with minimum prespecified occurrence probabilities. We provide a condition for the existence of a supervisor. We also present an algorithm to test this existence condition when the probabilistic languages are regular (so that they admit probabilistic automata representation with finitely many states). 1 Introduction The non-stochastic behavior of a discrete event system can be viewed as a binary valued map over the set of all possible sequences of events, called traces. (A trace is mapped to one if an...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:146338}, ANNOTE = {Ratnesh Kumar (Dept . of Elec . Eng . , Univ . of Kentucky , and Applied Research Lab . , Penn . State Univ.; Dept . of ECE , Univ . of Texas; Austin , TX); Vijay K. Garg (Dept . of Elec . Eng . , Univ . of Kentucky , and Applied Research Lab . , Penn . State Univ.; Dept . of ECE , Univ . of Texas; Austin , TX);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:249871}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/249871.html; http://www.ece.utexas.edu/~garg/des/wodes98.ps.Z} } @MISC{oai:CiteSeerPSU:252196, TITLE = {Control of Stochastic Discrete Event Systems: Synthesis}, AUTHOR = {Ratnesh Kumar and Vijay K. Garg}, YEAR = {1998}, MONTH = FEB # {~12}, ABSTRACT = {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 their supervisory control in [11], where control is exercised by dynamically disabling certain controllable events thereby nulling the occurrence probabilities of disabled events, and increasing the occurrence probabilities of enabled events proportionately. The control objective is to design a supervisor such that the controlled system never executes any illegal traces (their occurrence probability is zero), and legal traces occur with minimum prespecified occurrence probabilities. In other words, the probabilistic language of the controlled system lies within a prespecified range, where the upper bound is a {} } @ARTICLE{Aho97, AUTHOR = {Hannu Ahonen and Paulo A. {de Souza Jr.} and Vijayendra Kumar Garg}, TITLE = {A genetic algorithm for fitting Lorentzian line shapes in Mossbauer spectra}, JOURNAL = {Nuclear Instruments and Methods in Physics Research B}, YEAR = {1997}, VOLUME = {124}, PAGES = {633--638}, MONTH = {5 } # MAY, EMAIL = {souza@iacgu7.chemie.uni-mainz.de}, KEYWORDS = {genetic algorithms}, ISSN = {0168583X}, ABSTRACT = {A genetic algorithm was implemented for finding an approximative solution to the problem of fitting a combination of Lorentzian lines to a measured Mossbauer spectrum. This iterative algorithm exploits the idea of letting several solutions (individuals) compete with each other for the opportunity of being selected to create new solutions (reproduction). Each solution was represend as a string of binary digits (chromossome). In addition, the bits in the new solutions may be switched randomly from zero to one or conversely (mutation). The input of the program that implements the genetic algorithm consists of the measured spectrum, the maximum velocity, the peak positions and the expected number of Lorentzian lines in the spectrum. Each line is represented with the help of three variables, which correspond to its intensity, full line width at hald maxima and peak position. An additional parameter was associated to the background level in the spectrum. A chi-2 test was used for determining the quality of each parameter combination (fitness). The results obtained seem to be very promising and encourage to further development of the algorithm and its implementation.} } @ARTICLE{JPDC::TomlinsonG1997, TITLE = {Monitoring Functions on Global States of Distributed Programs}, AUTHOR = {Alexander I. Tomlinson and Vijay K. Garg}, PAGES = {173--189}, JOURNAL = {Journal of Parallel and Distributed Computing}, YEAR = {1997}, MONTH = {15~} # MAR, VOLUME = {41}, NUMBER = {2}, REFERENCES = {\cite{TCS::Bouge1987} \cite{ACMTCS::ChandyL1985} \cite{IPL::Garg1992}} } @ARTICLE{JPDC::GargCKM1997, TITLE = {Efficient Detection of Channel Predicates in Distributed Systems}, AUTHOR = {V. K. Garg and C. M. Chase and Richard Kilgore and J. Roger Mitchell}, PAGES = {134--147}, JOURNAL = {Journal of Parallel and Distributed Computing}, YEAR = {1997}, MONTH = {15~} # SEP, VOLUME = {45}, NUMBER = {2}, REFERENCES = {\cite{ACMTCS::ChandyL1985} \cite{IPL::dijkstraS1980} \cite{CACM::Fujimoto1990} \cite{CACM::Lamport1978} \cite{DC::SchwarzM1994}} } @ARTICLE{ACTAI::GargT1997, TITLE = {Using the Causal Domain to Specify and verify Distributed Programs}, AUTHOR = {Vijay K. Garg and Alexander I. Tomlinson}, JOURNAL = {Acta Informatica}, PAGES = {667--686}, YEAR = {1997}, VOLUME = {34}, NUMBER = {9} } @INPROCEEDINGS{PADS97*90, AUTHOR = {O. Damani and Y.-M. Wang and V. K Garg}, TITLE = {Optimistic Distributed Simulation Based on Transitive Dependency Tracking}, PAGES = {90--97}, ISBN = {0-8186-7964-6}, BOOKTITLE = {11th Workshop on Parallel and Distributed Simulation ({PADS}-97)}, MONTH = JUN # {~10--13}, PUBLISHER = {IEEE}, ADDRESS = {Los Alamitos, CA, USA}, YEAR = {1997} } @INPROCEEDINGS{conf/icdcs/MurtyG97, TITLE = {Characterization of Message Ordering Specifications and Protocols}, AUTHOR = {Venkatesh V. Murty and Vijay K. Garg}, YEAR = {1997}, BIBDATE = {2006-03-09}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/icdcs/icdcs97.html#MurtyG97}, BOOKTITLE = {ICDCS}, PAGES = {0} } @INPROCEEDINGS{conf/pdpta/MitchellG97, TITLE = {Optimistic agreement in distributed systems}, AUTHOR = {J. Roger Mitchell and Vijay K. Garg}, BIBDATE = {2004-04-20}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/pdpta/pdpta1997.html#MitchellG97}, BOOKTITLE = {PDPTA}, BOOKTITLE = {Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, {PDPTA} 1997, June 30 - July 3, 1997, Las Vegas, Nevada, {USA}}, PUBLISHER = {CSREA Press}, YEAR = {1997}, EDITOR = {Hamid R. Arabnia}, ISBN = {0-9648666-8-4}, PAGES = {885--889} } @INPROCEEDINGS{conf/aadebug/Garg97, TITLE = {Observation and Control for Debugging Distributed Computations}, AUTHOR = {Vijay K. Garg}, YEAR = {1997}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/aadebug/aadebug97.html#Garg97}, BOOKTITLE = {AADEBUG}, PAGES = {1--12}, URL = {http://www.ep.liu.se/ea/cis/1997/009/01/} } @MISC{oai:CiteSeerPSU:268041, TITLE = {Probabilistic Language Formalism for Stochastic Discrete Event Systems}, AUTHOR = {Vijay K. Garg and Ratnesh Kumar and Steven I. Marcus}, YEAR = {1997}, MONTH = DEC # {~03}, ABSTRACT = {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 the set of traces of the system satisfying certain consistency constraints. Regular language operators such as choice, concatenation, and Kleene-closure have been defined in the setting of probabilistic languages to allow modeling of complex systems in terms of simpler ones. The set of probabilistic languages is closed under such operators thus forming an algebra. It also is a complete partial order under a natural ordering in which the operators are continuous. Hence recursive equations can be solved in this algebra. This is alternatively derived by using contraction mapping theorem on the set of probabilistic languages which is shown to be a complete metric space. The notion of regularity, i.e., finiteness of automata representation of probabilistic languages has been defined and shown that...}, ANNOTE = {Vijay K. Garg (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , Texas 78712-1084); Ratnesh Kumar (Department of Electrical Engineering; University of Kentucky; Lexington , KY 40506-0046); Steven I. Marcus (Department of Electrical Engineering and; Institute for Systems Research; University of Maryland at College Park; College Park , MD 20742);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:268041}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/268041.html; http://www.engr.uky.edu/~kumar/PUBS/plang.ps} } @MISC{oai:CiteSeerPSU:49329, TITLE = {Distributed Recovery with}, AUTHOR = {Yi-min Wang and Om P. Damani and Vijay K. Garg}, YEAR = {1997}, MONTH = SEP # {~05}, ABSTRACT = {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 pessimistic logging because it allows fast and localized recovery. The price that they must pay, however, is the higher failure-free overhead. In this paper, we introduce the concept of K-optimistic logging where K is the degree of optimism that can be used to fine-tune the tradeoff between failure-free overhead and recovery efficiency. Traditional pessimistic logging and optimistic logging then become the two extremes in the entire spectrum spanned by K-optimistic logging. Our approach is to prove that only dependencies on those states that may be lost upon a failure need to be tracked on-line, and so transitive dependency tracking can be performed with a variable-size vector. The size of the vector piggybacked on a message then indicates the number of processes whose failures may revoke the me...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:9605; oai:CiteSeerPSU:553969; oai:CiteSeerPSU:44544; oai:CiteSeerPSU:49117; oai:CiteSeerPSU:118830; oai:CiteSeerPSU:1861; oai:CiteSeerPSU:499740; oai:CiteSeerPSU:25883}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:49329}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/49329.html; http://arirang.snu.ac.kr/~woojeong/fault_paper/ICDCS-1997.ps} } @TECHREPORT{oai:CiteSeerPSU:118660, TITLE = {A Quorum-based Distributed Channel Allocation Algorithm for Mobile Computing Systems}, AUTHOR = {Chakarat Skawratananond and Vijay K. Garg}, YEAR = {1997}, MONTH = MAY # {~02}, ABSTRACT = {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 channels among cells in distributed fashion. In update-based algorithms, each cell maintains its local knowledge about channels available for its use by exchanging messages among cells in its interference neighborhood. An advantage of the update approach is its low channel acquisition delay, which is defined as the time between the send event of channel requests and the moment that a channel is successfully acquired. However, the existing update algorithms suffer from high message complexity or high storage overhead. In this paper, we present a distributed update-based algorithm that imposes lower message complexity, while requiring smaller storage overhead than existing algorithms. Keywords Distributed channel allocation, mobile computing, distributed network algorithm. 1 Introduction The radi...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:95107; oai:CiteSeerPSU:316503; oai:CiteSeerPSU:346830; oai:CiteSeerPSU:430892; oai:CiteSeerPSU:159401; oai:CiteSeerPSU:370176}, ANNOTE = {Chakarat Skawratananond (Parallel Distributed Systems group; Department of Electrical Computer Engineering; University of Texas at Austin; Austin , Texas 78712); Vijay K. Garg (Parallel Distributed Systems group; Department of Electrical Computer Engineering; University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:118660}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/118660.html; http://maple.ece.utexas.edu/TechReports/1997/TR-PDS-1997-010.ps.Z} } @MISC{oai:CiteSeerPSU:208160, TITLE = {Predicate Control in Distributed Systems}, AUTHOR = {Ashis Tarafdar and Vijay K. Garg}, YEAR = {1997}, MONTH = FEB # {~17}, ABSTRACT = {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 this notion by defining the predicate control problem in terms of boolean global predicates and a model of distributed control. The problem arises in both off-line and on-line scenarios. We prove that general off-line predicate control is NP-Hard. However, we present an efficient solution for the class of disjunctive predicates. We show that on-line predicate control, on the other hand, is impossible to achieve even for disjunctive predicates. However, by placing restrictions on the underlying system, we are able to present an effective on-line control strategy. 1 Introduction An intrinsic problem in asynchronous distributed systems is that while no one process can have a global view, we still require the system as a whole to maintain global properties. This conflict has led to the design of...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:553969; oai:CiteSeerPSU:145873}, ANNOTE = {Ashis Tarafdar (Dept . of Computer Sciences Dept . of Computer and Electrical Engineering; University of Texas at Austin; Austin , TX 78712); Vijay K. Garg (Dept . of Computer Sciences Dept . of Computer and Electrical Engineering; University of Texas at Austin; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:208160}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/208160.html; http://www.ece.utexas.edu/~garg/dist/podc97.ps.Z} } @ARTICLE{Garg97, AUTHOR = {Vijay K. Garg}, TITLE = {Methods for Observing Global Properties in Distributed Systems}, JOURNAL = {IEEE Concurrency: Parallel Distributed \& Mobile Computing}, VOLUME = {5}, NUMBER = {4}, PAGES = {69--77}, MONTH = OCT # {-} # DEC, YEAR = {1997}, KEYWORDS = {distributed software,} } @INPROCEEDINGS{Mitchell97, AUTHOR = {J. Roger Mitchell and Vijay K. Garg}, TITLE = {Optimistic Agreement in Asynchronous Distributed Systems}, BOOKTITLE = {International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'97)}, PUBLISHER = {IEEE}, ADDRESS = {Las Vegas, Nevada, USA.}, MONTH = JUN, YEAR = {1997}, KEYWORDS = {short paper,}, ABSTRACT = {http://www.cps.udayton.edu/\~{}pan/pdpta.}, NOTE = {University of Texas, Austin} } @INPROCEEDINGS{ICDCS96*108, AUTHOR = {O. P. Damani and V. K. Garg}, TITLE = {How to Recover Efficiently and Asynchronously when Optimism Fails}, PAGES = {108--115}, BOOKTITLE = {Proceedings of the 16th International Conference on Distributed Computing Systems ({ICDCS} '96)}, ISBN = {0-8186-7398-2}, MONTH = MAY, PUBLISHER = {IEEE}, ADDRESS = {Washington - Brussels - Tokyo}, YEAR = {1996} } @INPROCEEDINGS{conf/seke/Garg96, TITLE = {Observation of Global Properties in Distributed Systems}, AUTHOR = {Vijay K. Garg}, YEAR = {1996}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/seke/seke1996.html#Garg96}, BOOKTITLE = {SEKE}, PAGES = {418--425} } @ARTICLE{journals/tpds/GargW96, TITLE = {Detection of Strong Unstable Predicates in Distributed Programs}, AUTHOR = {Vijay K. Garg and Brian Waldecker}, JOURNAL = {IEEE Trans. Parallel Distrib. Syst}, YEAR = {1996}, NUMBER = {12}, VOLUME = {7}, BIBDATE = {2003-11-20}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/tpds/tpds7.html#GargW96}, PAGES = {1323--1333}, URL = {http://www.computer.org/tpds/td1996/l1323abs.htm} } @ARTICLE{Cofer:1996:CTD, AUTHOR = {D. D. Cofer and V. K. Garg}, TITLE = {On controlling timed discrete event systems}, JOURNAL = {Lecture Notes in Computer Science}, VOLUME = {1066}, PAGES = {340--??}, YEAR = {1996}, CODEN = {LNCSD9}, ISSN = {0302-9743}, BIBDATE = {Wed Aug 14 09:38:08 MDT 1996}, ACKNOWLEDGEMENT = {Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|} } @MISC{oai:CiteSeerPSU:217976, TITLE = {How to Recover Efficiently and Asynchronously when Optimism Fails}, AUTHOR = {Om P. Damani and Vijay K. Garg}, YEAR = {1996}, MONTH = JAN # {~21}, ABSTRACT = {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 information in spite of failures, and a history mechanism to detect orphan states and obsolete messages. These two mechanisms together with checkpointing and messagelogging are used to restore the system to a consistent state after a failure of one or more processes. Our algorithm is completely asynchronous. It handles multiple failures and network partitioning, does not assume any message ordering, causes the minimum amount of rollback and restores the maximum recoverable state with low overhead. Earlier optimistic protocols lack one or more of the above properties. 1 Introduction For fault-resilience, a process periodically records its state on a stable storage [15]. This action is called checkpointing and the recorded state is called a checkpoint. The checkpoint is used to restore a pr...}, ANNOTE = {Om P. Damani (Dept . of Computer Sciences; Austin , Texas 78712); Vijay K. Garg (Dept . of Electrical and Computer Engineering; University of Texas at Austin; Austin , TX , 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:217976}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/217976.html; http://www.ece.utexas.edu/~garg/dist/om.ps.Z} } @MISC{oai:CiteSeerPSU:214141, TITLE = {An Efficient Algorithm for Multi-Process Shared Events}, AUTHOR = {Vijay K. Garg}, YEAR = {1996}, MONTH = JAN # {~21}, ABSTRACT = {Many problems in distributed computing systems require execution of events shared by multiple processes. In this paper, a fair and efficient algorithm for multiprocess shared events is presented. We also present its application to distributed implementation of generalized CSP alternative command. We show that our algorithm is simpler and has lower message and time complexity than proposed implementations for generalized CSP alternative command, and distributed algorithms for N-party interactions. 1. Introduction Wide availability of computer networks, and low cost of hardware has made it desirable to use distributed systems. Distributed systems, however, are difficult to design and often need tricky synchronization between multiple processes. The synchronization is required to coordinate multiple processes for events, which must be executed either by all, or none of them. Some examples of such shared events are distributed transactions in databases that require commit by either all o...}, ANNOTE = {Vijay K. Garg (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:214141}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/214141.html; http://www.ece.utexas.edu/~garg/dist/multi.ps.Z} } @MISC{oai:CiteSeerPSU:94029, TITLE = {Distributed Algorithms for Detecting Conjunctive Predicates}, AUTHOR = {Vijay K. Garg and Craig M. Chase}, YEAR = {1996}, MONTH = JAN # {~21}, ABSTRACT = {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 checker process requires O(n 2 m) time and space where m is the number of messages sent or received by any process and n is the number of processes over which the predicate is defined. In this paper, we introduce token-based algorithms which distribute the computation and space requirements of the detection procedure. The distributed algorithm has O(n 2 m) time, space and message complexity, distributed such that each process performs O(nm) work. We describe another distributed algorithm with O(Nm) total work, where N is the total number of processes in the system. The relative values of n and N determine which algorithm is more efficient for a specific application. 1 Introduction Detection of a global predicate is a fundamental problem in distributed computing. This problem arises in many ...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:150856; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:36395; oai:CiteSeerPSU:18867; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:158563}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:94029}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/94029.html; http://maple.ece.utexas.edu/~vijay/dist/dcs.ps.Z} } @MISC{oai:CiteSeerPSU:211665, TITLE = {Detection of Strong Unstable Predicates in Distributed Programs}, AUTHOR = {Vijay K. Garg and Brian Waldecker}, YEAR = {1996}, MONTH = JAN # {~21}, ABSTRACT = {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 to form many global sequences consistent with the single run of the program. A strong global predicate is true in a run if it is true for all global sequences consistent with the run. We present algorithms which detect if the given strong global predicate became true in a run of a distributed program. 1 Introduction Detection of global predicates is a fundamental problem in distributed computing. It arises in the designing, debugging and testing of distributed programs. Global predicates can be classified into two types - stable and unstable. A stable predicate is one which never turns false once it becomes true. An unstable predicate is one without such a property. Its value may alternate between true and false. Detection of stable predicates has been addressed in the literature by means ...}, ANNOTE = {Vijay K. Garg (Electrical and Computer Engineering Dept Austin Systems Center; University of Texas at Austin Schlumberger Well Services; Austin , TX 78712-1084 P.O. Box 200015); Brian Waldecker (Electrical and Computer Engineering Dept Austin Systems Center; University of Texas at Austin Schlumberger Well Services; Austin , TX 78712-1084 P.O. Box 200015);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:211665}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/211665.html; http://www.ece.utexas.edu/~garg/dist/strong.ps.Z} } @MISC{oai:CiteSeerPSU:142670, TITLE = {Exploiting Symmetry for Analysis of Distributed Systems}, AUTHOR = {Vijay K. Garg}, YEAR = {1996}, MONTH = JAN # {~21}, ABSTRACT = {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 have a large, or even an unknown, number of processes. These techniques, which are based on state space exploration, run into the state explosion problem. Since most distributed systems have one or more sets of identical processes, we exploit the symmetry to reduce the state space for automatic analysis techniques. We describe a model called Decomposed Petri Net that facilitates such analysis. We present symbolic and induction techniques to analyze concurrent systems described using Decomposed Petri Net. We illustrate our techniques by analyzing several examples: 2-out-of-3 problem, dining philosophers problem and mutual exclusion problem. These techniques are applicable to systems that are configured either in a star topology or a ring topology. We also show how to extend these techniques ...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:88007; oai:CiteSeerPSU:549299}, ANNOTE = {Vijay K. Garg (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:142670}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/142670.html; http://maple.ece.utexas.edu/~vijay/dist/analysis.ps.Z} } @MISC{oai:CiteSeerPSU:570176, TITLE = {Observation of Global Properties in Distributed Systems}, AUTHOR = {Vijay K. Garg}, YEAR = {1996}, MONTH = JUN # {~20}, ABSTRACT = {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 for observing various classes of global properties. These properties include those possibly true in a computation, definitely true in a computation and those based on the control flow structure of the computation.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:26745; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:18867; oai:CiteSeerPSU:147576; oai:CiteSeerPSU:176756; oai:CiteSeerPSU:70961; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:158563; oai:CiteSeerPSU:28082; oai:CiteSeerPSU:167359; oai:CiteSeerPSU:113196}, ANNOTE = {Vijay K. Garg (Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:570176}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/570176.html; http://www.ece.utexas.edu/~garg/dist/concur97.ps} } @TECHREPORT{oai:CiteSeerPSU:341010, TITLE = {Normality: {A} Consistency Condition for Concurrent Objects}, AUTHOR = {Vijay K. Garg and Michel Raynal and Projet Adp}, YEAR = {1996}, MONTH = JUN # {~19}, ABSTRACT = {: 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 operation applied by concurrent processes takes effect instantaneously at some point between the beginning and the end of its execution. When compared with other consistency conditions (such as sequential consistency) Linearizability satisfies the Locality property (i.e, a system is linearizable if each object taken individually is linearizable) and the Non-Blocking property (i.e., termination of an invoked operation does not depend on other pending invocations). Those are noteworthy properties as they allow concurrent systems to be designed and constructed in a modular fashion. This paper introduces a consistency condition called Normality that is less constraining than Linearizability (in the sense it does not refer to a global real-time order) and still satisfies Locality and Non-Blocking....}, ANNOTE = {Vijay K. Garg (INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYST EMES AL EATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France); Michel Raynal (INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYST EMES AL EATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:341010}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/341010.html; ftp://ftp.irisa.fr/techreports/1996/PI-1015.ps.gz} } @MISC{oai:CiteSeerPSU:249406, TITLE = {Parallel Distributed Systems group}, AUTHOR = {V. K. Garg and J. Roger Mitchel and Vijay K. Garg and J. Roger Mitchell}, YEAR = {1996}, MONTH = JUL # {~15}, ABSTRACT = {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 conjunction of two nonlocal predicates is possibly true in a distributed computation. For such global predicates, our algorithm is significantly more efficient than the previous algorithms by Cooper and Marzullo, and by Stoller and Schneider. 1 Introduction The detection of global conditions is a fundamental problem in an asynchronous distributed system. In such a system a process cannot know the state of other processes at any given time. This creates difficulty in detecting conditions, or predicates, spread across the system. Deadlock and termination are two such global predicates. Detection of these predicates is useful for distributed debugging, monitoring distributed systems for faults, and other areas of distributed computing. There are two interpretations of truthness of a global p...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:160542; oai:CiteSeerPSU:18867; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:28082}, ANNOTE = {V. K. Garg (Parallel Distributed Systems group; Department of Electrical Computer Engineering; University of Texas at Austin; Austin , Texas 78712); J. Roger Mitchel (Parallel Distributed Systems group; Department of Electrical Computer Engineering; University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:249406}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/249406.html; http://maple.ece.utexas.edu/~mitchell/PDS/1996/TR-PDS-1996-005.ps.Z} } @TECHREPORT{oai:CiteSeerPSU:138175, TITLE = {Characterization of Message Ordering Specifications and Protocols}, AUTHOR = {V. V. Murty and V. K. Garg}, YEAR = {1996}, MONTH = JUL # {~15}, ABSTRACT = {We study the problem of determining which message ordering specifications can be implemented in a distributed system. Further, if a specification can be implemented, we give a technique to determine whether it can be implemented by tagging information with user messages or if it requires control messages. To specify the message ordering, we use a novel method called forbidden predicates. All existing message ordering guarantees such as FIFO, flush channels, causal ordering, and logically synchronous ordering, (as well as many new message orderings) can be concisely specified using forbidden predicates. We then present an algorithm that determines from the forbidden predicate the type of protocol needed to implement that specification. Keywords: Message ordering, forbidden predicate, predicate graph, protocols and specifications. 1 Introduction A distributed computation or a run describes an execution of a distributed program. At an abstract level, a run can be defined as a partiall...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:9605; oai:CiteSeerPSU:171238; oai:CiteSeerPSU:1861}, ANNOTE = {V. V. Murty (Department of Electrical Computer Engineering; University of Texas at Austin; Austin , Texas 78712); V. K. Garg (Department of Electrical Computer Engineering; University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:138175}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/138175.html; http://maple.ece.utexas.edu/TechReports/1996/TR-PDS-1996-004.ps.Z} } @BOOK{Garg96, AUTHOR = {Vijay K. Garg}, TITLE = {Principles of Distributed Systems}, PUBLISHER = {Kluwer Academic Publishers}, ADDRESS = {Boston}, YEAR = {1996}, KEYWORDS = {book, text, time, mutual exclusion, predicates,}, NOTE = {UT Austin} } @TECHREPORT{Garg96a, AUTHOR = {Vijay K. Garg and Michel Raynal}, TITLE = {A Consistency Condition for Concurrent Objects}, INSTITUTION = {IRISA}, NUMBER = {PI-1015}, ADDRESS = {Campus de Beaulieu, 35042 Rennes Cedex, FRANCE}, MONTH = {mai}, YEAR = {1996}, KEYWORDS = {Concurrent Objects, Consistency Condition, Linearizability, Locality Property, Non-Blocking Property, Mots cl'es absence de blocage, coh'erence, lin'earisabilit'e, localit'e, objets concurrents}, ABSTRACT = {Abstract 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 operation applied by concurrent processes takes effect instantaneously at some point between the beginning and the end of its execution. When compared with other consistency conditions (such as sequential consistency) Linearizability satisfies the Locality property (i.e, a system is linearizable if each object taken individually is linearizable) and the Non-Blocking property (i.e., termination of an invoked operation does not depend on other pending invocations). Those are noteworthy properties as they allow concurrent systems to be designed and constructed in a modular fashion. This paper introduces a consistency condition called Normality that is less constraining than Linearizability (in the sense it does not refer to a global real-time order) and still satisfies Locality and Non-Blocking. As it does not refer to a global real-time, Normality is well-suited to objects supported by asynchronous distributed systems and can consequently be seen as an adaptation of Linearizability for these systems.\par R'esum'e Cet article pr'esente un crit`ere de coh'erence, appel'e Normalit'e, pour les objets d'efinis `a partir de types abstraits et acc'ed'es par des processus concurrents. La d'efinition est moins contraignante que celle de la lin'earisabilit'e, tout en pr'eservant comme cette derni`ere, les propri'et'es cruciales que sont la localit'e et le non-blocage. La normalit'e est particuli`erement int'eressante car, tout en formalisant la s'emantique intuitive classiquement utilis'ees par les programmeurs, elle ne fait pas r'ef'erence `a un temps physique global et `a ce titre s'adapte naturellement au contexte r'eparti asynchrone.}, NOTE = {ftp://ftp.irisa.fr/techreports/1996/PI-1015.ps.gz} } @INCOLLECTION{de_souza96a, AUTHOR = {Jr. P. A. {de Souza} and E. O. T. Salles and V. K. Garg}, TITLE = {Artificial neural network in Mossbauer mineralogy}, BOOKTITLE = {38th Midwest Symposium on Circuits and Systems. Proceedings}, PUBLISHER = {IEEE}, YEAR = {1996}, VOLUME = {1}, EDITOR = {L. P. Caloba and P. S. R. Diniz and A. C. M. {de Querioz} and E. H. Watanabe}, ADDRESS = {New York, NY, USA}, PAGES = {558--61}, DBINSDATE = {oldtimer} } @INPROCEEDINGS{Cofer95a, AUTHOR = {D. D. Cofer and V. K. Garg}, YEAR = {1995}, TITLE = {On Controlling Timed Discrete Event Systems}, BOOKTITLE = {Proc. Workshop on Verification and Control of Hybrid Systems}, PAGES = {340--349}, ABSTRACT = {This paper is a survey of our work on controlling discrete event systems modelled by timed event graphs. Such systems are structurally related to finite state machines in that both can be described by linear equations over an appropriate algebra. Using this structural similarity, we have extended supervisory control techniques developed for untimed DES to the timed case. When behavioral constraints are given as a a range of acceptable schedules, it is possible to compute an extremal controllable subset or superset of the desired behavior. When constraints are expressed in terms of minimum separation times between events, it is possible to determine whether there is a controllable schedule which realizes the desired behavior.} } @INPROCEEDINGS{WDAG::ChaseG1995, TITLE = {Efficient Detection of Restricted Classes of Global Predicates}, AUTHOR = {Craig M. Chase and Vijay K. Garg}, BOOKTITLE = {Distributed Algorithms, 9th International Workshop, {WDAG} '95}, EDITOR = {Jean-Michel H{\'e}lary and Michel Raynal}, ADDRESS = {Le Mont-Saint-Michel, France}, MONTH = {13--15~} # SEP, YEAR = {1995}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {972}, PUBLISHER = {Springer}, ISBN = {ISBN 3-540-60274-7}, PAGES = {303--317} } @ARTICLE{TCS::KumarG1995:67, TITLE = {Extremal solutions of inequations over lattices with applications to supervisory control}, AUTHOR = {Ratnesh Kumar and Vijay K. Garg}, JOURNAL = {Theoretical Computer Science}, PAGES = {67--92}, MONTH = {21~} # AUG, YEAR = {1995}, VOLUME = {148}, NUMBER = {1} } @INPROCEEDINGS{SPDP95*432, AUTHOR = {V. K. Garg and A. Tomlinson and E. Fromentin and M. Raynal}, TITLE = {Expressing and Detecting Control Flow Properties of Distributed Computations}, PAGES = {432--439}, BOOKTITLE = {Symposium on Parallel and Distributed Processing ({SPDP} '95)}, MONTH = OCT, PUBLISHER = {IEEE Computer Society Press}, ADDRESS = {Los Alamitos, Ca., USA}, YEAR = {1995}, ISBN = {0-8186-7195-5} } @INPROCEEDINGS{conf/hicss/GargCMK95, TITLE = {Detecting conjunctive channel predicates in a distributed programming environment}, AUTHOR = {Vijay K. Garg and Craig M. Chase and J. Roger Mitchell and Richard B. Kilgore}, YEAR = {1995}, BIBDATE = {2004-05-11}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/hicss/hicss1995-2.html#GargCMK95}, BOOKTITLE = {HICSS (2)}, PAGES = {232--241}, URL = {http://csdl.computer.org/comp/proceedings/hicss/1995/6935/00/69350232abs.htm} } @INPROCEEDINGS{conf/compsac/MitchellG95, TITLE = {Deriving distributed algorithms from a general predicate detector}, AUTHOR = {J. Roger Mitchell and Vijay K. Garg}, PUBLISHER = {IEEE Computer Society}, YEAR = {1995}, BIBDATE = {2003-02-12}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/compsac/compsac1995.html#MitchellG95}, BOOKTITLE = {COMPSAC}, PAGES = {268--277}, URL = {http://computer.org/proceedings/compsac/7119/71190268abs.htm} } @INPROCEEDINGS{conf/fsttcs/TomlinsonG95, TITLE = {Observation of Software for Distributed Systems with {RCL}}, AUTHOR = {Alexander I. Tomlinson and Vijay K. Garg}, BIBDATE = {2002-06-17}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/fsttcs/fsttcs95.html#TomlinsonG95}, BOOKTITLE = {FSTTCS}, BOOKTITLE = {Foundations of Software Technology and Theoretical Computer Science, 15th Conference, Bangalore, India, December 18-20, 1995, Proceedings}, PUBLISHER = {Springer}, YEAR = {1995}, VOLUME = {1026}, EDITOR = {P. S. Thiagarajan}, ISBN = {3-540-60692-0}, PAGES = {195--209}, SERIES = {Lecture Notes in Computer Science} } @MISC{oai:CiteSeerPSU:134185, TITLE = {Optimal Supervisory Control of Discrete Event Dynamical Systems}, AUTHOR = {Ratnesh Kumar and Vijay K. Garg}, YEAR = {1995}, MONTH = JUL # {~06}, ABSTRACT = {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 controlled by disabling some of its transitions. We define two types of cost functions: a cost of control function corresponding to disabling transitions in the state machine, and a penalty of control function corresponding to reaching some undesired states, or not reaching some desired states in the controlled system. The control objective is to design an optimal control mechanism, if it exists, so that the net cost is minimized. Since a DEDS is represented as a state machine---a directed graph---network flow techniques are naturally applied for designing optimal supervisors. We also show that our techniques can be used for solving supervisory control problems under complete as well as partial observation. In particular, we obtain, for the first time, techniques for computing the supremal controllable a...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:12283; oai:CiteSeerPSU:107182; oai:CiteSeerPSU:51811}, ANNOTE = {Ratnesh Kumar (Department of Electrical Engineering; University of Kentucky; Lexington , KY 40506-0046); Vijay K. Garg (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:134185}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/134185.html; http://www.ece.utexas.edu/~garg/des/siam2.ps.Z} } @MISC{oai:CiteSeerPSU:163987, TITLE = {Finite Buffer Realization of Input-Output Discrete Event Systems}, AUTHOR = {Ratnesh Kumar and Vijay K. Garg and Steven I. Marcus}, YEAR = {1995}, MONTH = JUL # {~06}, ABSTRACT = {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 (I/O DESs). In this paper we formulate and study the problem of stable realization of such systems in the logical setting. Given an input and an output language describing the sequences of events that occur at the input and the output, respectively, of an I/O DES, we study whether it is possible to realize the system as a unit consisting of a given set of buffers of finite capacity, called a dispatching unit. The notions of stable, conditionally stable, dispatchable and conditionally dispatchable units are introduced as existence of stable (or input-output bounded), and causal (or prefix preserving) input-output maps, and effectively computable necessary and sufficient conditions for testing them are obtained. 1 Introduction and Motivation A discrete event system (DES) is one in which the ...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:394586; oai:CiteSeerPSU:542436; oai:CiteSeerPSU:107182; oai:CiteSeerPSU:193302}, ANNOTE = {Ratnesh Kumar (Department of Electrical Engineering; University of Kentucky; Lexington , KY 40506-0046); Vijay K. Garg (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , Texas 78712-1084); Steven I. Marcus (Department of Electrical Engineering and; Institute for Systems Research; University of Maryland; College Park , MD 20742);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:163987}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/163987.html; http://www.ece.utexas.edu/~garg/des/buffer.ps.Z} } @MISC{oai:CiteSeerPSU:159118, TITLE = {Model Uncertainty in Discrete Event Systems}, AUTHOR = {Stanley Young and Vijay K. Garg}, YEAR = {1995}, MONTH = JUL # {~06}, ABSTRACT = {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 determining the correct model from a set of models. The result of the algorithm is a finite language which can be used to test for the correct model or notification that the remaining models cannot be controllably distinguished. We use the finite state machine model with controllable and uncontrollable events presented by Ramadge and Wonham 1 . Keywords: Discrete Event Systems, System Identification AMS(MOS) subject classification: 93A,93B Supported in part by National Science Foundation CCR-911065, and in part by the University Research Institute, University of Texas at Austin. 1 A preliminary version of this paper appeared as [18]. Another version will appear in SIAM Journal of Control and Optimization. 1 Introduction A discrete event system (DES) is one which responds to distinct eve...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:107182; oai:CiteSeerPSU:447613}, ANNOTE = {Stanley Young (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712); Vijay K. Garg (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:159118}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/159118.html; http://www.ece.utexas.edu/~garg/des/SCC-93-04.ps.Z} } @MISC{oai:CiteSeerPSU:77020, TITLE = {On the Fly Testing of Regular Patterms in Distributed Computations}, AUTHOR = {Eddy Fromentin and Michel Raynal and Vijay K Garg}, YEAR = {1995}, MONTH = MAR # {~10}, ANNOTE = {Eddy Fromentin (IRISA Projet ADP , Campus universitaire de Beaulieu , 35042 Rennes Cedex , France); Michel Raynal (IRISA Projet ADP , Campus universitaire de Beaulieu , 35042 Rennes Cedex , France); Vijay K Garg (IRISA Projet ADP , Campus universitaire de Beaulieu , 35042 Rennes Cedex , France);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, DESCRIPTION = {This paper will appear in the proceedings of the 23}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:77020}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/77020.html; http://www.laas.research.ec.org/broadcast/trs/./papers/43.ps} } @TECHREPORT{oai:CiteSeerPSU:116490, TITLE = {Detecting Conjunctive Channel Predicates in a Distributed Programming Environment}, AUTHOR = {J. Roger and Mitchell Richard Kilgore and Vijay K. Garg and Craig Chase and J. Roger Mitchell and Richard Kilgore}, YEAR = {1995}, MONTH = DEC # {~19}, ABSTRACT = {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 as a boolean formula of local predicates. Many properties in distributed systems, however, use the state of channels. In this paper, we introduce the concept of a channel predicate and provide an efficient algorithm to detect any boolean formula of local and channel predicates. We define a property called monotonicity for channel predicates. Monotonicity is crucial for efficient detection of global predicates. We show that many problems studied earlier such as detection of termination and computation of global virtual time are special cases of the problem considered in this paper. The message complexity of our algorithm is bounded by the number of messages used by the program. The main application of our results are in debugging and testing of distributed programs. Our algorithms have been ...}, ANNOTE = {Mitchell Richard Kilgore (UNIVERSITY; TEXAS AUSTIN); Vijay K. Garg (Parallel and Distributed Systems Laboratory; Austin , Texas 78712); Richard Kilgore (Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:116490}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/116490.html; http://maple.ece.utexas.edu/TechReports/1994/TR-PDS-1994-002.ps.Z} } @MISC{oai:CiteSeerPSU:59101, TITLE = {Conjunctive Predicate Detection}, AUTHOR = {Vijay K. Garg and Craig M. Chase and J. Roger Mitchell and Richard Kilgore}, YEAR = {1995}, MONTH = SEP # {~21}, ABSTRACT = {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 boolean formula of local predicates. Many properties in distributed systems, however, use the state of channels. In this paper, we introduce the concept of a channel predicate and provide an efficient algorithm to detect any boolean formula of local and channel predicates. We define a property called monotonicity for channel predicates. Monotonicity is crucial for efficient detection of global predicates. We show that many problems studied earlier, such as detection of termination and computation of global virtual time are special cases of the problem considered in this paper. The message complexity of our algorithm is bounded by the number of messages used by the program. The main application of our results are in debugging and testing of distributed programs. Our algorithms have been incorpora...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:150856; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:36395; oai:CiteSeerPSU:564740; oai:CiteSeerPSU:18867; oai:CiteSeerPSU:70961; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:158563}, ANNOTE = {Vijay K. Garg (Parallel and Distributed Systems Laboratory); Richard Kilgore (Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:59101}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/59101.html; http://lore.ece.utexas.edu/~rkilgore/Publications/papers/channel-hicss95.ps.gz} } @MISC{oai:CiteSeerPSU:82167, TITLE = {State Avoidance Control for Infinite State Systems using Assignment Program Model}, AUTHOR = {Ratnesh Kumar and Vijay K. Garg}, YEAR = {1995}, MONTH = MAY # {~28}, ABSTRACT = {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 allows a concise characterization of systems with infinitely many states, and secondly, state variable specification allows characterization of qualitative properties of general nondeterministic systems. An assignment program consisting of state variables and a finite set of conditional assignment statements is used for representing a discrete event system, and a set of forbidden states is used for representing a control specification. The control synthesis problem is undecidable in the general setting. However, in the special case when a single uncontrollable event is present, we show that the problem of computing a maximally permissive supervisor reduces to that of solving an arithmetic equation. Also, in another special case when the system can be represented as a vector addition system...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:107182; oai:CiteSeerPSU:51811; oai:CiteSeerPSU:269737; oai:CiteSeerPSU:273949; oai:CiteSeerPSU:452558; oai:CiteSeerPSU:273949; oai:CiteSeerPSU:106220}, ANNOTE = {Ratnesh Kumar (Department of Electrical Engineering; University of Kentucky; Lexington , KY 40506-0046); Vijay K. Garg (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:82167}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/82167.html; http://maple.ece.utexas.edu/~vijay/papers/des/statevar/root.ps.Z} } @ARTICLE{Garg95a, AUTHOR = {V. K. Garg and A. Tomlinson and E. Fromentin and M. Raynal}, JOURNAL = {(Proc. 7th IEEE Symp. on) Parallel and Distributed Processing}, PAGES = {432--439}, PUBLISHER = {IEEE}, ADDRESS = {Los Alamitos, CA}, YEAR = {1995}, KEYWORDS = {parallel programming,} } @INPROCEEDINGS{icpp94-2*73, AUTHOR = {E. Fromentin and M. Raynal and V. K. Garg and A. Tomlinson}, TITLE = {On the fly testing of regular patterns in distributed computations}, PAGES = {73--76}, ISBN = {0-8493-2494-7}, EDITOR = {K. C. Tai}, BOOKTITLE = {Proceedings of the 23rd International Conference on Parallel Processing. Volume 2: Software}, MONTH = AUG, PUBLISHER = {CRC Press}, ADDRESS = {Boca Raton, FL, USA}, YEAR = {1994} } @INPROCEEDINGS{SPDP93*478, AUTHOR = {V. K. Garg and A. I. Tomlinson}, TITLE = {Using Induction to Prove Properties of Distributed Programs}, PAGES = {478--485}, BOOKTITLE = {Symposium on Parallel and Distributed Systems ({SPDP} '93)}, MONTH = DEC, PUBLISHER = {IEEE Computer Society Press}, ADDRESS = {Los Alamitos, Ca., USA}, YEAR = {1994}, ISBN = {0-8186-4222-X} } @INPROCEEDINGS{spdp94*249, AUTHOR = {V. K. Garg and A. I. Tomlinson}, TITLE = {Causality versus Thme: How to Specify and Verify Distributed Algorithms}, PAGES = {249--256}, ISBN = {0-8186-6427-4}, BOOKTITLE = {Proceedings of the 6th Symposium on Parallel and Distributed Processing}, MONTH = OCT, PUBLISHER = {IEEE Computer Society Press}, ADDRESS = {Los Alamitos, CA, USA}, YEAR = {1994} } @ARTICLE{journals/tpds/GargW94, TITLE = {Detection of Weak Unstable Predicates in Distributed Programs}, AUTHOR = {Vijay K. Garg and Brian Waldecker}, JOURNAL = {IEEE Trans. Parallel Distrib. Syst}, YEAR = {1994}, NUMBER = {3}, VOLUME = {5}, BIBDATE = {2003-11-20}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/tpds/tpds5.html#GargW94}, PAGES = {299--307}, URL = {http://computer.org/tpds/td1994/l0299abs.htm} } @ARTICLE{journals/tpds/GargG94, TITLE = {Repeated Computation of Global Functions in a Distributed Environment}, AUTHOR = {Vijay K. Garg and Joydeep Ghosh}, JOURNAL = {IEEE Trans. Parallel Distrib. Syst}, YEAR = {1994}, NUMBER = {8}, VOLUME = {5}, BIBDATE = {2003-11-20}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/tpds/tpds5.html#GargG94}, PAGES = {823--834}, URL = {http://computer.org/tpds/td1994/l0823abs.htm} } @INPROCEEDINGS{Garg-Tomlinson/94, AUTHOR = {Vijay K. Garg and Alexander I. Tomlinson}, TITLE = {Causality versus time: How to specify and verify distributed algorithms}, BOOKTITLE = {Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing, SPDP'94 (Dallas, Texas, October 26-29, 1994)}, PAGES = {249--256}, YEAR = {1994}, PUBLISHER = {IEEE Computer Society Press}, ORGANIZATION = {IEEE Computer Society}, ADDRESS = {Los Alamitos-Washington-Brussels-Tokyo}, CDATE = {1970-01-01}, MDATE = {2005-08-18} } @TECHREPORT{oai:CiteSeerPSU:350279, TITLE = {Corrections to {} } @MISC{oai:CiteSeerPSU:13348, TITLE = {Supervisory Control of Real-time Discrete Event Systems using Lattice Theory}, AUTHOR = {Darren D. Cofer and Vijay K. Garg}, YEAR = {1994}, MONTH = JUL # {~06}, ABSTRACT = {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 languages also form a lattice, questions of controllability for timed DES may be treated in much the same manner as they are for untimed systems. In this paper we establish conditions for the controllability of timed DES performance specification which are expressed as inequations on the lattice. Thses specifications may take the form of sets of acceptable event occurrence times, maximum or minimum occurrence times, or limits on the separation times between events. Optimal behaviors are found as extremal solutions to these inequations using fixed point results for lattices. Keywords: Discrete event systems, supervisory control, maxalgebra, lattices. Supported in part by NSF Grant CCR-9110605, Army Grant N00039-91-C-0082, a TRW faculty assistantship award, General Motors Fellowship, and an IBM g...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:74476; oai:CiteSeerPSU:287011}, ANNOTE = {Darren D. Cofer (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , TX 78712-1084); Vijay K. Garg (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:13348}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/13348.html; http://www.ece.utexas.edu/~garg/des/SCC-94-02.ps.Z} } @MISC{oai:CiteSeerPSU:350746, TITLE = {Control of Discrete Event Systems Modeled with Deterministic {B}{\"u}chi Automata}, AUTHOR = {Stanley Young and Damir Spanjol and Vijay K. Garg}, YEAR = {1994}, MONTH = JUL # {~06}, ABSTRACT = {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 DES modeled by state machines which has been expanded by others to include the concepts of observability and stability. Previous work by Ramadge extended the concept of controllable languages to infinite languages and presented conditions for the existence of a supervisor for systems modeled by Buchi automata. The goal of this paper is to derive requirements for the existence of a supervisor under less restrictive conditions on the constraint language for plants which satisfy certain conditions. This supervisor is shown to approach the prescribed closed loop behavior and retain all behaviors within a specified error bound of the desired behavior. Both deterministic and nondeterministic supervisors are considered. The construction for such a supervisor is given along with example...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:12283; oai:CiteSeerPSU:107182; oai:CiteSeerPSU:350746}, ANNOTE = {Stanley Young (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712); Damir Spanjol (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712); Vijay K. Garg (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:350746}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/350746.html; http://www.ece.utexas.edu/~garg/des/SCC-93-03.ps.Z} } @MISC{oai:CiteSeerPSU:138566, TITLE = {Optimal Sensor and Actuator Choices for Discrete Event Systems}, AUTHOR = {Stanley D. Young and Vijay K. Garg}, YEAR = {1994}, MONTH = JUL # {~06}, ABSTRACT = {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 paper are algorithms which demonstrate: the polynomial solution to the choice of actuators, the polynomial solution to the choice of sensors for certain supervisory control problems, and the solution to the general choice of sensors 1 . Keywords: Discrete Event Systems, Observability, Controllability 1 Introduction This work addresses the question of how to choose sensors and actuators to control a discrete event system to attain a specified behavior. Supervision Supported in part by NSF CCR-911065 and TRW Faculty Assistantship Award. y Supported in part by a DuPont Fellowship. 1 A preliminary version of this paper appeared as [18]. of such systems is achieved by observing events and disabling those which are not desired or lead to undesirable behavior. A supervisor uses sensors ...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:94231; oai:CiteSeerPSU:18059; oai:CiteSeerPSU:138566}, ANNOTE = {Stanley D. Young (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , Texas 78712); Vijay K. Garg (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:138566}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/138566.html; http://www.ece.utexas.edu/~garg/des/SCC-93-07.ps.Z} } @MISC{oai:CiteSeerPSU:55855, TITLE = {Expressing and Detecting Control Flow Properties of Distributed Computations}, AUTHOR = {Vijay K Garg and Alex Tomlinson and Eddy Fromentin and Michel Raynal and Projets Adp}, YEAR = {1994}, MONTH = NOV # {~07}, ABSTRACT = {: 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 expressing general properties on control flows, seen as sequences of local states. Among other properties, we can express invariance, sequential properties (to satisfy such a property a control flow must match a pattern described as a word on some alphabet) and non-sequential properties (these properties are on several control flows at the same time). A decentralized detection algorithm for properties described by this logic is then presented. This algorithm, surprisingly simple despite the power of the logic, observes the underlying distributed computation, does not alter its control flows and uses message tags to carry detection-related information. Key-words: behavioral property, distributed computation, distributed debugging, on the fly detection, control flows. (R'esum'e : tsvp) ...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:150856; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:36395; oai:CiteSeerPSU:70961; oai:CiteSeerPSU:316657; oai:CiteSeerPSU:158563; oai:CiteSeerPSU:35789}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:55855}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/55855.html; ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-2384.ps.gz} } @TECHREPORT{oai:CiteSeerPSU:340013, TITLE = {{I} {R} {I} {S} a}, AUTHOR = {Vijay K Garg and Alex Tomlinson and Eddy Fromentin and Michel Raynal and Projets Adp}, YEAR = {1994}, MONTH = NOV # {~02}, ABSTRACT = {: 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 expressing general properties on control flows, seen as sequences of local states. Among other properties, we can express invariance, sequential properties (to satisfy such a property a control flow must match a pattern described as a word on some alphabet) and non-sequential properties (these properties are on several control flows at the same time). A decentralized detection algorithm for properties described by this logic is then presented. This algorithm, surprisingly simple despite the power of the logic, observes the underlying distributed computation, does not alter its control flows and uses message tags to carry detection-related information. Key-words: behavioral property, distributed computation, distributed debugging, on the fly detection, control flows. (R'esum'e : tsvp) ...}, ANNOTE = {Vijay K Garg (INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYSTE MES ALE ATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France); Alex Tomlinson (INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYSTE MES ALE ATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France); Eddy Fromentin (INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYSTE MES ALE ATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France); Michel Raynal (INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYSTE MES ALE ATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:340013}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/340013.html; ftp://ftp.irisa.fr/techreports/1994/PI-872.ps.gz} } @TECHREPORT{oai:CiteSeerPSU:345125, TITLE = {{I} {R} {I} {S} a}, AUTHOR = {Eddy Fromentin and Michel Raynal and Vijay K Garg and Projet Adp}, YEAR = {1994}, MONTH = APR # {~28}, ABSTRACT = {: 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 expected (or unwanted) behavior of a computation as sequences of relevant events (or as sequences of local predicates that must be successively verified). The sequences are defined by a finite state automaton (hence the name regular patterns). A computation verifies the property if and only if one of its causal paths matches a sequence. Key-words: behavioral property, distributed computation, distributed debugging, on the fly detection, regular pattern. (R'esum'e : tsvp) This paper will appear in the proceedings of the 23 th Int. Conf. on Parallel Processing, Pennsylvanie State Univ., August 1994. IRISA -- Campus de Beaulieu, 35042 RENNES cedex -- FRANCE, e-mail:ffromenti, raynalg@irisa.fr Dept. of ECE -- University of Texas at AUstin, Austin TX, e-mail: fvijay,alextg@pine.ece.utexas.edu ...}, ANNOTE = {Eddy Fromentin (ALEX TOMLINSON; INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYSTE MES ALE ATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France); Michel Raynal (ALEX TOMLINSON; INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYSTE MES ALE ATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France); Vijay K Garg (ALEX TOMLINSON; INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYSTE MES ALE ATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:345125}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/345125.html; ftp://ftp.irisa.fr/techreports/1994/PI-817.ps.gz} } @TECHREPORT{oai:CiteSeerPSU:36395, TITLE = {On The Fly Testing Of Regular Patterns In Distributed Computations}, AUTHOR = {Eddy Fromentin and Michel Raynal and Vijay K Garg}, YEAR = {1994}, MONTH = DEC # {~19}, ABSTRACT = {: 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 expected (or unwanted) behavior of a computation as sequences of relevant events (or as sequences of local predicates that must be successively verified). The sequences are defined by a finite state automaton (hence the name regular patterns). A computation verifies the property if and only if one of its causal paths matches a sequence. Key-words: behavioral property, distributed computation, distributed debugging, on the fly detection, regular pattern. (R'esum'e : tsvp) This paper will appear in the proceedings of the 23 th Int. Conf. on Parallel Processing, Pennsylvanie State Univ., August 1994. IRISA -- Campus de Beaulieu, 35042 RENNES cedex -- FRANCE, e-mail:ffromenti, raynalg@irisa.fr Dept. of ECE -- University of Texas at AUstin, Austin TX, e-mail: fvijay,alextg@pine.ece.utexas.edu...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:150856; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:70961; oai:CiteSeerPSU:316657; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:158563; oai:CiteSeerPSU:35789}, ANNOTE = {Eddy Fromentin (ALEX TOMLINSON; INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYSTE MES ALE ATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France); Michel Raynal (ALEX TOMLINSON; INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYSTE MES ALE ATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France); Vijay K Garg (ALEX TOMLINSON; INSTITUT DE RECHERCHE EN INFORMATIQUE ET SYSTE MES ALE ATOIRES; Campus de Beaulieu -- 35042 Rennes Cedex -- France);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:36395}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/36395.html; http://maple.ece.utexas.edu/TechReports/1994/TR-PDS-1994-013.ps.Z} } @TECHREPORT{oai:CiteSeerPSU:94453, TITLE = {Maintaining Global Assertions on Distributed Systems}, AUTHOR = {Alexander I. Tomlinson and Vijay K. Garg}, YEAR = {1994}, MONTH = DEC # {~19}, ABSTRACT = {This paper develops a method for maintaining global assertions on a network of distributed processes. The global assertion has the form (X 1 1 X 1 2 Delta Delta Delta X 1 N 1 ) + : : : + (X M 1 X M 2 Delta Delta Delta X M NM ) K, where X j i is a variable which is local to one process in a distributed system and K is a constant. It is assumed that the initial values of all local variables are known and that the global assertion initially holds. This form is more general than the summation form considered in earlier work. 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. Research supported in part by NSF Grant CCR 9110605, Navy Grant N00039-88-C-0082, TRW faculty assistantship award, IBM Agreement 153, and a Microelectronics Computer Development Fellowship. 1 Intr...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:71684}, ANNOTE = {Alexander I. Tomlinson (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , Texas 78712); Vijay K. Garg (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:94453}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/94453.html; http://maple.ece.utexas.edu/TechReports/1994/TR-PDS-1994-010.ps.Z} } @MISC{oai:CiteSeerPSU:252756, TITLE = {Parallel Distributed Systems group}, AUTHOR = {J. Roger and Mitchell Richard Kilgore and Vijay K. Garg and Craig Chase and J. Roger Mitchell and Richard Kilgore}, YEAR = {1994}, MONTH = DEC # {~19}, ABSTRACT = {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 as a boolean formula of local predicates. Many properties in distributed systems, however, use the state of channels. In this paper, we introduce the concept of a channel predicate and provide an efficient algorithm to detect any boolean formula of local and channel predicates. We define a property called monotonicity for channel predicates. Monotonicity is crucial for efficient detection of global predicates. We show that many problems studied earlier such as detection of termination and computation of global virtual time are special cases of the problem considered in this paper. The message complexity of our algorithm is bounded by the number of messages used by the program. The main application of our results are in debugging and testing of distributed programs. Our algorithms ...}, ANNOTE = {Mitchell Richard Kilgore (UNIVERSITY; TEXAS AUSTIN); Vijay K. Garg (Parallel and Distributed Systems Laboratory; Austin , Texas 78712); Richard Kilgore (Electrical and Computer Engineering Department; The University of Texas at Austin; Austin , TX 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:252756}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/252756.html; http://maple.ece.utexas.edu/~mitchell/PDS/1994/TR-PDS-1994-002.ps.Z} } @TECHREPORT{oai:CiteSeerPSU:71078, TITLE = {Causality for Time: How to Specify and Verify Distributed Algorithms}, AUTHOR = {Vijay K. Garg and Alexander I. Tomlinson}, YEAR = {1994}, MONTH = DEC # {~19}, ABSTRACT = {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. All properties are proven using induction on the happenedbefore relation and its complement. We illustrate our technique by providing a formal proof of Lamport's algorithm for mutual exclusion. 1 Introduction We define a distributed system as a collection of processors geographically distributed which do not share any memory or clock. Further, it is assumed that different clocks cannot be perfectly synchronized due to uncertainty in communication delays. The importance of distinction between causality and time in such an environment was first emphasized by Leslie Lamport in [9]. It is now well understood that the concept of time can be replaced by that of causality with many advantages. For example, even though it is impossible to detect a global property that became true at some physical t...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:160542; oai:CiteSeerPSU:171238; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:564740}, ANNOTE = {Vijay K. Garg (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712-1084); Alexander I. Tomlinson (Department of Electrical and Computer Engineering,; University of Texas; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:71078}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/71078.html; http://maple.ece.utexas.edu/TechReports/1994/TR-PDS-1994-007.ps.Z} } @TECHREPORT{oai:CiteSeerPSU:113196, TITLE = {Monitoring Functions on Global States of Distributed Programs}, AUTHOR = {Alexander I. Tomlinson and Vijay K. Garg}, YEAR = {1994}, MONTH = DEC # {~19}, ABSTRACT = {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 which the sum x 1 +x 2 + : : : +xN exceeds some constant K, where x i is defined in process i. We examine the cases where x i is an integer variable and where x i is a boolean variable. For both cases we provide algorithms, prove their correctness and analyze their complexity. 1 Introduction As a distributed program executes, each process proceeds through a sequence of local states. The set S of all local states is partially ordered by Lamport's happens before relation[Lam78], denoted by !. A global state is a subset of S in which no two elements are ordered by !. Given a global state c of some execution, it is impossible to determine if c actually occurred in an execution. However, it is known that c is consistent with some global state that did occur in the execution [CL85, Mat89]. In ot...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:150856; oai:CiteSeerPSU:160542; oai:CiteSeerPSU:36395; oai:CiteSeerPSU:171238; oai:CiteSeerPSU:18867; oai:CiteSeerPSU:70961; oai:CiteSeerPSU:316657; oai:CiteSeerPSU:145873; oai:CiteSeerPSU:158563}, ANNOTE = {Alexander I. Tomlinson (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , Texas 78712); Vijay K. Garg (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:113196}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/113196.html; http://maple.ece.utexas.edu/TechReports/1994/TR-PDS-1994-006.ps.Z} } @MISC{oai:CiteSeerPSU:322338, TITLE = {On The Fly Testing Of Regular Patterns In Distributed Computations}, AUTHOR = {Alex Tomlinson and Eddy Fromentin and Michel Raynal and Vijay K Garg and Projet Adp}, YEAR = {1994}, MONTH = MAY # {~20}, ABSTRACT = {: 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 expected (or unwanted) behavior of a computation as sequences of relevant events (or as sequences of local predicates that must be successively verified). The sequences are defined by a finite state automaton (hence the name regular patterns). A computation verifies the property if and only if one of its causal paths matches a sequence. Key-words: behavioral property, distributed computation, distributed debugging, on the fly detection, regular pattern. (R'esum'e : tsvp) This paper will appear in the proceedings of the 23 th Int. Conf. on Parallel Processing, Pennsylvanie State Univ., August 1994. IRISA -- Campus de Beaulieu, 35042 RENNES cedex -- FRANCE, e-mail:ffromenti, raynalg@irisa.fr Dept. of ECE -- University of Texas at AUstin, Austin TX, e-mail: fvijay,alextg@pine.ece.utexas.edu ...}, ANNOTE = {Alex Tomlinson (Avril 1994); Eddy Fromentin (Avril 1994); Michel Raynal (Avril 1994); Vijay K Garg (Avril 1994);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:322338}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/322338.html; ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-2252.ps.gz} } @MISC{oai:CiteSeerPSU:568147, TITLE = {An Algorithm For Minimally Latent Global}, AUTHOR = {Alexander I. Tomlinson and Vijay K. Garg}, YEAR = {1994}, MONTH = JAN # {~24}, ABSTRACT = {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 course of a simulation. A small GVT latency (delay between its occurrence and detection) allows for more efficient use of resources. We present an algorithm which minimizes the latency, and we prove its correctness. The algorithm is unique in that a target virtual time (TVT) is predetermined by an initiator who then detects when GVT TVT. This approach eliminates the avalanche effect because the collection phase is spread out over time, and it allows for regular and timely GVT updates.}, ANNOTE = {Alexander I. Tomlinson (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , Texas 78712); Vijay K. Garg (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:568147}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/568147.html; http://www.ece.utexas.edu/~garg/dist/TR-PDS-1994-009.ps} } @MISC{oai:CiteSeerPSU:572015, TITLE = {International Conference on}, AUTHOR = {Alexander I. Tomlinson and Vijay K. Garg}, YEAR = {1994}, MONTH = JAN # {~24}, ABSTRACT = {This paper develops a method for maintaining global assertions on a network of distributed processes. The global assertion has the form (X N 1 ) + : : : + NM ) K, where X i is a variable which is local to one process in a distributed system and K is a constant. It is assumed that the initial values of all local variables are known and that the global assertion initially holds. This form is more general than the summation form considered in earlier work.}, CITESEER-REFERENCES = {oai:CiteSeerPSU:71684}, ANNOTE = {Alexander I. Tomlinson (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , Texas 78712); Vijay K. Garg (Department of Electrical and Computer Engineering; The University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:572015}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/572015.html; http://www.ece.utexas.edu/~garg/dist/TR-PDS-1994-010.ps} } @INPROCEEDINGS{Tomilinson:1994:MGA, AUTHOR = {A. I. Tomilinson and V. K. Garg}, TITLE = {Maintaining Global Assertions on Distributed Systems}, EDITOR = {N. Balakrishnan}, BOOKTITLE = {Computer systems and education: International conference --- June 1994, Bangalore, India}, PUBLISHER = {Tata McGraw-Hill}, ADDRESS = {pub-TATA-MCGRAW-HILL:adr}, ISBN = {0-07-462044-4}, PAGES = {257--272}, YEAR = {1994}, BIBDATE = {Mon Aug 26 10:38:41 MDT 1996}, ACKNOWLEDGEMENT = {Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|} } @INPROCEEDINGS{1993:pdd:tomlinson, AUTHOR = {Alexander I. Tomlinson and Vijay K. Garg}, TITLE = {Detecting Relational Global Predicates in Distributed Systems}, EDITOR = {B. P. Miller and C. McDowell}, BOOKTITLE = {Proceedings of the {ACM}/{ONR} Workshop on Parallel and Distributed Debugging}, YEAR = {1993}, PAGES = {21--31}, URL = {http://www.acm.org/pubs/articles/proceedings/onr/174266/p21-tomlinson/p21-tomlinson.pdf}, GENTERMS = {ALGORITHMS, RELIABILITY}, CATEGORIES = {D.1.3 Software, PROGRAMMING TECHNIQUES, Concurrent Programming, Distributed programming. D.2.5 Software, SOFTWARE ENGINEERING, Testing and Debugging, Debugging aids.}, ANNOTE = {incomplete} } @INPROCEEDINGS{pads93*35, AUTHOR = {Alexander I. Tomlinson and Vijay K. Garg}, TITLE = {An Algorithm for Minimally Latent Global Virtual Time}, PAGES = {35--42}, ISBN = {1-56555-055-2}, EDITOR = {Rajive Bagrodia and David Jefferson}, BOOKTITLE = {Proceedings of the 7th Workshop on Parallel and Distributed Simulation}, ADDRESS = {San Diego, CA}, MONTH = MAY, YEAR = {1993}, PUBLISHER = {IEEE Computer Society Press} } @INPROCEEDINGS{YouGar:93, BOOKTITLE = {Proc.\ of 32nd {IEEE} Conf.\ Decision and Control}, ADDRESS = {San Antonio, TX, USA}, MONTH = DEC, YEAR = {1993}, AUTHOR = {S. D. Young and V. K. Garg}, TITLE = {On Self-Stabilizing Systems: An Approach to the Specification and Design of Fault Tolerant Systems}, PAGES = {1200--1205} } @INPROCEEDINGS{Gar:93, BOOKTITLE = {Proc.\ of 32nd {IEEE} Conf.\ Decision and Control}, ADDRESS = {San Antonio, TX, USA}, MONTH = DEC, YEAR = {1993}, AUTHOR = {V. K. Garg}, TITLE = {Parallel and Distributed Algorithms for Supervisory Control of Discrete Event Systems}, PAGES = {2236--2241} } @TECHREPORT{oai:CiteSeerPSU:135443, TITLE = {Synchronous Message Passing}, AUTHOR = {V. V. Murty and V. K. Garg}, YEAR = {1993}, MONTH = DEC # {~19}, ABSTRACT = {This paper studies the characteristics of synchronous ordering of messages. Synchronous ordering of messages defines synchronous communication based on the causality relation rather than time. We present the necessary characteristics of any algorithm providing deadlock-free synchronous ordering of the messages. We also present the sufficient conditions, based on the causality relations, for any algorithm to provide synchronous ordering. The paper proposes an algorithm using acknowledgment messages to implement the sufficient conditions. The acknowledgment messages are used to satisfy the causality relation between the events. The algorithm is deadlock-free, and provides a higher degree of concurrency then the algorithms which define synchronous communication based on time. 1 Introduction Distributed programs are difficult to design and test due to their non-deterministic nature. That is, a distributed program may exhibit multiple behaviors on the same external input. This nondetermini...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:145873; oai:CiteSeerPSU:63501}, ANNOTE = {V. V. Murty (Department of Electrical Computer Engineering; University of Texas at Austin; Austin , Texas 78712); V. K. Garg (Department of Electrical Computer Engineering; University of Texas at Austin; Austin , Texas 78712);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:135443}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/135443.html; http://maple.ece.utexas.edu/TechReports/1994/TR-PDS-1994-001.ps.Z} } @ARTICLE{IPL::Garg1992, TITLE = {Some optimal algorithms for decomposed partially ordered sets}, AUTHOR = {Vijay K. Garg}, PAGES = {39--43}, JOURNAL = {Information Processing Letters}, YEAR = {1992}, MONTH = {9~} # NOV, VOLUME = {44}, NUMBER = {1} } @ARTICLE{TCS::GargR1992, TITLE = {Concurrent regular expressions and their relationships to {Petri} nets}, AUTHOR = {Vijay K. Garg and M. T. Ragunath}, PAGES = {285--304}, JOURNAL = {Theoretical Computer Science}, YEAR = {1992}, MONTH = {13~} # APR, VOLUME = {96}, NUMBER = {2} } @INPROCEEDINGS{lncs652*253, AUTHOR = {V. K. Garg and B. Waldecker}, TITLE = {Detection of Unstable Predicates in Distributed Programs}, PAGES = {253--264}, ISBN = {3-540-56287-7}, EDITOR = {Rudrapatna Shyamasundar}, BOOKTITLE = {Proceedings of Foundations of Software Technology and Theoretical Computer Science}, MONTH = DEC, SERIES = {LNCS}, VOLUME = {652}, PUBLISHER = {Springer}, ADDRESS = {Berlin, Germany}, YEAR = {1992} } @INPROCEEDINGS{CofGar:92, BOOKTITLE = {Proc.\ of 31st {IEEE} Conf.\ Decision and Control}, ADDRESS = {Tucson, AZ, USA}, MONTH = DEC, YEAR = {1992}, AUTHOR = {D. D. Cofer and V. K. Garg}, TITLE = {A Timed Model for the Control of Discrete Event Systems Involving Decisions in the Max/Plus Algebra}, PAGES = {3363--3368} } @INPROCEEDINGS{ToHoGa:92, BOOKTITLE = {Proc.\ of 1992 American Control Conf.}, ADDRESS = {Chicago, IL, USA}, MONTH = JUN, YEAR = {1992}, AUTHOR = {A. Tomlinson and G. Hoagland and V. K. Garg}, TITLE = {Distributed Resource Management Using Active Supervisory Predicate Control} } @INPROCEEDINGS{GarKum:92, BOOKTITLE = {Proc.\ of 1992 American Control Conf.}, ADDRESS = {Chicago, IL, USA}, MONTH = JUN, YEAR = {1992}, AUTHOR = {V. K. Garg and R. Kumar}, TITLE = {A State-Variable Approach for Controlling Discrete Event Systems with Infinite States}, PAGES = {2809--2813} } @INPROCEEDINGS{Gar:92b, BOOKTITLE = {Proc.\ of 26th Conf.\ on Information Sciences and Systems}, ADDRESS = {Princeton, NJ, USA}, MONTH = MAR, YEAR = {1992}, AUTHOR = {V. K. Garg}, TITLE = {Probabilistic Languages for Modeling of {DEDS}} } @ARTICLE{GarRag:92, AUTHOR = {V. K. Garg and M. T. Raghunath}, TITLE = {Concurrent Regular Expressions and their Relationship to Petri Net Languages}, JOURNAL = {Theoretical Computer Science}, VOLUME = {96}, YEAR = {1992}, PAGES = {285--304} } @ARTICLE{KuGaMa:92, TITLE = {On supervisory control of sequential behaviors}, AUTHOR = {R. Kumar and V. K. Garg and S. I. Marcus}, JOURNAL = {IEEE Transactions on Automatic Control}, YEAR = {1992} } @ARTICLE{KuGaMa:92b, TITLE = {Predicates and predicate transformers for supervisory control of discrete event systems}, AUTHOR = {R. Kumar and V. K. Garg and S. I. Marcus}, JOURNAL = {IEEE Transactions on Automatic Control}, YEAR = {1992}, NOTE = {to appear} } @ARTICLE{KuGaMa:92c, TITLE = {Stability and stabilizability of behavior of discrete event systems}, AUTHOR = {R. Kumar and V. K. Garg and S. I. Marcus}, JOURNAL = {SIAM Journal of Control and Optimization}, YEAR = {1992}, NOTE = {to appear} } @INPROCEEDINGS{SpYoGa:92ACC, AUTHOR = {D. Spanjol and S. Young and V. K. Garg}, TITLE = {Control of Discrete Event Systems Modeled with Infinite Languages}, BOOKTITLE = {Proc. of 1992 American Control Conference}, ADDRESS = {Chicago, IL}, YEAR = {1992}, MONTH = JUN, BIB = {G} } @MISC{oai:CiteSeerPSU:88007, TITLE = {Concurrent Regular Expressions and their Relationship to Petri Nets}, AUTHOR = {Vijay K. Garg}, YEAR = {1992}, MONTH = JAN # {~21}, ABSTRACT = {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 with four operators - interleaving, interleaving closure, synchronous composition and renaming. This alternative characterization of Petri net languages gives us a flexible way of specifying concurrent systems. Concurrent regular expressions are modular and hence easier to use for specification. The proof of equivalence also provides a natural decomposition method for Petri nets. 1 Introduction Formal models proposed for specification and analysis of concurrent systems can be categorized roughly into two groups: algebra based and transition based. The algebra based models specify all possible behaviors of concurrent systems by means of expressions that consist of algebraic operators and primitive behaviors. Examples of such models are path expressions[3], behavior expressions[21] and extend...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:572604; oai:CiteSeerPSU:169858}, ANNOTE = {Vijay K. Garg (; Department of Electrical and Computer Engineering,; University of Texas; M.T.Raghunath; Computer Science Division,; University of California , Berkeley; ; Austin , TX 78712-1084; Berkeley , CA 94720);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:88007}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/88007.html; http://maple.ece.utexas.edu/~vijay/dist/tcs.ps.Z} } @ARTICLE{journals/cl/GargR91, TITLE = {Con{C}: {A} Language for Concurrent Programming}, AUTHOR = {Vijay K. Garg and C. V. Ramamoorthy}, JOURNAL = {Comput. Lang}, YEAR = {1991}, NUMBER = {1}, VOLUME = {16}, BIBDATE = {2003-11-27}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/cl/cl16.html#GargR91}, PAGES = {5--18} } @INPROCEEDINGS{Waldecker-Garg/91, AUTHOR = {Brian Waldecker and Vijay K. Garg}, TITLE = {Detection of strong predicates in distributed programs}, BOOKTITLE = {Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing, SPDP'91 (Dallas, Texas, December 2-5, 1991)}, PAGES = {692--699}, YEAR = {1991}, PUBLISHER = {IEEE Computer Society Press}, ORGANIZATION = {IEEE Computer Society}, ADDRESS = {Los Alamitos-Washington-Brussels-Tokyo}, CDATE = {1970-01-01}, MDATE = {2005-08-18} } @INPROCEEDINGS{YouGar:91, AUTHOR = {S. Young and V. K. Garg}, TITLE = {Uncertainty in Discrete Event Systems}, BOOKTITLE = {Proc.\ of 6th IEEE Int.\ Symp.\ on Intelligent Control}, YEAR = {1991}, PAGES = {245--250} } @INPROCEEDINGS{KumGar:91, BOOKTITLE = {Proc.\ of 29th Allerton Conf.\ on Communication, Control and Computing}, ADDRESS = {Champaign, IL, USA}, MONTH = OCT, YEAR = {1991}, AUTHOR = {R. Kumar and V. K. Garg}, TITLE = {Optimal Control of Discrete Event Dynamical Systems Using Network Flow Techniques} } @INPROCEEDINGS{KuGaMa:91, AUTHOR = {R. Kumar and V. K. Garg and S. I. Marcus}, TITLE = {Stability of Discrete Event System Behavior}, BOOKTITLE = {Proceedings of 1991 IFAC Symposium on Distributed Intelligent Systems}, YEAR = {1991}, MONTH = AUG, PAGES = {13--18} } @INPROCEEDINGS{KuGaMa:91ACC, AUTHOR = {R. Kumar and V. K. Garg and S. I. Marcus}, TITLE = {On $\omega-$Controllability and $\omega-$Normality of {DEDS}}, BOOKTITLE = {Proc. of 1991 American Control Conference}, ADDRESS = {Boston, MA}, YEAR = {1991}, MONTH = JUN, BIB = {G} } @INPROCEEDINGS{KuGaMa:91d, AUTHOR = {R. Kumar and V. K. Garg and S. I. Marcus}, TITLE = {On Using Predicate Transformers for Supervisory Control}, BOOKTITLE = {Proc. of 31st Conf. Decision and Control}, ADDRESS = {Brighton, United Kingdom}, MONTH = DEC, YEAR = {1991} } @ARTICLE{KuGaMa:91e, AUTHOR = {R. Kumar and V. K. Garg and S. I. Marcus}, TITLE = {On Controllability and Normality of Discrete Event Dynamical Systems}, JOURNAL = {Systems and Control Letters}, YEAR = {1991}, VOLUME = {17}, PAGES = {157--168} } @INPROCEEDINGS{Waldecker91, AUTHOR = {Brian Waldecker and Vijay K. Garg}, TITLE = {Unstable Predicate Detection in Distributed Program Debugging}, BOOKTITLE = {Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging}, PAGES = {276--278}, ADDRESS = {Santa Cruz, California}, MONTH = MAY, YEAR = {1991}, KEYWORDS = {par-debugging bib,}, ABSTRACT = {Extended abstract.} } @INPROCEEDINGS{GarGho90, AUTHOR = {V. K. Garg and J. Ghosh}, TITLE = {Symmetry in Spite of Hierarchy}, PAGES = {4--11}, BOOKTITLE = {Proceedings of the 10th International Conference on Distributed Computing Systems (ICDCS)}, YEAR = {1990}, PUBLISHER = {IEEE Computer Society}, ADDRESS = {Washington, DC}, ISBN = {0-8186-2048-X} } @ARTICLE{BGKLM:90, AUTHOR = {R. D. Brandt and V. K. Garg and R. Kumar and F. Lin and S. I. Marcus and W. M. Wonham}, TITLE = {Formulas for Calculating Supremal and Normal Sublanguages}, JOURNAL = {Systems and Control Letters}, PAGES = {111--117}, YEAR = {1990}, VOLUME = {15}, NUMBER = {8} } @INPROCEEDINGS{KuGaMa:90, TITLE = {Language stability of {DEDS}}, AUTHOR = {R. Kumar and V. K. Garg and S. I. Marcus}, BOOKTITLE = {Proceedings of 1990 International Conference on Mathematical Theory of Control}, ADDRESS = {Indian Institute of Technology, Bombay, India}, YEAR = {1990}, MONTH = DEC } @INPROCEEDINGS{conf/forte/Garg89, TITLE = {Modeling of Distributed Systems by Concurrent Regular Expressions}, AUTHOR = {Vijay K. Garg}, PUBLISHER = {North-Holland}, YEAR = {1989}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/conf/forte/forte1989.html#Garg89}, BOOKTITLE = {FORTE}, EDITOR = {Son T. Vuong}, ISBN = {0-444-88544-7}, PAGES = {313--327} } @UNPUBLISHED{Gar:89, AUTHOR = {V. K. Garg}, TITLE = {{P}etri Nets and Concurrent Regular Expressions}, INSTITUTION = {Univ.\ of Texas at Austin, USA}, NOTE = {Preprint}, YEAR = {1989}, MONTH = APR } @INPROCEEDINGS{KuGaMa:89, TITLE = {Supervisory control of discrete event systems: supremal controllable and observable languages}, AUTHOR = {R. Kumar and V. K. Garg and S. I. Marcus}, BOOKTITLE = {Proceedings of 1989 Allerton Conference}, YEAR = {1989}, PAGES = {501--510}, MONTH = SEP, ADDRESS = {Allerton, IL} } @INPROCEEDINGS{Garg88a, AUTHOR = {V. K. Garg}, TITLE = {Analysis of Distributed Systems with Many Identical Processes}, PAGES = {358--365}, BOOKTITLE = {Proceedings of the 8th International Conference on Distributed Computing Systems (ICDCS)}, YEAR = {1988}, PUBLISHER = {IEEE Computer Society}, ADDRESS = {Washington, DC}, ISBN = {0-8186-0865-X} } @PHDTHESIS{oai:xtcat.oclc.org:OCLCNo/ocm21854261, TITLE = {Specification and analysis of distributed systems with a large number of processes}, AUTHOR = {Vijay Kumar Garg}, YEAR = {1988}, ANNOTE = {University of California; Berkeley.--Dept. of Electrical Engineering and Computer Sciences.}, BIBSOURCE = {OAI-PMH server at alcme.oclc.org}, DESCRIPTION = {Thesis (Ph. D. in Computer Science)--University of California, Berkeley, Nov. 1988.; Bibliography: leaves 189-195.}, OAI = {oai:xtcat.oclc.org:OCLCNo/ocm21854261}, SCHOOL = {University of California, Berkeley, Nov.} } @ARTICLE{IEEETSE::RamamoorthyGP1988, TITLE = {Support for Reusability in Genesis}, AUTHOR = {C. V. Ramamoorthy and Vijay K. Garg and Atul Prakash}, JOURNAL = {IEEE Transactions on Software Engineering}, PAGES = {1145--1154}, MONTH = AUG, YEAR = {1988}, VOLUME = {14}, NUMBER = {8} } @INPROCEEDINGS{ICDCS87*544, AUTHOR = {V. K. Garg and C. V. Ramamoorthy}, TITLE = {Effect of Locality in Large Networks}, PAGES = {544--551}, BOOKTITLE = {7th International Conference on Distributed Computing Systems ({ICDCS} '87)}, ISBN = {0-8186-0801-3}, MONTH = SEP, PUBLISHER = {IEEE Computer Society Press}, ADDRESS = {Washington, D.C., USA}, YEAR = {1987} } @ARTICLE{journals/computer/RamamoorthySG87, TITLE = {Software Development Support for {AI} Programs}, AUTHOR = {C. V. Ramamoorthy and Shashi Shekhar and Vijay K. Garg}, JOURNAL = {IEEE Computer}, YEAR = {1987}, NUMBER = {1}, VOLUME = {20}, BIBDATE = {2002-06-07}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/computer/computer20.html#RamamoorthySG87}, PAGES = {30--40} } @ARTICLE{journals/ac/RamamoorthyPGYB87, TITLE = {Issues in the Development of Large, Distributed, and Reliable Software}, AUTHOR = {C. V. Ramamoorthy and Atul Prakash and Vijay K. Garg and Tsuneo Yamaura and Anupam Bhide}, JOURNAL = {Advances in Computers}, YEAR = {1987}, VOLUME = {26}, BIBDATE = {2002-01-03}, BIBSOURCE = {DBLP, http://dblp.uni-trier.de/db/journals/ac/ac26.html#RamamoorthyPGYB87}, PAGES = {393--443} } @ARTICLE{IEEETSE::RamamoorthyGP1986, TITLE = {Programming in the Large}, AUTHOR = {C. V. Ramamoorthy and Vijay K. Garg and Atul Prakash}, JOURNAL = {IEEE Transactions on Software Engineering}, PAGES = {769--783}, MONTH = JUL, YEAR = {1986}, VOLUME = {12}, NUMBER = {7} } @ARTICLE{Agrawl-Garg84, KEY = {Agrawl \& Garg}, AUTHOR = {Mukul Babu Agrawal and Vijay Kumar Garg}, TITLE = {Dimensional Analysis in Pascal}, JOURNAL = {ACM SIGPLAN Notices}, YEAR = {1984}, MONTH = MAR, VOLUME = {19}, NUMBER = {3}, PAGES = {7--11}, ANNOTE = {Claims dimensional analysis needs extensions to type structure and makes a proposal for extensions to Pascal. 3 references.} } @ARTICLE{Garg:1984:SOH, AUTHOR = {Vijay Kumar Garg}, TITLE = {Screen-oriented highlevel debugger {(SHD)} for {Pascal}}, JOURNAL = {ACM SIG{\-}PLAN Notices}, VOLUME = {19}, NUMBER = {3}, PAGES = {39--41}, MONTH = MAR, YEAR = {1984}, CODEN = {SINODQ}, ISSN = {0362-1340}, BIBDATE = {Sun Dec 14 09:14:42 MST 2003}, BIBSOURCE = {http://portal.acm.org/}, ACKNOWLEDGEMENT = {Nelson H. F. Beebe, Center for Scientific Computing, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|}, CLASSIFICATION = {C6150G (Diagnostic, testing, debugging and evaluating systems)}, CORPSOURCE = {IIT, Kanpur, India}, KEYWORDS = {debugger; high level; interactive programming; Pascal; program debugging; screen oriented}, TREATMENT = {P Practical} } @MISC{oai:CiteSeerPSU:278517, TITLE = {Control of Stochastic Discrete Event Systems Modeled by Probabilistic Languages}, AUTHOR = {Ratnesh Kumar and Vijay K. Garg}, ABSTRACT = {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 supervisory control where the control is exercised by dynamically disabling certain controllable events thereby nulling the occurrence probabilities of disabled events, and increasing the occurrence probabilities of enabled events proportionately. This is a special case of probabilistic supervision{} } @MISC{oai:CiteSeerPSU:323292, TITLE = {On the Fly Testing of Regular Patterms in Distributed Computations}, AUTHOR = {Eddy Fromentin and Michel Raynal and Vijay K Garg}, ANNOTE = {Eddy Fromentin (IRISA Projet ADP , Campus universitaire de Beaulieu , 35042 Rennes Cedex , France); Michel Raynal (IRISA Projet ADP , Campus universitaire de Beaulieu , 35042 Rennes Cedex , France); Vijay K Garg (IRISA Projet ADP , Campus universitaire de Beaulieu , 35042 Rennes Cedex , France);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, DESCRIPTION = {This paper will appear in the proceedings of the 23}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:323292}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/323292.html; http://www.mathematik.uni-kl.de/ftp/pub/Docs/Broadcast/./43.ps.gz} } @TECHREPORT{ercim.inria.publications//RR-2252, PAGES = {13 p.}, TYPE = {Technical Report}, NUMBER = {RR-2252}, INSTITUTION = {Inria, Institut National de Recherche en Informatique et en Automatique}, TITLE = {On the fly testing of regular patterns in distributed computations}, BIBDATE = {April 1, 1994}, AUTHOR = {Eddy Fromentin and Michel Raynal and Vijay K. Garg and Alex Tomlinson}, LANGUAGE = {A} } @TECHREPORT{ercim.inria.publications//RR-2384, PAGES = {19 p.}, TYPE = {Technical Report}, NUMBER = {RR-2384}, INSTITUTION = {Inria, Institut National de Recherche en Informatique et en Automatique}, TITLE = {Expressing and Detecting Control Flow Properties of Distributed Computations}, BIBDATE = {October 1, 1994}, AUTHOR = {Vijay K. Garg and Alex Tomlinson and Eddy Fromentin and Michel Raynal}, LANGUAGE = {A}, ABSTRACT = {Les propri{\'e}t{\'e}s d{'}une ex{\'e}cution r{\'e}partie peuvent \être exprim{\'e}es sur ses {\'e}tats globaux ou bien sur ses flots de contr\ôle. Nous nous int{\'e}ressons dans ce rapport aux propri{\'e}t{\'e}s sur les flots de contr\ôle. Dans un premier temps, est pr{\'e}sent{\'e}e une logique simple (quoique puissante) permettant d{'}exprimer des propri{\'e}t{\'e}s sur les flots de contr\ôle vus comme des s{\'e}quences d{'}{\'e}tats locaux. Au moyen de cette logique, nous pouvons notamment exprimer des propri{\'e}t{\'e}s telles l{'}invariance, les propri{\'e}t{\'e}s s{\'e}quentielles (un flot de contr\ôle satisfait une propri{\'e}t{\'e} s{\'e}quentielle si et seulement si il peut \être mis en correspondance avec un motif d{\'e}crit comme un mot sur un alphabet) et les propri{\'e}t{\'e}s non s{\'e}quentielles (ces propri{\'e}t{\'e}s ne consid{\`e}rent pas qu{'}un seul flot de contr\ôle au m\ême instant). Nous pr{\'e}sentons ensuite un algorithme d{\'e}centralis{\'e} permettant la d{\'e}tection de toute propri{\'e}t{\'e} d{\'e}crite au moyen de cette logique. Cet algorithme, bien que simple en d{\'e}pit de sa puissance d{'}expression, observe l{'}ex{\'e}cution r{\'e}partie sous-jacente en en pr{\'e}servant les flots de contr\ôle (les informations n{\'e}cessaire {\`a} la d{\'e}tection sont transmises dans les messages de l{'}application). 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 expressing general properties on control flows, seen as sequences of local states. Among other properties, we can express invariance, sequential properties (to satisfy such a property a control flow must match a pattern described as a word on some alphabet) and non-sequential properties (these properties are on several control flows at the same time). A decentralized detection algorithm for properties described by this logic is then presented. This algorithm, surprisingly simple despite the power of the logic, observes the underlying distributed computation, does not alter its control flows and uses message tags to carry detection-related information.} } @MISC{oai:CiteSeerPSU:287011, TITLE = {Extremal Solutions of Inequations over Lattices with Applications to Supervisory Control}, AUTHOR = {Ratnesh Kumar and Vijay K. Garg}, YEAR = {0}, MONTH = DEC # {~03}, ABSTRACT = {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 existence of supremal as well as infimal solution of a given system of inequations. Iterative techniques are presented for the computation of the extremal solutions whenever they exist, and conditions under which the termination occurs in a single iteration are provided. These results are then applied for obtaining extremal solutions of various inequations that arise in computation of maximally permissive supervisors in control of logical discrete event systems (DESs) first studied by Ramadge and Wonham. Thus our work presents a unifying approach for computation of supervisors in a variety of situations. Keywords: Fixed points, lattices, inequations, discrete event systems, supervisory control, language theory. 1 Introduction Given a set X and a function f : X ! X, x 2 X is called a fixed p...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:94231; oai:CiteSeerPSU:12283; oai:CiteSeerPSU:51811}, ANNOTE = {Ratnesh Kumar (Department of Electrical Engineering; University of Kentucky; Lexington , KY 40506-0046); Vijay K. Garg (Department of Electrical and Computer Engineering; University of Texas at Austin; Austin , TX 78712-1084);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:287011}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/287011.html; http://www.engr.uky.edu/~kumar/PUBS/fp.ps} } @MISC{oai:CiteSeerPSU:245745, TITLE = {Implementable Failure Detectors in Asynchronous Systems}, AUTHOR = {Vijay K. Garg and J. Roger Mitchell}, YEAR = {0}, MONTH = APR # {~09}, ABSTRACT = {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 can be implemented in an asynchronous system. We provide one such implementation and show its application to fault-tolerant server maintenance problem. 1 Introduction We introduce a failure detector which is implementable in asynchronous systems. The previous work [CT96] has only considered those failure detectors which solve the consensus problem in asynchronous systems. It follows from [FLP85] that these failure detectors are not implementable in asynchronous systems. The failure detector introduced in this paper, called Infinitely Often Accurate detector (IO detector for short), can be implemented efficiently in asynchronous systems. An IO detector requires the detector to satisfy even weaker accuracy then eventually weak accuracy proposed by Chandra and Toueg [CT96]. Intuitively,...}, CITESEER-REFERENCES = {oai:CiteSeerPSU:416345; oai:CiteSeerPSU:534597; oai:CiteSeerPSU:570744; oai:CiteSeerPSU:394466}, ANNOTE = {Vijay K. Garg (Parallel and Distributed Systems Laboratory); J. Roger Mitchell (Parallel and Distributed Systems Laboratory);}, BIBSOURCE = {OAI-PMH server at cs1.ist.psu.edu}, LANGUAGE = {en}, OAI = {oai:CiteSeerPSU:245745}, RIGHTS = {unrestricted}, URL = {http://citeseer.ist.psu.edu/245745.html; http://www.ece.utexas.edu/~garg/dist1/alg.ps} }