CSbib.bib
@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}
}
This file has been generated by
bibtex2html 1.66