%From dechter@ramat-aviv.ics.uci.edu Tue Jul 6 15:19:37 1999
%Date: Fri, 18 Jun 1999 10:36:55 -0700
%From: Rina Dechter
%To: simon@cs.uchicago.edu
%Cc: dolev@cs.bgu.ac.il
%Subject: paper.tex
\documentclass[12pt]{article}
\usepackage{graphicx}
%proof
\usepackage{latexsym} %for Box symbol
\def\QED{$\Box$}
\newenvironment{proof}
{\begin{trivlist}\item[\hskip\labelsep{\textbf{Proof\,}}]}
{\leavevmode\unskip\nobreak\quad\hspace*{\fill}\QED\end{trivlist}}
%ital operators
\def\operator#1{\mathop{\it#1}\nolimits}
\newcommand{\parent}{{\operator{parent}}}
\newcommand{\children}{{\operator{children}}}
\newcommand{\ancestors}{{\operator{ancestors}}}
\newcommand{\predecessors}{{\operator{predecessors}}}
\newcommand{\descendants}{{\operator{descendants}}}
\newcommand{\mode}{{\operator{mode}}}
\newcommand{\Domain}{{\operator{Domain}}}
\newcommand{\tag}{{\operator{tag}}}
\newcommand{\pointer}{{\operator{pointer}}}
\newcommand{\direction}{{\operator{direction}}}
\newcommand{\domain}{{\operator{domain}}}
\newcommand{\Value}{{\operator{value}}}
\newcommand{\val}{{\operator{val}}}
\newcommand{\setofnodes}{{\operator{set\_of\_nodes}}}
\newcommand{\Root}{{\operator{root}}}
\newcommand{\Dim}{{\operator{dim}}}
\newcommand{\shrink}[1]{}
\newcommand{\tree}{minimally labeled tree}
\newcommand{\lm}[1]{\mbox{$\ell_{#1}$}}
\newcommand{\pl}[1]{\wp({#1})}
%\setlength{\textwidth}{5.2in} % for 12pt
%\setlength{\textheight}{8.5in} % for 12pt
%\setlength{\topmargin}{0in} % for 12pt
%\setlength{\headheight}{0in}
%\setlength{\headsep}{0in}
% DELIMITER PAIRS AND MATHEMATICAL FUNCTIONS
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\card}[1]{\left| #1\right|}
\newcommand{\ord}[1]{O\left( #1\right)}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\ang}[1]{\left\langle #1 \right\rangle}
\newcommand{\prob}[1]{\Pr\left\{ #1 \right\}}
% BINARY OPERATION, RELATION, AND ARROW SYMBOLS
\newcommand{\propsubset}
{\stackrel{\subset}{\scriptscriptstyle \not {\scriptstyle =}}}
\newcommand{\dhrightarrow}{\rightarrow \hspace*{-15pt} \rightarrow}
\renewcommand{\gets}{\leftarrow}
\newcommand{\manyone}{\leq_{\rm m}}
\newcommand{\turing}{\leq_{\rm T}}
\newcommand{\encode}[1]{\langle #1 \rangle}
% OTHER MATHEMATICAL SYMBOLS OR CONSTRUCTS
\newcommand{\cents}{\hbox{\rm\rlap/c}}
\newcommand{\half}{\frac{1}{2}}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qed}{\hspace*{\fill}
\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}\smallskip}
% THEOREM-LIKE ENVIRONMENTS
\newtheorem{lemma}{Lemma}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{claim}[lemma]{Claim}
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{proposition}[lemma]{Proposition}
% PROGRAM-LIKE ENVIRONMENT
% #1 - label_name #2 - caption_name #3 - text
\newcommand{\Tabs}{xxx\= xxx\= xxx\= xxxx\= xxxx\= xxxx\= xxxx\= xxxx\= xxxx\= xxxx\= xxxx\= \kill}
\newenvironment{program}[3]{\begin{figure*}[hbtp]
\begin{center}
\fbox{
\begin{minipage}{\textwidth}
\begin{tabbing}
\Tabs
#3
\end{tabbing}
\end{minipage}
}
\end{center}
\caption{#2}
\label{#1}
\end{figure*}}{}
% MACROS FOR ALGORITHMS OR PROGRAMS
\newcommand{\Backward}{\mbox{\sc backward}}
\newcommand{\Forward}{\mbox{\sc forward}}
\newcommand{\True}{\mbox{\sc true}}
\newcommand{\False}{\mbox{\sc false}}
\newcommand{\On}{\mbox{\sc on}}
\newcommand{\Off}{\mbox{\sc off}}
%\input{psfig}
\title{Self-stabilizing Distributed Constraint Satisfaction}
\author{Zeev Collin\\
Computer Science Department\\
The Technion\\Haifa, Israel\\
zeev@cs.technion.ac.il
\and
Rina Dechter\\
Department of Information
and Computer Science\\
University of California\\
Irvine, California, USA\\
dechter@ics.uci.edu
\and
Shmuel Katz\\
Computer Science Department\\
The Technion\\
Haifa, Israel\\
katz@cs.technion.ac.il
}
\date{31 December 1999}
\begin{document}
%%
%% CJTCS frontmatter, Insert after \begin{document}
%%
\def\registered{\({}^{\ooalign%
{\hfil\raise.07ex\hbox{{\tiny\textup{R}}}%
\hfil\crcr\scriptsize\mathhexbox20D\cr}}\)}
\begin{titlepage}
\pagenumbering{roman}
\null\vfil\vskip 60pt
\begin{center}
{\Huge\bf Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science\par}
\vskip 3em
{\huge\it The MIT Press\par}
\end{center}
\par\vskip 1.5em
{\Large
\begin{center}
Volume 1999, Article 10\\
\textit{Self-stabilizing Distributed Constraint Satisfaction}
\end{center}
}
\par\noindent
ISSN 1073--0486. MIT Press Journals, Five Cambridge Center, Cambridge, MA
02142-1493 USA; (617)253-2889;
\emph{journals-orders@mit.edu, journals-info{\allowbreak}@mit.edu}.
Published one article at a time in \LaTeX\ source form on the
Internet. Pagination varies from copy to copy. For more
information and other articles see
\begin{itemize}
\item \emph{http://mitpress.mit.edu/CJTCS/}
\item \emph{http://www.cs.uchicago.edu/publications/cjtcs/}
\item \emph{ftp://mitpress.mit.edu/pub/CJTCS}
\item \emph{ftp://cs.uchicago.edu/pub/publications/cjtcs}
\end{itemize}
\par\noindent
The \emph{Chicago Journal of Theoretical Computer Science} is
abstracted or indexed in \emph{
Research Alert\registered,
SciSearch\registered,
Current Contents\registered/Engineering
Computing \& Technology}, and \emph{CompuMath Citation Index\registered.}
\par\noindent\copyright 1999 The Massachusetts Institute of Technology.
Subscribers are licensed to use journal articles in a variety of
ways, limited only as required to ensure fair attribution to authors
and the journal, and to prohibit use in a competing commercial
product. See the journal's World Wide Web site for further
details. Address inquiries to the Subsidiary Rights Manager, MIT
Press Journals; (617)253-2864;
\emph{journals-rights@mit.edu}.\pagebreak[2]
\par\noindent The \emph{Chicago Journal of Theoretical Computer Science}
is a peer-reviewed scholarly journal in theoretical computer
science. The journal is committed to providing a forum for
significant results on theoretical aspects of all topics in computer
science.
\par
\begin{trivlist}
\item[\emph{Editor-in-Chief:}] Janos Simon
\item[\emph{Consulting Editors:}]
Joseph Halpern, Eric Allender, Raimund Seidel
\item[\emph{Editors:}]
\begin{tabular}[t]{lll}
Martin Abadi & Greg Frederickson & John Mitchell \\
Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\
Eric Allender & Georg Gottlob & Gil Neiger \\
Tetsuo Asano & Vassos Hadzilacos & David Peleg \\
Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\
Eric Bach & Maurice Herlihy & James Royer \\
Stephen Brookes & Ted Herman & Alan Selman \\
Jin-Yi Cai & Stephen Homer & Nir Shavit \\
Anne Condon & Neil Immerman & Eva Tardos \\
Cynthia Dwork & Howard Karloff & Sam Toueg \\
David Eppstein & Philip Klein & Moshe Vardi \\
Ronald Fagin & Phokion Kolaitis & Jennifer Welch \\
Lance Fortnow & Stephen Mahaney & Pierre Wolper \\
Steven Fortune & Michael Merritt
\end{tabular}
\vspace{1ex}
\item[\emph{Managing Editor:}] Michael J.\ O'Donnell
\vspace{1ex}
\item[\emph{Electronic Mail:}] \emph{chicago-journal@cs.uchicago.edu}
\end{trivlist}
\vfil\null
\end{titlepage}
\maketitle
\pagenumbering{arabic}
%%
%% End frontmatter code
%%
%\input{title}
\maketitle
\begin{abstract}
Distributed
architectures and
solutions are described for classes of
constraint satisfaction problems, called {\em network
consistency problems}.
An inherent assumption of these architectures
is that the communication
network mimics the structure of the constraint problem.
The solutions are required to
be self-stabilizing and to treat arbitrary networks,
which makes them suitable
for dynamic or error-prone environments.
We first show that
even for relatively simple constraint networks,
such as rings,
there is no self-stabilizing solution that guarantees convergence
from every initial state of the system using a completely
uniform, asynchronous model (where all processors are identical).
An {\em almost uniform}, asynchronous,
network consistency protocol with one specially designated
node is shown and proven correct.
We also show that some restricted topologies such as trees can
accommodate the uniform, asynchronous model when neighboring
nodes cannot take simultaneous steps.
\end{abstract}
\section{Introduction}
\label{introduction_sec}
Consider the distributed version of the graph coloring problem,
where each node must select a color (from a given set) that
is different from any color selected by
its neighbors. This NP-complete
problem belongs to the
class of {\em constraint satisfaction
problems} (csp's), which present interesting challenges
to distributed computation.\footnote{Obviously,
there is no
connection to Hoare's CSP (communicating
sequential processes) notation \cite{H85}.}
We call the distributed versions of this class of problems
{\em network consistency problems}. Since constraint satisfaction
is inherently intractable for the general case, the interesting questions
for distributed models are those of feasibility rather
than efficiency.
We wish to answer the following main question: What types
of distributed models admit a self-stabilizing algorithm,
namely, one that converges to a solution, if such exists,
from any initial state of the network?
For models that do admit solutions, we present and prove the
correctness of appropriate algorithms that converge to a solution
for any specific problem.
The motivation for addressing this question stems from
attempting to solve constraint satisfaction problems in
environments that are inherently distributed. For instance,
an important family of constraint satisfaction problems in
telecommunications involves scheduling transmissions in radio networks
\cite{ramamathan}.
A radio network is a set of $n$ stations
that communicate by broadcasting and receiving signals.
Typical examples of radio networks are packet radio networks
and satellite networks. Every station has
a transmission radius.
The {\em broadcast scheduling problem} involves scheduling broadcast
transmissions from different stations in an interference-free
way. In the time-division multiplexing
version, there is a fixed set of time slots,
and each station must assign itself one time slot
such that any two stations that are within the transmission radius
of each other are assigned different time slots.
The frequency-division multiplexing version is similar, with
the fixed set of time slots replaced by a fixed set of
frequencies.
One can easily see that the problem translates naturally
to a graph coloring problem where broadcasting radios are
the nodes in the graph and any two nodes are connected
if and only if their
transmission radii overlap.
Solving the broadcasting scheduling problem autonomously
and distributedly by the
radio stations themselves is highly desirable
because the environment is inherently distributed:
In some applications (e.g., in a military setting, when the radios
are moving) no central
control is feasible or practical. Moreover, a self-stabilizing
distributed solution
has the important virtue of being fault tolerant.
Another motivating area, distributed artificial intelligence (DAI),
has become very popular in recent years \cite{lesser}.
The issue addressed is problem solving
in a multiagent environment where
agents have to
cooperate to solve a problem and to carry out its solution
in a distributed manner.
As in the broadcast scheduling problem,
the distributed environment
is a physical necessity rather than a programmer's design choice.
One possible architecture considered for solving the network
consistency problem is neural networks.
Such networks perform distributed computation
with uniform units and are normally
self-stabilizing.
However, current connectionist approaches
to constraint problems
\cite{Ballard,Dahl}
lack theoretical guarantees of
convergence to a solution,
and the conditions under which such convergence can be guaranteed
(if at all) have not been systematically explored.
This paper aims to establish such guarantees by
studying the feasibility of solving
a csp in uniform, self-stabilizing distributed architectures.
Intuitively, a distributed algorithm is {\em self-stabilizing}
\cite{Dijkstra} if it converges to a solution
from any initial state of both the network and the algorithm.
Our aim is to determine what types of distributed models
admit self-stabilizing algorithms and,
whenever possible, to present such an algorithm.
Self-stabilization is a desirable property
since it yields robustness
in the face of dynamically changing environments.
This is especially true if the solution treats any network configuration
and, thus, within some time after a change to the network,
converges to a solution.
Some changes can be imposed externally
(e.g., adding new components to the problem,
changing the values of variables or buffers);
others may occur to the system
internally,
by errors in the implementing hardware.
The accepted model we use for self-stabilization \cite{Dijkstra}
treats the part of the computation
from after a perturbation to the next perturbation as a
normally executing algorithm with abnormal initial values, including
control locations. The implicit assumption is
that perturbations occur infrequently, so that the system
stabilizes and does most of its work in consistent states.
In this paper, we
characterize
architectures that allow a self-stabilizing distributed solution
for classes of
constraint satisfaction problems, and we present algorithms when possible.
As noted above, the self-stabilization can model dynamically changing
constraint networks as well as transient network perturbations, thus
increasing the robustness of the solutions.
Following some background on constraint networks
and self-stabilization (Section 2) we show
that {\em uniform} networks, in which all
nodes run identical procedures and any scheduling policy is allowed,
cannot admit algorithms that
guarantee convergence to a consistent solution from
any initial state using an asynchronous model
(Section 3).
In Section 4, we depart slightly from uniformity
by allowing one unit to execute a different algorithm.
We call this model {\em almost uniform} and use it to
present an asynchronous,
network consistency protocol.
It combines a subprotocol to generate a depth-first search
(DFS) spanning tree, with a
value-assignment subprotocol. The value assignment exploits the potential
parallelism of the spanning tree, using a special form of backtracking
appropriate for constraint problems.
In Section 5, we show that some restricted topologies, such as trees, can
accommodate the uniform, asynchronous model.
Preliminary versions of some of these results first appeared in
\cite{CDK:feasibility}.
\section{Background}
\label{model_sec}
\subsection{Constraint networks}
A csp
is defined over
a {\em constraint network} that
consists of a finite set of {\it variables},
each associated with a {\it domain}
of values, %$D_{1} ,\ldots ,D_{n},$
and a set of {\it constraints}. %, $\{C_{1}, \ldots ,C_{t}\}$.
A {\em solution} is an assignment of a value to each variable
from its domain such that all the constraints are satisfied.
Typical constraint satisfaction problems
are to determine whether
a solution exists, to find one or all solutions,
and to find an optimal solution relative to a given cost function.
An example of a constraint satisfaction problem
is the $k$-colorability problem mentioned in the
introduction. The problem is to color, if possible,
a given graph with $k$ colors only, such that
any two adjacent nodes have different colors.
A constraint satisfaction formulation
of this problem associates the nodes of the graph with variables,
the possible colors are their domains,
and the inequality constraints
between adjacent nodes are the constraints of the problem.
Each constraint of a csp may be expressed as a relation, defined on
some subset of variables, denoting their legal combinations of
values.
In addition, constraints can be described by mathematical
expressions or by computable procedures.
The structure of a constraint network is depicted by a constraint
graph whose nodes represent the variables and in which any two
nodes are connected if the corresponding variables
participate in the same constraint.
In the $k$-colorability formulation,
the graph to be colored is the constraint graph.
Constraint networks have proven successful in
modeling mundane cognitive tasks such as vision, language comprehension,
default reasoning, and abduction, as well as in applications such as
scheduling, design, diagnosis, and temporal
and spatial reasoning.
In general, constraint satisfaction tasks
are computationally intractable (NP-hard).
Techniques for processing constraints
can be classified into two categories \cite{dechter-ency}:
(1) search
and (2) consistency inference,
and these techniques interact.
Search algorithms traverse the space of
partial instantiations, while consistency-inference algorithms
reason through equivalent problems.
Search is either systematic and complete, or
stochastic and incomplete. Likewise, consistency-inference
has complete solution algorithms (e.g., variable-elimination)
or incomplete versions in the form
of {\em local consistency} algorithms. Let us state this formally.
\begin{definition}
A {\em network of binary constraints}
is a set of $n$ variables
$X= \{X_1, \dots , X_n \}$, a domain $D_i$ of possible values for
each variable $X_i$, $ 1 \leq i \leq n$, and a set of constraints
$R_{S_1},\ldots,R_{S_t}$, where $S_i \subseteq X$.
A {\em binary constraint}, denoted $R_{ij}$ over two
variables $X_i$ and $X_j$, is
a subset of the product of their domains,
$R_{ij} \subseteq D_i \times D_j$.
A {\em solution} is an assignment of a value to each variable,
$x \bar = (x_1,\ldots,x_n)$, $x_i \in D_i$, such that
$\forall i,j$, $1 \leq i,j \leq n, ~(x_i,x_j) \in R_{ij}$.
A {\em constraint graph} has a node for each variable
and links connecting pairs of variables that appear in the same
constraint.
\end{definition}
General constraint satisfaction problems may involve
constraints of any arity,
but since network communication is only pairwise we
focus on this subclass of problems.
Figure \ref{CSP_fig}a presents a csp constraint graph,
where each node represents a variable having values $\set{a,b,c}$,
and each link is associated with a strict lexicographic order
($X_i\prec X_j$ in the lexicographic order if and only if $i 1)$.
Since convergence to a solution is guaranteed
from any initial configuration,
the protocol also converges when initially
all nodes are in identical states.
We construct a fair execution of such a protocol that satisfies
the restriction on the scheduler but
for which the network never converges to a consistent solution,
contradicting the self-stabilization property of the protocol.
Assume the following execution:
\[
\begin{array}{lllll}
P_0, & P_q, & P_{2q}, & \ldots , & P_{(r-1)q}, \\
P_1, & P_{q+1}, & P_{2q+1},& \ldots , & P_{(r-1)q+1}, \\
\vdots \\
P_{q-1}, & P_{2q-1}, & P_{3q-1},& \ldots , & P_{rq-1}, \\
P_0, & \ldots \\
\vdots
\end{array}
\]
Note that nodes $P_0, P_q, P_{2q}, \ldots ,P_{(r-1)q}$
move to identical states
after their first activation,
because their inputs, initial states,
and transition functions are identical, and when each one of them is
activated its neighbors are in identical states too.
The same holds for any sequential activation of processors
$\{ P_{iq+j} |~0 \! \leq \! i \! < \! r,~0 \! \leq \! j \! < \! q \}$.
Thus, cycling through the above schedule
assures that $P_0$ and $P_q$, for instance,
move to identical states over and over again,
an infinite number of times.
Since a consistent solution requires their states
to be different, the network never reaches a consistent solution,
thus yielding a contradiction.
Figure \ref{ring_fig} demonstrates such a counterexample execution for
a ring with six nodes.
The indicated nodes are scheduled in each configuration.
Different colors refer to different states.
\end{proof}
\begin{figure}[tbh]
\begin{center}
\includegraphics[scale=.8]{aring_fig.eps}
%\makebox[442pt][l]{
% \vbox to 106pt{
% \vfill
% \special{psfile=ring_fig.ps}
% }
% \vspace{-\baselineskip}
%}
\end{center}
\caption{The ring ordering problem ($n=6$)}
\label{ring_fig}
\end{figure}
Theorem \ref{impossibility} is proven above
for a centralized scheduler, but as noted earlier it holds also for a
distributed scheduler.
This theorem means that
it is generally impossible to guarantee convergence to a consistent
solution using a uniform protocol if no additional restrictions are made
on the possible executions.
In particular, convergence cannot be guaranteed for a class of
sequential algorithms using ``repair'' methods, as in
\cite{Minton}, if a completely random order of repair is allowed.
It does not, however, exclude the possibility
of uniform protocols for restricted scheduling policies
or for special network topologies (not including a ring).
In practice it is fair to assume that adversarial
scheduling policies are not likely to occur or can be deliberately
avoided.
When using a distributed scheduler,
convergence (to a solution) cannot
be guaranteed even for {\em tree networks}.
Consider, for instance, the coloring problem
in a tree network constructed from two connected nodes,
each having the domain \{{\sc black, white}\}.
Since the two nodes are topologically identical,
if they start from identical
initial states and both of them are activated simultaneously,
they can never be assigned different values
and will never converge to a legal
solution, although one exists.
This trivial counterexample can be extended to a large class
of trees, where there is no possible way to distinguish
between two internal nodes.
However, we show (Section \ref{tree_sec})
that for a central scheduler, a uniform self-stabilizing
tree network consistency protocol does exist.
Having proven that the network consistency problem cannot
always
be solved by
using a uniform protocol, even with a central scheduler,
we switch to a slightly more relaxed
model of an {\em almost uniform} protocol,
in which all nodes but one are identical.
We denote the special node as node 0 (or $P_0$).
Note that such a special processor can be determined by finding
a leader in a distributed network. Thus, if a leader could be elected
uniformly, it could be used to convert our almost uniform protocol
to a uniform one.
Since we cannot solve the consistency problem for a central scheduler
with an almost uniform protocol, it follows from our
impossibility result (as is well known \cite{angluin})
that a leader cannot be elected in
an arbitrary anonymous (where all processors are identical)
network.
However, randomization can be used to break the symmetry and to elect
a leader in uniform networks
\cite{afek}.
\section{Consistency-generation protocol}
\label{protocol_sec}
This section presents an almost uniform, self-stabilizing
network consistency protocol.
The completeness of this protocol (i.e., the guarantee of converging
to a solution if one exists) stems from the completeness of the
sequential constraint satisfaction algorithm it simulates.
It can accommodate changes to constraints, as long as the
resulting graph is connected and includes the special
node (or one can be elected using randomization).
We briefly review some basic sequential techniques for constraint
satisfaction.
\subsection{Sequential aspects of constraint satisfaction}
The most common algorithm for solving a csp is {\em backtracking}.
In its standard version, the algorithm traverses the
variables in a predetermined order, provisionally assigning consistent
values to a subsequence $(X_1 ,\ldots , X_i)$ of variables and
attempting to append to it a new instantiation of $X_{i+1}$ such
that the whole set is consistent ({\em forward} phase).
If no consistent assignment can be found for the next variable
$X_{i+1}$, a dead-end situation occurs; the algorithm
backtracks to the most
recent variable ({\em backward} phase),
changes its assignment, and continues from there.
A useful improvement of backtracking,
{\em graph-based backjumping} \cite{D:enhancement},
consults the topology of the constraint
graph to guide its backward phase. Specifically,
instead of going back to the
most recent variable instantiated,
it {\em jumps back} several levels to the first variable connected
to the dead-end variable.
If the variable to which the algorithm retreats has no more values,
it backs up further, to the most
recent variable among those connected either to the original variable
or to the new dead-end variable, and so on.
It turns out that when using a depth-first search (DFS)
on the constraint graph (to generate a DFS spanning tree) and then
conducting backjumping in a preorder traversal of the DFS tree
\cite{Even},
the jump-back destination of variable $X$
is the parent of $X$ in the DFS spanning tree \cite{dechter-ency}.
The nice property of a DFS spanning tree
that allows a parallel implementation
is that any arc of the graph that is not
in the tree connects
a node to one of its tree ancestors (i.e., to a node residing
along the path leading to it from the root).
Consequently, the DFS spanning tree represents a useful decomposition of the
graph: If a variable $X$ and all its ancestors in the tree are removed
from the graph, the remaining subtrees rooted at the children of
$X$ are disconnected.
Figure \ref{CSP_fig}b presents a DFS spanning tree of the constraint graph
presented in Figure \ref{CSP_fig}a. Note that if $X_2$ and its
ancestor $X_1$ are removed from the graph,
the network becomes
two disconnected trees rooted at $X_3$ and $X_5$.
This translates to a problem decomposition
strategy: If all ancestors of
variable $X$ are instantiated, then the solutions of all its subtrees
are completely independent and can be performed in parallel
\cite{FQ:lineal}.
\subsection{General protocol description}
\label{general_desc}
The distributed version of the binary csp
is called the network consistency (NC) problem.
Our network consistency protocol is
based on a distributed version of graph-based backjumping
implemented on a
variable ordering generated by a depth-first traversal
of the constraint graph.
The NC protocol
is logically composed of two self-stabilizing subprotocols
that can be executed interleaved,
as long as one self-stabilizes for any configuration, and then
establishes a condition guaranteeing the self-stabilization of
the second \cite{DIM93}. The subprotocols are as follows:
\begin{enumerate}
\item DFS spanning tree generation
\item value assignment (using the graph traversal mechanism)
\end{enumerate}
The second subprotocol assumes the existence of a DFS spanning
tree in the network.
However, the implementations of
these subprotocols are unrelated to each other and, thus,
can be independently
replaced by any other implementation.
Until the first subprotocol establishes a DFS spanning tree,
the second subprotocol executes but, in all likelihood,
does not lead to a proper assignment of values.
%SSS
We use a self-stabilizing DFS spanning tree
protocol that is described in \cite{CD:dfs}.
The spanning tree protocol
is not affected by the interleaved second subprotocol,
and thus the existence of a DFS spanning tree is eventually guaranteed.
The convergence of the second subprotocol is also guaranteed
starting from any configuration
and assuming the existence of a DFS spanning tree (which is not
changed by continued operation of the first subprotocol).
Therefore, the combination is guaranteed to converge properly after the
DFS spanning tree is completed.
The basic idea of the second subprotocol is to
decompose the network (problem) logically
into several independent subnetworks (subproblems),
according to the DFS spanning tree structure, and to instantiate these
subnetworks (solve the subproblems) in parallel.
Proper control over value instantiation is guaranteed by the
graph traversal mechanism presented in Section \ref{graph_traversal}.
We would like to emphasize that using graph-based backjumping
rather than naive backtracking as the sequential basis for
our distributed implementation is crucial for the success of
our protocol.
First, naive backtracking leads naturally to algorithms in
which only one processor executes at a time.
Second, it requires a total ordering of the processors
generally encoded in their identifiers.
Moreover, unless the nodes that are consecutive
in the backtracking order are connected in the communication
graph, passing activation from one node to another when going forward
or upon a dead end seems
feasible only when using node
identifiers.
Algorithm graph--based backjumping uses a partial order
that is derived from the DFS spanning tree,
thus providing more opportunities for parallelism
and eliminating the need for node identifiers.
\subsection{Self-stabilizing DFS spanning tree generation protocol}
\label{dfs_section}
First we describe an almost uniform,
self-stabilizing protocol for generating a DFS spanning tree.
The full algorithm was described in
\cite{CD:dfs} and, thus, is not described in
detail or proven here.
Alternative self-stabilizing algorithms for generating a DFS
spanning tree could be used instead and may yield a better space
complexity, as discussed in Section \ref{space}.
This subprotocol is
the source of nonuniformity for the whole NC protocol.
The root of the
generated tree is the distinguished node 0 ($P_0$).
Each processor, $P_i$, has (at most) one adjacent processor, $\parent(i)$,
designated as its {\em parent} in the tree,
and a set of {\em child} processors, $\children(i)$.
The set of the processors
that reside along the path from the root to $P_i$ in the
DFS spanning tree is denoted by $\ancestors(i)$, while
$\descendants(i)$ is the set of processors $P_j$ so that $P_i$
is in $\ancestors(j)$.
The set of $P_i$'s neighboring processors that are in $\ancestors(i)$,
except the parent of $P_i$, are called $P_i$'s
predecessors and are denoted by $\predecessors(i)$.
Figure \ref{neighborhood_fig} indicates the environment of
an internal processor. The $\ancestors(i)$ set is empty if $i$ is
the root, while the $\descendants(i)$ set is empty if $i$ is a leaf.
\begin{figure}[tbh]
\begin{center}
\includegraphics{afig2a.eps}
%\makebox[351pt][l]{
% \vbox to 117pt{
% \vfill
% \special{psfile=fig2a.ps}
% }
% \vspace{-\baselineskip}
%}
\end{center}
\caption{The neighborhood set of $i$ in a DFS-marked graph}
\label{neighborhood_fig}
\end{figure}
The links of every processor $P$ are divided
into the following categories (see Figure \ref{neighborhood_fig}):
\begin{enumerate}
\item {\em Tree-edges} are the edges that belong to the DFS spanning tree.
\begin{enumerate}
\item {\em Inlink} is the edge that connects $P$ to its parent.
Every nonroot processor has one such link and the root has none.
\item {\em Outlinks} are the edges that connect $P$
to its children.
\end{enumerate}
\item {\em Backward edges} are the edges that connect $P$ to its
predecessors.
\item {\em Descendant edges} are the edges that connect $P$ to its
descendants, excluding its children.
\end{enumerate}
A distributed graph is called {\em DFS-marked}
if there is a DFS spanning tree over the graph such that
every processor in the system can
identify the category of each of its adjacent edges with relation
to this DFS spanning tree.
Each node has a local
numbering (ranking) of its edges.
During the execution of the protocol the special node 0,
which plays the role of the root, repeatedly assigns itself the label $\perp$
(the minimal element)
and suggests labels to its neighbors.
The label suggested to $j$ by its neighbor $i$ is constructed by concatenating
$i$'s ranking of the edge from $i$ to $j$ to the right of $i$'s own label.
Thus a label is a sequence of elements, each of which is
the minimal element or an edge rank.
Labels are compared using
lexicographic order. The sequence in a label has a fixed maximal length,
and the concatenation can lead to ``overflow'' where
the leftmost element is removed (and this is needed for convergence).
Every nonroot node chooses the smallest label suggested to it
to be its label and the suggesting neighbor to be its parent,
and suggests labels to its neighbors in a similar way.
The communication register between $i$ and $j$ contains the following
fields used by the DFS spanning tree generation protocol:
\begin{description}
\item[{$r_{ij}.\mbox{\it mark}$}] contains
the label that is ``suggested''
to $j$ by $i$.
\item[{$r_{ij}.\mbox{\it par}$}] is a boolean field that is set to
\True\ if and only if
$i$ chooses $j$ as its parent.
\end{description}
The output of the DFS spanning tree algorithm,
after the network has converged, is a
DFS-marked graph maintained in a distributed fashion.
\subsection{Value assignment subprotocol}
\label{graph_traversal}
The second subprotocol assumes the existence of a DFS spanning tree in
the network; namely, each nonroot node has a designated
parent, children, and predecessors among its neighboring nodes
(see Figure \ref{neighborhood_fig}).
When the DFS spanning tree generation subprotocol stabilizes,
each node has a minimal label and a designated parent.
Using this information, each node can compute its children set,
$\children(i)$, by selecting the neighbors whose
$r_{ji}.\mbox{\it par}$ field
is true, and its predecessors set, $\predecessors(i)$,
by selecting the neighbors whose minimal label ($r_{ji}.\mbox{\it mark}$
without the last character) is a prefix of its own.
This means that we can traverse the directed tree either
toward the leaves or toward the root.
The value assignment subprotocol presents a graph traversal mechanism that
passes control to the nodes in the order of the value assignment
of the variables (in DFS order), without losing the parallelism gained by
the DFS structured network.
Section \ref{activation} presents the basic idea of {\em privilege passing}
that implements the graph traversal mechanism,
while Section \ref{assignment} presents
the value assignment strategy that guarantees convergence to a solution.
Each node $i$ (representing the variable $X_i$)
has a list of possible values, denoted as $\Domain_{i}$,
and a pairwise relation $R_{ij}$ with each neighbor $j$.
The domain and the constraints may be viewed as a part of
the system or as inputs that are always valid (though they
can be changed during the execution, forcing the network
to readjust itself to the changes).
The state register of each node contains the following fields:
\begin{description}
\item[{$\Value_i$}] is a field to which it assigns
one of its domain values or the symbol ``$\star$''
(to denote a dead end).
\item[{$\mode_i$}] is a field indicating
the node's ``belief'' regarding the status of the network.
A node's mode is \On\
if the value assignment of itself or one of its ancestors
has changed since the last time it was in a forward phase
(to be explained in Section \ref{assignment});
otherwise it is \Off.
The modes of all nodes also give
an indication of whether they
have reached a consistent state
(all in an \Off\ mode).
\item[{\rm$\parent\_\tag$ and $\children\_\tag$}] are
two boolean fields
used for the graph traversal
(Section \ref{activation}).
\end{description}
Additionally, each node has a sequence set of domain values that
is implemented as an ordered list
and is controlled by a local domain {$\pointer$}
(to be explained later), and a local {$\direction$} field
indicating whether the algorithm is in its
forward or backward phase.
\subsubsection{Graph traversal using privileges}
\label{activation}
The graph traversal is handled by a self-stabilizing
{\em privilege passing mechanism}, according to which
a node obtains the privilege to act,
granted to it either by
its parent or by its children.
A node is allowed to change its state
only if it is privileged.
Our privilege passing mechanism is an extension of
a mutual exclusion protocol for two nodes
called {\em balance-unbalance} \cite{Dijkstra,DIM93}.
Once a DFS spanning tree is established,
this scheme is implemented by
having every state register
contain two fields: $\parent\_\tag$, referring
to its inlink
and $\children\_\tag$, referring to all its outlinks.
A link is {\em balanced} if the $\children\_\tag$
and the $\parent\_\tag$ on its endpoints have the same value,
and the link is {\em unbalanced} otherwise.
A node becomes privileged if its inlink
is unbalanced and {\em all} its outlinks are balanced.
In other words, the following two conditions must be satisfied
for a node $i$ to be privileged:
\begin{enumerate}
\item
$\parent\_\tag_{i} \neq \children\_\tag_{\parent(i)}$
(the inlink is unbalanced)
\item
$\forall k \in \children(i) :
\, \children\_\tag_{i} = \parent\_\tag_{k}$
(the outlinks are balanced)
\end{enumerate}
By definition, we consider the inlink of the root to be
unbalanced and the outlinks of the leaves to be balanced.
A node applies the value assignment subprotocol
(described in Section \ref{assignment})
only when it is privileged;
otherwise it leaves its state unchanged.
As part of the execution of the subprotocol, the node passes the privilege.
The privilege can be passed backward to the
parent by balancing the inlink
or forward to the
children by unbalancing the outlinks
(i.e., by changing the value of
$\parent\_\tag$ or $\children\_\tag$, respectively).
We use the following notation to define the set of configurations
that are legally controlled relative to the graph traversal:
\begin{itemize}
\item Denote a {\em chain} to be a maximal sequence of unbalanced links,
$e_{1}, e_{2} \ldots,\allowbreak e_{n}$, such that the
following are true:
\begin{enumerate}
\item The inlink of the node whose outlink is $e_{1}$
is balanced, unless the node is the root.
\item Every adjacent pair of links $e_{i}, e_{i+1}~(1\leq i < n)$
is an inlink and an outlink, respectively,
of a common node.
\item All the outlinks of the node whose inlink is $e_{n}$
are balanced.
\end{enumerate}
\item The chain begins at the node with $e_{1}$ as one of its
outlinks, denoted as the {\em chain head},
and ends at the node with the inlink $e_{n}$,
denoted as the {\em chain tail}.
\item Denote a {\em branch} to be a path from the root to a leaf.
\item A branch {\em contains} a chain
(or a chain is {\em on} the branch) if
all the links of the chain are in the branch.
\item A configuration is {\em legally controlled} if
it does not contain any nonroot chain heads,
namely, every branch of
the tree contains no more than one chain and its
chain head is the root.
\end{itemize}
Figure \ref{legal_conf_fig} shows a
legally controlled configuration. The DFS spanning tree edges are directed,
and the values ($+$ or $-$)
of the $\parent\_tag$ and the $\children\_tag$ of every node
are specified above and below the node, respectively.
The privileged nodes are black.
In a legally controlled configuration, a node and its ancestors
are not privileged at the same time and therefore
cannot reassign their values simultaneously.
The privileges travel backward and forward along the branches.
We prove (Section \ref{correctness_sec}) that, using the graph traversal
mechanism, the network eventually converges
to a set of legally controlled configurations
that are also legal with respect to the network
consistency task.
\begin{figure}[tbh]
\begin{center}
\includegraphics[scale=.95]{afig3.eps}
%\makebox[397pt][l]{
% \vbox to 101pt{
% \vfill
% \special{psfile=fig3.ps}
% }
% \vspace{-\baselineskip}
%}
\end{center}
\caption{Legally controlled configuration}
\label{legal_conf_fig}
\end{figure}
Once it has become privileged, a node cannot tell
where the privilege came from
(i.e., from its parent or from its children).
Thus, a node uses its $\direction$ field to indicate
the source of its privilege.
Since during the legally controlled period
no more than one node is privileged on every branch,
the privileges travel along the branches backward and forward.
The $\direction$ field of each node
indicates the direction of the next expected wave.
When passing the privilege to its children, the node assigns
its $\direction$ field the \Backward\ value,
expecting to get the privilege back during the next backward wave,
while when passing the privilege
to its parent it assigns the \Forward\ value,
preparing itself for the next forward wave.
Thus, upon receiving the privilege again, it is able to
recognize the direction it came from:
if $\direction = \Backward$, the privilege was recently
passed toward the leaves, and therefore
it can come only from its children;
if $\direction = \Forward$, the privilege was recently
passed toward the root, and therefore it can come only from its parent.
The value of the $\direction$ field can be improper upon the
initialization of the system. However, after the first time a node
passes the privilege, its $\direction$ field remains properly updated.
Figure \ref{priv-proc} presents the privilege passing procedures for node $i$.
\begin{program}{priv-proc}{Privilege passing procedures}{\small
procedure {\bf pass-privilege-to-parent} \\
\small Begin \\
\small 1.\>
\small $\direction_{i} \gets$ \Forward \>\>\>\>\>\>\>\>
\small \{ prepare for the next wave \}\\
\small 2.\>
\small $\parent\_tag_{i} \gets \children\_tag_{\parent(i)}$\>\>\>\>\>\>\>\>
\small \{ balance inlink \} \\
\small End. \\
\\
\small procedure {\bf pass-privilege-to-children} \\
\small Begin \\
\small 1.\>
\small $\direction_{i} \gets$ \Backward \>\>\>\>\>\>\>\>
\small \{ prepare for the next wave \}\\
\small 2.\>
\small $\children\_tag_{i} \gets
\small \neg \parent\_tag_{k\in \children(i)}$\>\>\>\>\>\>\>\>
\small \{ unbalance outlinks \} \\
\small End.}
\end{program}
\subsubsection{Value assignment}
\label{assignment}
The value assignment has forward and backward phases,
corresponding to the two phases of the
sequential backtracking algorithm.
During the forward phase, nodes
in different subtrees assign themselves (in parallel)
values consistent with their predecessors
or verify the consistency of their assigned values.
When a node senses a dead end (i.e., it has no consistent value
to assign), it assigns
its $\Value$ field a $\star$ and initiates a backward phase.
Since the root has no ancestors, it does not check
consistency and is never dead-ended. It only assigns a new value
at the end of a backward phase, when needed,
and then initiates a new forward phase.
When the network is consistent (all the nodes are in an \Off\ mode),
the forward and backward phases continue, where
the forward phase is used to verify the consistency of the network,
while the backward phase just returns the privilege to the root
to start a new forward wave. Once consistency
is violated, the node sensing the violation relative to its predecessors
moves to an \On\ mode and
initiates a new value assignment.
A more elaborate description follows.
An internal node can be in one of three situations:
\begin{itemize}
\item
{Node {$i$} is activated
by its parent, which is in an \On\ mode}
(this is the forward phase of value assignments).
In that case, some change of value in one of
its predecessors might have occurred.
It therefore
finds the first value in its domain that is
consistent with all its predecessors,
puts itself in \On\ mode, and passes
the privilege to its children.
If no consistent value exists,
it assigns itself the $\star$ value
(a dead end) and passes the privilege
to its parent (initiating a backward phase).
\item
{Node {$i$} is activated by its
parent, which is in an \Off\ mode}
(this is the forward phase of consistency verification).
In that case, it
verifies the consistency of its current value with
its predecessors.
If it is consistent, it stays in (or moves to) an \Off\ mode
and passes the privilege
to its children. If not, it tries to find the next value in its
domain that is consistent with all its predecessors,
and continues as in the previous case.
A leaf, having no children, is always activated by its parent
and always passes the privilege back to its parent
(initiating a backward phase).
\item
{Node {$i$} is activated by its children}
(backward phase).
If one of the children has a $\star$ value,
$i$ selects the next value in its domain that is
consistent with all its predecessors,
and passes the privilege back to its children.
If no consistent value is available,
it assigns itself a $\star$ and passes the privilege
to its parent.
If all children have a consistent value, $i$
passes the privilege to its parent.
\end{itemize}
Due to the privilege passing mechanism, when a parent sees
one of its children in a dead end, it still has to wait until {\em all}
of them have given it the privilege. This is done to
guarantee that all subtrees have
a consistent view regarding their predecessors' values.
%ccc adding:
This requirement limits the amount of parallelism considerably.
It can be relaxed in various ways to allow more
parallelism.
%ccc
The algorithms performed by a nonroot node ($i \neq 0$)
and the root once they become privileged
and after reading the neighbors' states are presented in Figures
\ref{update} and \ref{procedures}.
%\input{protocol}
\begin{program}{update}{Value assignment subprotocols
for root and nonroot nodes}{
\footnotesize {\bf root 0:} \\
\footnotesize Begin \\
%1. \>
\footnotesize if $\exists k \! \in \! \children(0): \; \Value_{k} = \star$ then \\
\footnotesize 1. \>
\footnotesize if $\neg${\bf consistent($\Value_0,\children(0)$)} then \\
\footnotesize 2. \> \>
\footnotesize $\mode \gets$ \On \\
\footnotesize 3. \> \>
\footnotesize $\Value \gets$ {\bf next-value} \\
\footnotesize 4. \>
\footnotesize else\> \> \> \> \>
\footnotesize \{ all children are consistent \} \\
\footnotesize 5. \> \>
\footnotesize $\mode \gets$ \Off\ \\
\footnotesize 6. \>
\footnotesize {\bf pass-privilege-to-children} \\
\footnotesize End. \\
\\
\footnotesize {\bf\boldmath nonroot $i$:} \\
\footnotesize Begin \\
\footnotesize 1. \>
\footnotesize if $\direction$ = \Forward\ then \>\>\>\>\>\>\>
\footnotesize \{ forward phase \}\\
\footnotesize 2. \> \>
\footnotesize if $\mode_{\parent(i)} =$ \On\ then \>\>\>\>\>\>
\footnotesize \{ a change in a value assignment occurred \} \\
\footnotesize 3. \> \> \>
\footnotesize $\pointer \gets 0$ \>\>\>\>\>
\footnotesize \{ reset domain pointer \}\\
\footnotesize 4. \> \>
\footnotesize else \> \> \> \> \> \>
\footnotesize \{ parent's mode is \Off \} \\
\footnotesize 5. \> \> \>
\footnotesize if {\bf consistent($\Value_i,\predecessors(i)$)} then \\
\footnotesize 6.\> \> \> \>
\footnotesize $\mode \gets$ \Off \\
\footnotesize 7. \>
\footnotesize if $(\pointer=0)\vee\neg${\bf consistent($\Value_i,\predecessors(i)$)} $\vee$ \\
\pushtabs
\footnotesize xxx\=
\footnotesize if $(\pointer=0)$\= \kill
\footnotesize \>\>
\footnotesize $\vee (\direction=\Backward\wedge\neg${\bf consistent($\Value_i,\children(i)$)}) then \\
\poptabs
\footnotesize 8.\> \>
\footnotesize $\Value \gets$ {\bf compute-next-consistent-value} \\
\footnotesize \> \> \> \> \> \> \> \> \>
\footnotesize \{ privilege passing \}\\
\footnotesize 9.\>
\footnotesize if {\bf leaf($i$)} $\vee\; (\Value=\star )\vee (\direction=\Backward\ \wedge$
\footnotesize {\bf consistent($\Value_i,\children(i)$)}) \\
\footnotesize 10.\>\>
\footnotesize then {\bf pass-privilege-to-parent} \\
%\pushtabs
%xxxx\= if $(leaf(i)\vee value=\star\vee (direction=\Backward\wedge
%children-consistent))$ \= then \kill
\footnotesize 11.\>\>
\footnotesize else {\bf pass-privilege-to-children} \\
%\poptabs
\footnotesize End. }
\end{program}
The procedure {\em compute-next-consistent-value} (Figure \ref{procedures})
tests each value
located after the domain pointer for consistency.
More precisely, the domain value is checked against each of
$\predecessors (i)$'s values, and the next domain value consistent
with the values of the predecessors is returned.
The pointer's location is readjusted accordingly
(i.e., to the found value), and the mode of the node is set to \On.
If no consistent value is found, the
value returned is $\star$ and the pointer is reset to the beginning
of the domain.
The predicate {\em consistent($\val,\setofnodes$)}
is \True\ if the value of $\val$ is consistent with the $\Value$
fields of $\setofnodes$ and none of them is dead-ended
(has the value $\star$).
%Following are the procedures for processor $P_i$
%(we assume that its domain is implemented as an array $Domain_{i}$):
\begin{program}{procedures}{Consistency procedure}{
procedure {\bf\small compute-next-consistent-value} \\
\small Begin \\
\small 1.\>
\small $\mode_i\gets\On$ \\
\small 2.\>
\small while $\pointer \leq$ endof $\Domain_i$ do \\
\small 3.\> \>
\small $\pointer \gets \pointer+1$ \\
\small 4.\> \>
\small if {\bf
consistent($\Domain_i [\pointer],\; \predecessors(i)$)} then \\
\small 5.\> \> \>
\small return $\Domain_i [\pointer]$ \> \> \> \> \> \>
\small \{ a consistent value was found \} \\
\small 6.\>
\small $\pointer \gets 0$ \\
\small 7.\>
\small return $\star$ \> \> \> \>
\small \{ no consistent value exists \} \\
\small End. \\
}
\end{program}
The algorithm performed by the root $P_0$,
when it is privileged, is
simpler. The root does not check
consistency. All it does is assign a new value
at the end of each backward phase, when needed,
and then initiate a new forward phase.
The procedure {\em next-value} increments the domain pointer's location
and returns the value indicated by the domain pointer.
If the end of the domain list is reached,
the pointer is reset to the first (smallest) value.
The value assignment subprotocol can be regarded as uniform, since each node
may have both the root's protocol and the nonroot's protocol
and decide between them based on the role assigned to
it by the DFS spanning tree protocol.
\subsubsection{Proof of self-stabilization}
\label{correctness_sec}
To prove the correctness of our NC protocol,
we first prove that the graph traversal
is self-stabilizing, namely, that the system
eventually reaches a legally controlled configuration
(even if the values in the nodes are not yet consistent),
and from that point it remains legally controlled.
Assuming the system is legally controlled, we show that if a legal
assignment exists, it is eventually reached and thereafter remains unchanged.
Thus the system reaches a legal set of configurations and stays
there---and therefore is self-stabilizing.
Note that a nonroot node is privileged when its inlink
is unbalanced (thus it is on a chain) and all its outlinks are balanced.
In other words, a nonroot node is privileged if and only if it is a chain tail.
The root is privileged if and only if it is not a chain head.
Also note that passing the privilege by a node affects only the chains
on the branches containing that node, because it has no interaction
with other branches.
To prove the self-stabilization of the privilege passing mechanism,
we first prove some of its properties.
\begin{lemma}
\label{pass-priv}
In every infinite fair execution, every nonroot node
that is on a chain
eventually passes the privilege to its parent.
\end{lemma}
\begin{proof}
We prove the lemma by induction on the node's height, $h$
(i.e., its distance from the nearest leaf),
and on the possible value assignments from the domain of the node.
{\em Base:} $h =0$.
The node is a leaf and, therefore, when activated,
can pass the privilege only to its parent.
{\em Step:} Assume node $i$, whose height is $h>0$,
is on a chain.
Node $i$ eventually becomes privileged because,
if any of $i$'s outlinks are unbalanced,
then the corresponding children are on chains and
the induction hypothesis holds for them,
namely, they eventually pass the privileges to $i$.
Note that a node that passes its privilege to the parent
(to $i$ in our case) does not become privileged again
unless its parent had become privileged first and passed the privilege
to its children, since outlinks are unbalanced
by a privileged node only.
If, when becoming privileged,
$i$ passes the privilege to its parent, the claim is proven.
Otherwise, whenever $i$ passes the privilege
to its children the same argument holds, so $i$ eventually becomes
privileged again.
Moreover, $i$'s domain pointer is advanced
every time it passes the privilege to its children.
Therefore, after a finite number of such passings,
bounded by the size of $\domain_i$,
the domain pointer reaches a $\star$ and then, following the code
in Figures \ref{update} and \ref{procedures}, $i$
passes the privilege to its parent.
\end{proof}
\begin{theorem}
\label{acm}
The graph traversal mechanism is self-stabilizing with respect to the
set of legally controlled configurations.
Namely, it satisfies the following assertions:
\begin{enumerate}
\item {Reachability:}
Starting from any initial configuration, the system eventually
reaches a legally controlled configuration.
\item {Closure:}
If $c$ is a legally controlled configuration and $c \rightarrow c'$,
then $c'$ is also a legally controlled configuration.
\end{enumerate}
\end{theorem}
\begin{proof}
We prove the theorem by showing that all the nonroot chain heads
in the network eventually disappear.
Note that passing a privilege by the root makes the root a chain head
but does not increase the number of nonroot chain heads.
Passing a privilege by any nonroot node does not create any chain head.
When a nonroot node passes the privilege, it is a chain tail
(its outlinks are balanced). Thus, if the
privilege is passed to the node's children, none of them become a chain head
since their parent is still on the same chains.
On the other hand,
if the privilege is passed to its parent, the node balances its inlink,
which cannot possibly create a new chain head.
Thus the number of nonroot chain heads in the network
never increases.
Moreover, Lemma \ref{pass-priv} implies that every nonroot node that is
on a chain, and particularly any nonroot chain head,
eventually passes the privilege to its parent and stops being
a chain head. Therefore, the number of nonroot chain heads steadily
decreases until no nonroot chain heads are left, and hence
the network is legally controlled. Since no nonroot chain heads
are ever created, the network remains legally controlled forever.
\end{proof}
The self-stabilization property of the NC protocol is inherited
from its subprotocols: DFS spanning tree generation and value assignment.
Once the self-stabilization of
privilege passing is established, it assures that the
control is a correct, distributed implementation of
DFS-based backjumping, which guarantees
the convergence of the network to a legal solution,
if one exists, and if not, it repeatedly checks all the possibilities.
\subsection{Complexity analysis}
\label{complexity}
\subsubsection{Time complexity}
A worst-case complexity estimate of the
value assignment subprotocol, once a DFS tree already exists,
can be given by counting the number of state changes until
the network becomes {\em legally controlled} and by adding
to it the
number of state changes before a legal {\em consistent configuration}
is reached.
These two counts bound the sequential performance
of the value assignment protocol and thus, also,
its worst-case parallel time. The bound
is tight since it can be realized when the depth of the DFS tree
equals $n$. In that case only one node is activated at a time.
We next bound the sequential time and
the parallel time, as a function
of the depth of the DFS tree, $m$.
We show that in some cases an optimal speedup
is realizable.
Let $T^1_m$ stand for the maximal
number of privilege passings in the subnetwork
with a DFS spanning subtree of depth $m$,
before its root completes a full round of assigning all of its domain
values (if necessary) and passing the privilege forward to its children for
every assigned value
(for a nonroot node it is the number of privilege
passings in its subtree before the node passes the privilege backward).
Let $b$ be the maximal
branching degree in the DFS spanning tree, and let $k$ bound the domain sizes.
Since every time the root of a subtree becomes privileged,
it either tries to assign a new value or passes the privilege backward,
$T^1_m$ obeys the following recurrence:
\begin{eqnarray*}
T^1_m & = & k \cdot b \cdot T^1_{m-1}, \\
T^1_0 & = & k.
\end{eqnarray*}
Solving this recurrence yields
$T^1_m = b^m k^{m+1}$, which is the worst-case number of privilege
passings before reaching
the legally controlled configuration where only the root is privileged.
The worst-case number of additional state changes toward a consistent
solution (if one exists)
is bounded by the worst-case time of sequential graph-based
backjumping on the DFS tree-ordering.
Let $T^2_m$ stand for the maximal
number of value reassignments in the subnetwork
with a DFS spanning subtree of depth $m$,
before it reaches a solution. This equals
the search space explored by the sequential algorithm.
Since any assignment of a value to the root node generates $b$ subtrees
of depth $m-1$ or less that can be solved independently,
$T^2_m$ obeys the same recurrence as $T^1_m$ and results
in the same expression:
$T^2_m = b^m k^{m+1}$.
Thus, the overall worst-case time complexity
of the value assignment subprotocol is
$T_m = T^1_m+T^2_m = \ord{b^m k^{m+1}}$.
Note that when the tree is balanced, we have
$T_m = \ord{(n/b)\cdot k^{m+1}}$ since $n= O(b^{m+1})$.
Next, we evaluate the parallel time of the value
assignment subprotocol, assuming that the privilege passing mechanism
has already stabilized into legally controlled configurations
(namely, the root is activated).
For this analysis we assume that
the DFS tree is balanced. Clearly, when the tree
is not balanced, the speedup reduces as a function of $b$.
Consider now two cases.
Assume that the network is backtrack-free.
In that case, since there are no dead
ends, the sequential time obeys the recurrence
\begin{eqnarray*}
T^2_m & = &k + b \cdot T^2_{m-1}, \\
T^2_0 & = & 1,
\end{eqnarray*}
yielding
\begin{eqnarray*}
T^2_m &=& b^m + k \cdot (b^{m+1} -1 )/(b-1)\\
&=& O(n/b \cdot k).
\end{eqnarray*}
The parallel time obeys the recurrence
\begin{eqnarray*}
T^2_m & = & k+ T^2_{m-1}, \\
T^2_0 & = & 1,
\end{eqnarray*}
yielding
$T^2_m = m \cdot k +1 $.
The overall speedup in this case is bounded by $n/(b \cdot m)$
where $m = \log_b n$.
Consider now the general case while still assuming that the
tree is balanced.
The sequential complexity, as shown earlier, is $O(n/b \cdot k^{m+1} )$.
In that case, since the subtrees are traversed in parallel,
the parallel complexity obeys the recurrence
\begin{eqnarray*}
T^2_m & = & k \cdot T^2_{m-1}, \\
T^2_0 & = & k,
\end{eqnarray*}
yielding $T^2_m = k^{m+1}$.
In this case a speedup of $(n/b)$ seems realizable.
In summary, we have shown that,
as in the sequential case, our protocol's complexity is
exponentially proportional to the depth
of the DFS spanning tree; that is, the system has a better chance for
a ``quick'' convergence when the DFS spanning tree is of a minimal depth.
There is no gain in speedup when the depth of the tree is $n$.
However, for balanced trees having a depth of $m = log_b n$,
the speedup lies between $n/b$ and $n/(b \cdot m)$.
\subsubsection{Space complexity}
\label{space}
Each node needs to have the information about the constraints
with its neighbors. Assuming that the maximum degree in the
graph is $d$ and since a constraint can be expressed in $O(k^2)$,
each node needs space for $O(d \cdot k^2)$ values.
Among the subprotocols, the DFS subprotocol requires the most
space, $O(n \cdot \log d )$ bits.
Thus there is an overall space requirement for each processor of
$O(n \cdot \log d + d \cdot k^2)$ values, using our subprotocols.
In \cite{DJPV98} a DFS spanning tree can be accomplished
using only $O(\log d)$ space per
node, but the time needed for stabilization may be longer.
In order to store the whole network information, a processor needs
space for $O(n^2 \cdot k^2)$ values, so our distributed treatment is
clearly superior to a centralized solution.
Note that the log encoding common in the analysis of space requirements
may not be feasible in practice for this context, because the
communication registers are fixed, values must be communicated,
and constraints must be changed during execution.
\subsubsection{Speedup of incremental change}
Our model allows adaptation to change without external intervention.
Moreover, in many cases a change may be locally, and thus quickly,
stabilized.
For example, suppose, after the network has converged to a solution,
that the domain of a variable is made smaller by some external event
or that a new constraint
is introduced. If these newly enforced restrictions
are consistent with the current assignment, there is no
change to the solution.
Alternatively, if a current assignment does
not satisfy the new constraint, at least one processor detects
the problem, since it repeatedly checks consistency,
and tries to
choose an alternative value that satisfies
its local environment.
If it succeeds
and if the neighbors are happy with the new assignment,
change stops.
It is clear, however, that in the worst case, local changes
may cause a complete execution of the algorithm
that may be time exponential.
\subsubsection{Adding arc consistency}
The average performance of the NC protocol can be further
improved by adding to it
a uniform self-stabilizing {\em arc consistency}
subprotocol \cite{MF:complexity}.
A network is said to be {\em arc consistent} if,
for every value in each node's domain, there is a consistent value in
all its neighbors' domains.
Arc consistency can be achieved by a repeated execution of
a ``relaxation procedure," where each node reads its neighbors'
domains and eliminates any of its own values for
which there is no consistent value in one of its
neighbors' domains.
This protocol is clearly self-stabilizing,
since the domain sizes are finite,
and they can only shrink or be left intact by each activation.
As a result, after a finite number of steps
all the domains remain unchanged.
Since arc consistency can be applied in a uniform and self-stabilizing
manner,
it suggests that various
constraint propagation methods can be incorporated to
improve backjumping \cite{dfrost94a},
while maintaining properties of self-stabilization.
In particular, the well-known technique of forward checking
can be used along with
arc consistency during
the value assignment subprotocol.
If, as a result, a future variable's domain becomes empty,
that information can be propagated back to the current
privileged variable.
The details and impact of such improvements remain to
be worked out.
\section{Network consistency for trees}
\label{tree_sec}
It is well known that the sequential network consistency problem
on trees is tractable
and can be achieved in linear time \cite{MF:complexity}.
A special algorithm for this task is composed of an arc consistency
phase (explained in the previous section)
that can be efficiently implemented on trees, followed by
a backtrack-free value
assignment in an order created by some {\em rooted tree}.
Since the DFS spanning tree
subprotocol of our general algorithm was the
source of its nonuniformity, we reexamine
the possibility that for trees, a rooted directed tree can be imposed
via a uniform protocol.
We have already shown that when using a distributed scheduler,
a uniform, network consistency protocol for trees is not
feasible. Therefore, the only avenue not yet explored
is whether under a central scheduler such a protocol does exist.
We next show that this conjecture is indeed correct.
In principle a uniform tree consistency (TC) protocol can be extracted from
the general NC protocol by
replacing the DFS spanning tree protocol with a uniform
rooted tree protocol to direct an undirected tree,
since in trees any rooted tree
is a DFS tree.
Since the arc consistency protocol
and the value assignment protocol are already uniform,
the resulting TC protocol is uniform.
Nevertheless, we show that for trees, the value assignment
protocol can be simplified as well, while there is no need
for a special privilege-passing mechanism.
The proposed TC protocol consists of the three subprotocols:
tree directing, arc consistency, and tree value assignment.
When the variables' domains are arc consistent and the tree has
been directed,
value assignment is eventually guaranteed by having each node
follow the rule (of the {\em tree value assignment} protocol),
``Choose a value consistent with your parent's assignment.''
Such a value must exist, since otherwise the
value assigned by the parent would have
been removed by the arc consistency procedure.
Since, as we show,
the tree-directing protocol is self-stabilizing,
and since the arc consistency protocol is self-stabilizing as well,
the value assignment protocol
eventually converges to a consistent solution.
To direct the tree uniformly,
we must exploit the topology of the tree to
break the symmetry reflected by the
identical codes and the lack of identifiers.
For this task we use a distributed protocol
for finding the {\em centers} of a tree \cite{Korach,KPBG94}.
A center of a tree is a node whose maximal distance from
the leaves is minimal.
Consider a sequential algorithm that works in phases, so that in
every phase the leaves of the previous phase are removed from the tree.
In the last phase the tree has either one or two connected
nodes left.
These nodes are the centers of the tree.
Note that if we regard a center as the root of the tree, the children
of every node are removed from the tree in earlier phases than
the node itself (except in the case of two centers that are removed
in the same, last, phase of the algorithm), which means that the
removal phase of a node is greater than the removal phase of
any of its children,
and the removal phase of its parent is greater than
(or, in the case of two centers, equals) its own.
We denote the removal phase of a node in this sequential algorithm
as its {\em level}. The level of the leaves is 0.
Another way to define the level of a node is its maximal
distance to a leaf without passing through a center.
Our protocol distributedly simulates the above algorithm.
If only one center exists,
it declares itself as a root, %(by setting its $root$ field to \True),
and all the incident edges are directed toward it.
When two centers exist, one of them becomes a root
and the link that connects them is directed accordingly.
The choice of which center becomes the root is not deterministic
and depends on the scheduling order and the initial values.
This approach yields a simple,
uniform, tree-directing protocol that simulates the above description.
Every node $i$ has the following fields:
\begin{description}
\item{$l_i$} is the level of $i$,
a variable that eventually
indicates the phase of the sequential algorithm
in which $i$ is removed from the tree.
%(so that $l = 0$ means that $i$ is a leaf in
%the original tree).
\item{$\Root_i$} is a boolean field that indicates whether
$i$ is the root. %Eventually only one of the centers has the value
%\True in this field.
\item{$\parent_i$} is a variable assigned the number
of the edge leading to the neighbor that
becomes the parent of $i$.% (the enumeration is made by the
%$\alpha_i$ function, as in the general protocol, and is local to $i$).
\shrink{
When the network stabilizes, namely, when all the $l$
values converge,
every node except the root has only one neighbor
that is eligible to be its parent,
and no two nodes are parents of each other.
}
\end{description}
The protocol works by having each node repeatedly
compute its own $l$-value by adding 1 to the second-largest value
among the $l$-values of its neighbors.
Each node except the centers ultimately chooses as its parent the neighbor
to which it is still connected whenever it becomes a leaf,
namely, that neighbor whose level is greater than its own.
A node views itself as a center when one of the
following two conditions is satisfied:
\begin{enumerate}
\item
Its $l$-value is greater than all of its neighbors',
which means that it is a single center.
\item
Its $l$-value is equal to that of its largest
neighbor---the other center.
In this case, the node checks whether the other center is already the root.
If so,
it chooses the other center to be
its parent; otherwise
it becomes the root.
\end{enumerate}
Because the $l$-values converge to the correct values of
the level of the node, the above interpretation is ultimately accurate.
Clearly, once the $l$-values converge, each node properly chooses its
parent,
and the direction of the tree is completed. Therefore, it is sufficient
to prove the convergence of the $l$-values to the levels of the nodes.
A proper convergence of the $l$-values can be proved
by induction on the levels
of the nodes.
For more details of the tree-directing algorithm and its proof
see \cite{collin:full}.
The parallel time can be linearly
bounded by the {\em diameter} ($\Dim$) of the tree, where the diameter is
the longest path between any two leaves of the tree.
Since in the worst case the diameter of a tree equals the
number of nodes, $n$, the space that is required in this case to
hold the level of each node is $\ord{\log{\Dim}}$.
A different self-stabilizing tree-directing algorithm is presented
in \cite{pinkas-dechter}.
In that algorithm,
any node of the tree may become the root,
depending on the initial configuration and the schedule.
Although that algorithm is usually better in its space requirements than
the one presented above,
forcing a center to become the root,
as is done here, yields a more balanced tree.
\section{Conclusions}
\label{conclusions_sec}
The results presented in this paper establish theoretical
bounds on the capabilities of distributed self-stabilizing
architectures to solve constraint satisfaction problems.
The paper focuses on the feasibility of
solving the network consistency problem using self-stabilizing
distributed protocols, namely, guaranteeing convergence to
a consistent solution, if such exists, from {\em any}
initial configuration.
We have proved that, when any scheduler is allowed, a uniform
protocol (one in which all nodes
are identical)
cannot solve the network
consistency problem, even if only one node is activated
at a time (i.e., when using a central scheduler).
Consequently, although such protocols have obvious advantages,
they cannot guarantee convergence to a solution.
On the other hand, distinguishing one single node from the rest
is sufficient to guarantee such a convergence
even when sets of nodes are activated simultaneously.
A protocol for solving the problem under such conditions is presented.
Note that the negative results are established under a
model requiring convergence for every central or distributed
schedule and is not applicable
to many cases where the schedule is restricted.
We demonstrated that when the network
is restricted to trees, a uniform, self-stabilizing
protocol exists for solving the problem with any central scheduler,
where only one neighboring node is activated at a time.
Note also that the restriction to a central scheduler is not as severe
as it might at first appear. Any protocol that works with a
central scheduler can also
be implemented with a distributed scheduler that obeys the
restriction that
two neighboring nodes are never activated together.
It is still an open question whether
a uniform protocol is feasible for general graphs
under restricted scheduling policies (e.g., round-robin).
Regarding time complexity, we showed that in the worst case
the distributed and the sequential protocols have the
same complexity bound:
exponential in the depth of the DFS tree. On the
average, however, a speedup
between $n/b$ and $n/(b \cdot m)$ is possible, where $n$ is the number
of nodes and $m$ is the DFS's tree depth.
We also argued that when the environment undergoes local
change, the solution to the network consistency problem
can often be repaired quickly (but not for
all cases),
due to the inherent local computation of the distributed
architecture.
\section*{Acknowledgments}
We thank Shlomo Moran for help in the proof of
the root-finding protocol and
Arun Jagota for his advice on related work
and for useful discussions.
\subsection*{Acknowledgment of support}
Dechter was partially supported by
the National Science Foundation, grant number IIS9610015,
and by the Air Force Office of Scientific Research,
grant number AFOSR-90-0136.
Katz was partially supported by the
Argentinian Research Fund at the
Technion-Israel Institute of Technology.
\bibliography{collin}
\bibliographystyle{alpha}
\end{document}