%\begin{thebibliography}{99}
@ARTICLE{DIM93,
AUTHOR = "D. Dolev and A. Israeli and S. Moran",
TITLE = "Self-stabilization of dynamic systems assuming only
read/write atomicity",
JOURNAL = "Distributed Computing",
VOLUME = 7,
YEAR = 1993,
PAGES = "3--16"
}
@ARTICLE{AVG96,
AUTHOR = "A. Arora and G. Varghese and M. Gouda",
TITLE = "Constraint satisfaction as a basis for designing
nonmasking fault-tolerance",
JOURNAL = "Journal of High-Speed Networks",
VOLUME = 5,
YEAR = 1996,
PAGES = "1--14"
}
@ARTICLE{DH97,
AUTHOR = "S. Dolev and T. Herman",
TITLE = "Superstabilizing protocols for dynamic distributed systems",
JOURNAL = "Chicago Journal of Theoretical Computer Science",
VOLUME = 3,
NUMBER = 4,
YEAR = 1997
}
@inproceedings{DJPV98,
author = "A. K. Ditta and C. Johnen and F. Petit and V. Villain",
title = "Self-stabilizing
depth-first token circulation
in arbitrary rooted networks",
booktitle = {Proceedings of SIROCCO'98, International Colloquium
on Structural Information and Communication Complexity},
year = 1998
}
@inproceedings{KPBG94,
author = "M. Karaata and S. Pemmaraju and S. Bruell and S. Ghosh",
title = "Self-stabilizing algorithms for finding centers
and medians of trees (brief announcement)",
booktitle = {Proceedings of PODC'94, Thirteenth ACM
Symposium on Principles of Distributed Computing},
publisher={ACM Press},
year = 1994,
pages = 374
}
@book{H85,
author = "C. A. R. Hoare",
title = "Communicating
Sequential Processes",
publisher = {Prentice Hall},
year = 1985 }
@inproceedings{dfrost94a,
author = "D. Frost and R. Dechter",
title = "In
search of best search: {An} empirical evaluation",
booktitle = "AAAI-94: Proceedings of the Twelfth National Conference
on Artificial Intelligence",
publisher = "Morgan Kaufmann",
address = "Seattle, Wash.",
pages = "301--306",
year = "1994"
}
@ARTICLE{afek,
AUTHOR = "Y. Afek and Y. Matias",
TITLE = "Elections in anonymous networks",
JOURNAL = "Information and Computation",
VOLUME = 113,
YEAR = 1994,
PAGES = "312--330"
}
@misc{jagota-private,
AUTHOR = "A. Jagota",
TITLE = "Private communication",
YEAR = "December, 1996",
}
@inproceedings{angluin,
author = "D. Angluin",
title = "Local and global properties in networks of
processes",
booktitle = {Proceedings
of the 12th Annual ACM Symposium on Theory of Computing},
publisher={ACM Press},
year = 1980,
pages = {82--93}
}
@inproceedings{ramamathan,
author = "R. Ramanathan and E. L. Lloyes",
title = "Scheduling
algorithms for multi-hop
radio networks",
booktitle = {Proceedings of the SIGCOMM'92, Communication
Architectures and Protocols},
publisher={ACM Press},
year = 1992,
address = "New York",
pages = {211--222}
}
@ARTICLE{KP1,
KEY = "katzpeled1",
AUTHOR = "S. Katz and D. Peled",
TITLE = "Interleaving set temporal logic",
JOURNAL = "Theoretical Computer Science",
VOLUME = 75,
YEAR = 1990,
PAGES = "263--287"
}
@ARTICLE{lesser,
AUTHOR = "V. R. Lessr",
TITLE = "An overview of {DAI}: {V}iewing distributed
{AI} as distributed search",
JOURNAL = "Japanese Society for Artificial Intelligence",
VOLUME = "5(4)",
YEAR = 1990,
}
@ARTICLE{KP2,
KEY = "katzpeled2",
AUTHOR = "S. Katz and D. Peled",
TITLE = "Verification of distributed programs using
representative interleaving sequences",
JOURNAL = "Distributed Computing",
VOLUME = 6,
YEAR = 1992,
PAGES = "107--120"
}
@ARTICLE{KP3,
KEY = "katzpeled3",
AUTHOR = "S. Katz and D. Peled",
TITLE = "Defining conditional independence using collapses",
JOURNAL = "Theoretical Computer Science",
VOLUME = 101,
YEAR = 1992,
PAGES = "337--359"
}
@incollection{Hinton,
author = "G. E. Hinton and T. J. Sejnowski",
title = "Learning and relearning in Boltzman machines ",
booktitle = " Parallel Distributed Processing: Explorations in the Microstructure of Cognition I",
editor = {J. L. McClelland, D. E. Rumelhart},
publisher= "MIT Press",
address= "Cambridge",
year = 1986
}
@incollection{mackworth-ency,
author = "A. Mackworth",
title = "Constraint
Satisfaction",
booktitle = "Encyclopedia of Artificial Intelligence",
editor = "S. Shapiro",
publisher= "Wiley",
address={New York},
year = {1991},
pages = {285--292}
}
@incollection{dechter-ency,
author = "R. Dechter",
title = "Constraint
Networks",
booktitle = "Encyclopedia of Artificial Intelligence",
editor = "S. Shapiro",
publisher= "Wiley",
year = {1991},
address={New York},
pages = {276--285}
}
@incollection{Kumar-rao,
author = "V. Kumar and V. N. Rao",
title = "Scalable
parallel formulations of depth first search",
booktitle = "Parallel Algorithms for Machine Intelligence and Vision",
editor = {V. Kumar and P. S. Gopalakrishnan and L. Kanal},
publisher= "Springer-Verlag",
year = {1990},
pages = {1--41}
}
@incollection{zhang,
author = "Y. Zhang and A. Mackworth",
title = "Parallel
and distributed finite constraint
satisfaction: {C}omplexity, algorithms and experiments",
booktitle = "Parallel Algorithms for Machine Intelligence and Vision",
editor = {L. N. Kanal and V. Kumar and H. Kitano and C. B. Suttner},
publisher= "Elsevier",
address={Amsterdam},
year = {1994},
pages = {1--41}
}
@techreport{Ballard,
author = "D. H. Ballard and P. C. Gardner and M. A. Srinivas",
title = "Graph problems and connectionist architectures",
institution = {University of Rochester},
address = {Rochester, N.Y.},
number = 167,
month = {March},
year = 1986
}
@inproceedings{BGW,
author = "J. Burns and M. Gouda and C. L. Wu",
title = "A
self-stabilizing token system",
booktitle = {Proceedings of the 20th Annual International Conference
on System Sciences},
address = {Hawaii},
publisher= {Western Periodicals},
year = 1987,
pages = {218--223}
}
@inproceedings{Collin,
author = "Z. Collin and R. Dechter",
title = "A
Distributed solution to the network consistency problem",
booktitle = {Proceedings of the 5th International Symposium on
Methodologies for Intelligent Systems.},
address = {Tennessee, USA},
year = 1990,
pages = {242--251}
}
@inproceedings{CDK:feasibility,
author = "Z. Collin and R. Dechter and S. Katz",
title = "On
the Feasibility of Distri\-buted Constraint Satisfaction",
booktitle = {Proceedings of IJCAI-91},
address = {Sydney, Australia},
publisher= {Morgan Kaufmann},
year = 1991
}
@techreport{collin:full,
author = "Z. Collin and R. Dechter and S. Katz",
title = "Self-stabilizing
distributed constraint satisfaction",
institution = {Information and Computer Science (R15b)},
note={www.ics.uci.edu/{\allowbreak}$\sim$dechter/{\allowbreak}publications/R15},
year = 1994
}
%\bibitem{F:Collin}
%Z. Collin,
%R. Dechter, and
%S. Katz
%``Boundaries of distributed constraint satisfaction,''
%Technion report, in preparation.
@ARTICLE{CD:dfs,
AUTHOR = "Z. Collin and S. Dolev",
TITLE = "Self-stabilizing depth-first search",
JOURNAL = "Information Processing Letters",
VOLUME = "49",
PAGES = "297--301",
YEAR = 1994
}
@inproceedings{Dahl,
author = "E. D. Dahl",
title = "Neural
network algorithms for an NP-Complete problem:
{M}ap and graph coloring",
booktitle = "Proceedings of the IEEE First International Conference
on Neural Networks",
address = "San Diego",
year = 1987,
pages = {113--120}
}
@inproceedings{DD:belief,
author = "R. Dechter and A. Dechter",
title = "Belief
maintenance in dynamic constraint networks",
booktitle = "Proceedings AAAI-88",
address = "St. Paul, Minn.",
publisher= {Morgan Kaufmann},
month = {August},
year = 1988,
pages = {37--42}
}
@article{DD:belief1,
author = "R. Dechter and A. Dechter",
title = "Structure driven algorithms for truth maintenance",
journal = "Artificial Intelligence Journal",
vol = "82",
year = "1996",
pages = {1--20}
}
@article{D:enhancement,
author = "R. Dechter",
title = "Enhancement Schemes for Constraint Processing:
{B}ackjumping, Learning, and Cutset Decomposition",
journal = "Artificial Intelligence Journal",
volume = 41,
number = 3,
month = {January},
year = 1990,
pages = {273--312}
}
@inproceedings{Hopfield-82,
author = "J. J. Hopfield",
title = "Neural
networks and physical systems with emergent
collective computational abilities",
booktitle = "Proceedings of the National Academy of Science ",
volume = 79,
year = 1982,
pages = {2554--2558}
}
@inproceedings{Kasif1,
author = " S. Kasif and J. Reif and D. Sherlekar",
title = "Formula
Dissection: {A}
Parallel Algorithm for Constraint Satisfaction",
booktitle = "Proceedings of the 1987 IEEE Workshop on Computer Architecture for Pattern",
year = 1987,
pages = {51--58}
}
@article{Kasif2,
author = "S. Kasif and D. Delcher",
title = " Local
Consistency in Parallel Constraint Networks",
journal = "Artificial Intelligence",
volume={69},
number={1--2},
pages={307--327},
year = 1994
}
@inproceedings{sellman,
author = "B. Selman and H. J. Levesque and D. G. Mitchell",
title = "A
new method for solving hard satisfiability problems",
booktitle = "AAAI-92",
address = {San Jose, Calif.},
publisher= {Morgan Kaufmann},
year = 1992,
pages = {440--446}
}
@inproceedings{pinkas-dechter,
author = "G. Pinkas and R. Dechter ",
title = "An improved connectionist activation for energy minimization",
booktitle = "AAAI-92",
address = {San Jose, Calif.},
publisher= {Morgan Kaufmann},
year = 1992,
pages = {434--439}
}
@article{pinkas-91,
author = "G. Pinkas",
title = "Energy minization and the satisfiability of propositional calculus",
journal = "Neural Computation",
volume = 3,
number = 2,
year = 1991,
pages = {282--291}
}
@inproceedings{morris,
author = "P. Morris",
title = "The
breakout method for escaping from local minima",
booktitle = "AAAI-93",
address = {San Jose, Calif.},
publisher= {Morgan Kaufmann},
year = 1993,
pages = {40--45}
}
@article{Hopfield-85,
author = "J. J. Hopfield and D. W. Tank",
title = "Neural computation of decisions in optimization problems",
journal = "Biological Cybernetics",
volume = 52,
year = 1985,
pages = {144--152}
}
@article{Dijkstra,
author = "E. W. Dijkstra",
title = "Self-stabilizing systems in spite of distributed control",
journal = "Communications of the ACM",
volume = 17,
number = 11,
year = 1974,
pages = {643--644}
}
@inproceedings{Dolev,
author = "S. Dolev and A. Israeli and S. Moran",
title = "Self
stabilization of dynamic systems
assuming only read/write atomicity",
booktitle = "Proceedings of PODC-90",
address = "Quebec City",
month = {August},
year = 1990,
pages = {103--118}
}
@book{Even,
author = "S. Even",
title = "Graph
Algorithms",
publisher = "Computer Science Press",
address = "Rockville, Md.",
year = 1979
}
@article{Freuder,
author = "E. C. Freuder",
title = "A Sufficient Condition for Backtrack-Free Search",
journal = "Journal of the ACM",
volume = 29,
number = 1,
month = {January},
year = 1982,
pages = {24--32}
}
@article{Finkel,
author = "R. Finkel and U. Manber",
title = "Scalable parallel formulations of depth-first search",
journal = "ACM Transactions on Programming Languages and Systems",
volume = 9,
year = 1987,
pages = {235--256}
}
@techreport{FQ:lineal,
author = "E. C. Freuder and M. J. Quinn",
title = "The use of lineal spanning trees to represent
constraint satisfaction problems",
institution = "University of New Hampshire",
address = "Durham, N.H.",
number = {87--41},
year = 1987
}
%\bibitem{FQ:parallelism}
%E. C. Freuder and
%M. J. Quinn,
%``Parallelism in algorithms that take advantage of stable sets
%of variables to solve constraint satisfaction problems,''
%University of New Hampshire,
%Durham, New Hampshire,
%Tech. Rep. 85-21,
%January, 1985
@article{Gusgen1,
author = "H. W. Guesgen and J. Hertzberg",
title = "Some fundamental properties of local constraint propagation",
journal = {Artificial Intelligence Journal},
volume = 36,
number= 2,
year = 1988,
pages= {237--247}
}
%\bibitem{Haralick}
%R. M. Haralick and
%G. L. Elliott,
%``Increasing Tree-search Efficiency for Constraint
%Satisfaction Problems,''
%{\em Artificial Intelligence Journal},
%Vol 14,
%1980
%pp 263-313
@article{Korach,
author = "E. Korach and D. Rotem and N. Santoro",
title = "Distributed Algorithms for Finding Centers and Medians in
Networks",
journal = "ACM Transactions on Programming Languages and Systems",
volume = 6,
number = 3,
month = {July},
year = 1984,
pages = {380--401}
}
@article{Mackworth,
author = "A. K. Mackworth",
title = "Consistency in Networks of Relations",
journal = "Artificial intelligence",
volume = 8,
number = 1,
year = 1977,
pages = {65--73}
}
@article{MF:complexity,
author = "A. K. Mackworth and E. C. Freuder",
title = "The Complexity of Some Polinomial Network Consistency
Algorithms for Constraint Satisfaction Problems",
journal = "Artificial intelligence",
volume = 25,
year = 1985,
pages = {65--74}
}
@inproceedings{Minton,
author = "S. Minton and M. D. Johnston and A. B. Philips and P. Laird",
title = "Solving
large scale constraint satisfaction
and scheduling problems using a heuristic repair method",
booktitle = "Proceedings of AAAI-90",
volume = 1,
address = "Boston",
year = 1990,
publisher= {Morgan Kaufmann},
pages = {17--24}
}
%\bibitem{Rossi}
%F. Rossi and
%U. Montanari,
%``Exact solution of networks of constraints using perfect relaxation,''
%{\em Proceedings of the first Intl. Conf.
%on Principles of Knowledge Representation and Reasoning},
%Toronto, Canada:
%1989
@inproceedings{Yokoo,
author = "M. Yokoo and T. Ishida and K. Kuwabara",
title = "Distributed
constraint satisfaction for DAI problems",
booktitle = {Proceedings of AAAI Spring Symposium on Constraint-based reasoning},
address = {Palo Alto},
year = 1991,
pages = {191--199}
}
@inproceedings{Yokoo1,
author = "M. Yokoo and E. H. Durfee and T. Ishida and K. Kuwabara",
title = "Distributed
constraint satisfaction for formalizing
distributed problem solving",
booktitle = {IEEE 12th International Conference on Distributed Computing Systems},
year = 1992,
pages = {614--621}
}
@inproceedings{Yokoo2,
author = "M. Yokoo",
title = "Asynchronous
weak commitment search for solving
distributed constraint satisfaction problems",
booktitle = {First International Conference on Constraint
Programming},
address = {France},
publisher= {Springer-Verlag},
year = 1995,
}
@inproceedings{Gusgen,
author = "H. W. Guesgen",
title = "Connectionist
networks for constraint satisfaction",
booktitle = {Proceedings of AAAI Spring Symposium on Constraint-based reasoning},
address = {Palo Alto},
year = 1991,
pages = {182--190}
}
@inproceedings{Holldobler,
author = "S. Holldobler",
title = "Constraint satisfaction in a connectionist inference system",
booktitle = {Proceedings of AAAI Spring Symposium on Constraint-based reasoning},
address = {Palo Alto},
year = 1991,
pages = {200--208}
}
@article{Schneider,
author = "M. Schneider",
title = "Self-stabilization",
journal = "ACM Computing Surveys",
volume = 25,
number = 1,
month = {March},
year = 1993,
pages = {45--67}
}
%\end{thebibliography}
@INPROCEEDINGS{DH95a,
AUTHOR = "S. Dolev and T. Herman",
TITLE = "Superstabilizing
protocols for dynamic distributed systems",
BOOKTITLE = "Proceedings of the Second Workshop on Self-Stabilizing Systems",
PAGES = "3.1--3.15",
YEAR = 1995
}
@INPROCEEDINGS{GGHP96,
AUTHOR = "S. Ghosh and A. Gupta and T. Herman and S. V. Pemmaraju",
TITLE = "Fault-containing
self-stabilizing algorithms",
BOOKTITLE = "Proceedings of the Fifteenth Annual ACM Symposium on Principles
of Distributed Computing",
publisher= {ACM Press},
YEAR = 1996,
PAGES = "45--54"
}
@ARTICLE{GK93a,
AUTHOR = "S. Ghosh and M. H. Karaata",
TITLE = "A self-stabilizing algorithm for coloring
planar graphs",
JOURNAL = "Distributed Computing",
VOLUME = 7,
YEAR = 1993,
PAGES = "55--59"
}
@INPROCEEDINGS{GGKP95,
AUTHOR = "S. Ghosh and A. Gupta and M. H. Karaata and S. V. Pemmaraju",
TITLE = "Self-stabilizing
dynamic programming algorithms on trees",
BOOKTITLE = "Proceedings of the Second Workshop on Self-Stabilizing Systems",
PAGES = "11.1--11.15",
YEAR = 1995
}
@ARTICLE{K79,
AUTHOR = "H. S. M. Kruijer",
TITLE = "Self-stabilization (in spite of distributed
control) in tree-structured systems",
JOURNAL = "Information Processing Letters",
VOLUME = 8,
YEAR = 1979,
PAGES = "91--95"
}
@ARTICLE{CYH91,
AUTHOR = "N. S. Chen and H. P. Yu and S. T. Huang",
TITLE = "A self-stabilizing algorithm for constructing
spanning trees",
JOURNAL = ipl,
VOLUME = 39,
YEAR = 1991,
PAGES = "147--151"
}
@ARTICLE{HC92,
AUTHOR = "S. T. Huang and N. S. Chen",
TITLE = "A self-stabilizing algorithm for constructing
breadth-first trees",
JOURNAL = ipl,
VOLUME = 41,
YEAR = 1992,
PAGES = "109--117"
}