On the Feasibility of Distributed Constraint Satisfaction

1 Introduction

Consider the distributed version of the graph coloring problem, where each node must select a color (from a given set of colors) that is different from any color se­ lected by its neighbors. This coloring task, whose se­ quential version is known to be NP-complete, belongs to a class of Constraint Satisfaction Problems ( CSPs) that present interesting challenges to distributed com­ putation, particularly in the framework of connectionist architectures. We call the distributed versions of such problems Network Consistency Problems (NCPs). We consider what types of distributed models admit a self-stabilizing algorithm (namely, one that converges to a solution from any initial state of the network), and present such algorithms when possible.

C~mstraints are useful in programming languages, sim­ ulatiOn packages and general knowledge representation systems, and the prospects of solving such problems by connectionist networks promise the combined advan- Shmuel Katz CS, TechnionIsrael Institute of Technology, Haifa, 32000, Israel tages of parallelism, simplicity of design and error cor­ rection capabilities.

·This work was partially supported by the National Sci­ ence Foundation, Grant #IRI-8821444 and by the Air Force Office of Scientific Research, Grant #AFOSR-90-0136.

, Indeed, many interesting problems attacked by researchers in neural networks are combinatorial and many involve constraint satisfaction [Ballard et al., 1986, Dahl, 1987]. In fact, any discrete state connectionist net­ \YOrk can be viewed as a type of constraint network, with each stable -pattern of states representing a consistent solution. However, current connectionist approaches to CSPs lack theoretical guarantees of convergence (to a so­ lution satisfying all constraints), and the terms on which such convergence can be guaranteed (if at all) have not been explored till now.

In this paper we show that widely used connectionist­ type architectures in which all nodes run identical pro­ cedures cannot admit algorithms that guarantee conver­ gence to a consistent solution, even if such a solution exists (Section 2). We then identify a distributed model that is close in spirit to the connectionist paradigm, for which such guarantees can be established (Section 3). Within this model, we characterize and provide algo­ rithms for a restricted subclass of networks that can be solved uniformly (Section 4).

2 Model and Definitions

2.1 CSP definition

A network of binary constraints involves a set of n vari­ ables X1, ... , Xn, each represented by its domain values, D1, ... , Dn, and a set of constraints. A binary con­ straint R;i between two variables Xi and Xj is a subset of the Cartesian product Di x Dj that specifies which values of the variables are compatible with each other. A solution is an assignment of values to all the variables which satisfies all the constraints, and the constraint sat­ isfaction problems associated with these networks are to find one or all solutions. A binary CSP can be asso­ ciated with a constraint-graph in which nodes repre­ sent variables and arcs connect pairs of variables which are constrained explicitly. (General constraint satisfac­ t~on problems may involve constraints of any arity, but smce network communication is only pairwise we focus on this subclass of problems.) Figure 1a presents a CSP constraint graph.

'"

2.2 The model

Our general communication model is known as the shared memory multi-reader single-writer modeL A distributed network consists of n nodes, connected by shared communication registers, called state registers. The network can be viewed as a communication graph where nodes represent processors and arcs correspond to communication registers. The register statei is written only by node i, but may be read by several nodes (all of i's neighbors). The state register may have several fields, but it is regarded as one unit. A node can be modeled as a finite state-machine where its state is controlled by a transition function that is dependent on its current state and the states of its neighbors. In other words, an activated .node performs an atomic step consisting of reading the states of all its neighbors, deciding whether to change its state and then moving to a new state (by writing in its state register) 1 · The collection of all tran­ sition functions is called a protocol. The processors are anonymous i.e. , have no identities (we use the terms ' . node i and processor Pi interchangeably and as a wnting convenience only). A configuration c of the system is the state vector of all processors.

The execution of the system can be managed either by a central demon (scheduler) defined in [Dijkstra, 1974, Dolev et a/. 1990] or by a distributed demon defined in [Burns et'al., 1987, Dolev eta/., 1990]. The distributed demon activates a subset of the system's nodes at each step, while the central dem~n acti~ates only on~ pro_ces­ sor at a time (and thus can be VIewed as a s1mphfied version of the distributed demon). All activated nodes execute a single atomic step simultaneously.

The central demon means that an interleaving is suf­ ficient for the analysis of the protocoL Nevertheless, on the implementation level, truly independent nodes can execute in parallel since they cannot affect each other. Only neighboring nodes in the constraint graph cannot execute at the same atomic step when a central demon is assumed.

We denote c1 -+ c2 if c2 is a configuration which is reached from configuration ci by some subset of proces­ sors simultaneously executing a single atomic step. An execution of the system is an infinite sequence of con­ figurations E = CI, c2 ··· such that for every i, Ci :-: Ci+l· An execution is considered fair if every node participates in it infinitely often.

1 In fact, a finer degree of atomicity, requiring only_ a test­ and-set operation, is possible, but is not used here m order to simplify the arguments.

2.3 Self-stabilization

A self-stabilizing protocol [Dijkstra, 197 4] is one with a particular convergence property. The system configuration-space is partitioned into two classes - le­ gal, denoted by L, and illegaL Th~ protoco! is self­ stabilizing if in any infinite fair executiOn, startmg from any initial configuration (and with any input values) and given "enough time", the system eventually reaches a le­ gal configuration, and all subsequently computed config­ urations are legaL Thus a self-stabilizing protocol con­ verges from any point in its configuration-space to a sta­ ble, legal region.

The legality of a configuration depends on the aim of the protocoL In our case, we wish to design a protocol for solving the network consistency problem. Thus, the set of legal configurations are those having a consistent assignment of values t? all the nodes in the ne.twork, _if such an assignment exists, and any set, otherwise. This definition allows the system to oscillate among various solutions if more than one consistent assignment is pos­ sible. H~wever, the protocols that are presented in this paper converge to one of the possible solutions.

2.4 The limits of uniform self-stabilization

A protocol is uniform if all the nodes are logically equivalent and identically programmed (i.e. have identi­ cal transition functions). Following an observation made by Dijkstra [Dijkstra, 1974] regarding the computational limits of a uniform model for performing the mutual ex­ clusion task we show that the network consistency prob­ lem cannot 1 be solved using a uniform protocoL This is accomplished by presenting a specific constraint network and proving that its convergence cannot be guaranteed using any uniform protocoL

Consider the task of numbering a ring of proces­ sors in a cyclic ascending order - we call this CSP the "ring ordering problem". The constraint-graph of the problem is a ring of nodes with the domains {0, 1, ... , n- 1}. Every arc has the set of constraints {(i, (i+ 1) mod n)l 0$ i $ n -1} i.~., the lef~ node is o~e smaller than the right one. A solutiOn to this problem IS a cyclic permutation of the numbers 0, ... ,n- 1, which means that there are n possible solutions, and in all of them different nodes are assigned different values.

Theorem 1: No uniform, self stabilizing protocol can solve the ring ordering problem, under a central demon policy.

Proof: In order to obtain a contradiction, assume that there exists a uniform self-stabilizing protocol for solving the problem. In particular, it would solve the ring-ordering problem for a ring having a composite number of nodes, n = r · q (r, q > 1). Since convergence to a solution is guaranteed from any initial configura­ tion, it also applies to one where all nodes are in identical states. We construct a fair execution for such a protocol for which the network never converges to a consistent solution, contradicting the self stabilization property of the protocol. Assume the following execution:

Note that nodes Po, P 9 , P2 9 , ··· ,P(r-1)q· after their first activation, move to identical states because their in­ puts, initial states and transition functions are identical, and when each one of them is activated their neighbors are in identical states too. The same holds for any se­ quential activation of processors { Piq+j I 0 $ i < r, 0 $ j < q}. Thus, cycling through the above schedule assures that Po and P 9 , 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 will never reach a consistent solution, thus yielding a contradiction. 0

Theorem 1 implies that it is generally impossible to guarantee convergence to a consistent solution using a uniform protocol. It also implies that- such convergence cannot be guaranteed for a class of sequential algorithms using so called "repair" methods, such as in [Minton et al., 1990]. It does not, however, exclude the possibility of existence of uniform protocols for restricted activation policies.

We can also show that, when using a distributed de­ mon, convergence (to a solution) cannot be guaranteed even for tree-networks. Consider, for instance, the col­ oring problem in a tree-network constructed from exactly two connected nodes each having the domain {BLACK, WHITE}. Since the two nodes are topologically identi­ cal, If they start from identical initial states and both of them are activated simultaneously, they can never be as­ signed different values. Consequently, the network does not converge to a legal solution, although one exists. This counterexample can be extended to a large class of trees, where there is no possible way to distinguish be­ tween two internal nodes. We will show, however, (sec­ tion 4) that for a central demon a uniform self stabilizing tree-network consistency protocol does exist.

Having proved that the network consistency problem cannot be solved using a uniform protocol, even with a central demon, we switch to a slightly more relaxed model of an "almost uniform" protocol, whereby all nodes but one are identical. We denote the special node as Po.

3 Consistency-Generation Protocol

Our network consistency protocol is based on a sequen­ tial version of a backtracking algorithm, called back­ jumping. When implemented on a variable ordering generated by a depth-first traversal of the constraint graph, the technique enables a distributed implementa­ tion. A preliminary version of this protocol appears in [Collin and Dechter, 1990].

3.1 Sequential aspects of constraint satisfaction

The most common algorithm for solving a CSP is back­ tracking. In its standard version, the algorithm traverses the variables in a predetermined order, provisionally as­ signing consistent values to a subsequence (X1, ... , Xi) of variables and attempting to append to it a new in­ stantiation of xi+1 such that the whole set is consistent. If no consistent assignment can be found for the next variable Xi+l, a deadend situation occurs; the algorithm "backtracks" to the most recent variable, changes its as­ signment and continues from there.

One useful improvement of backtracking, called back­ jumping [Dechter, 1990] consults the topology of the constraint graph to guide its "backward" phase. Specif­ ically, instead of going back to the most recent variable instantiated it jumps back several levels to the first variable connected to the deadend variable. It turns out that when using a depth-first search (DFS) on the constraint graph (to generate a DFS tree) and then con­ ducting backjumfing in an inorder traversal of the DFS tree, [Even, 1979 the jump-back destination of variable X is the parent of X in the DFS tree.

The nice property of a DFS tree that allows a parallel implementation is that any arc of the graph which is not in the tree connects a node to one of its tree ancestors (i.e. along the path leading to it from the root). Conse­ quently, the DFS tree represents a useful decomposition of the graph: if a variable X and all its ancestors are re­ moved from the graph, the subtrees rooted at X will be disconnected (Figure lb). 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 ( see also [Freuder and Quinn, 1987]).

3.2 General Network Consistency protocol

The network-consistency (NC) protocol is logically com­ posed of two self-stabilizing subprotocols that can be executed interleaved (we divide the second subprotocol into two parts in order to simplify the explanation):

1. DFS-tree generation
2. (a) graph-traversal protocol
3. (b) value-assignment

These subprotocols are unrelated to each other and, thus, can be independently replaced by any other version of implementation.

The basic idea of the protocol is to decompose the net­ work into several independent subnetworks, according to the DFS-tree structure, and to instantiate these subnet­ works in parallel. A proper order of value instantiation is guaranteed by the graph traversal protocol.

3.2.1 Neighborhoods and states

A self-stabilizing algorithm for generating a DFS-tree is presented in [Collin and Dolev, 1991] and will not be discussed here. This subprotocol is almost uniform and is the source of non-uniformity for the whole NC proto­ col. When the algorithm stabilizes each internal node, i, has one adjacent node, parent( i), designated as its parent in the tree, and a set of child nodes denoted children( i). Figure 2 indicates the environment of an internal node (2a), the root (2b), and a leaf (2c). The link leading from parent( i) to i is called i's inlink while the links connecting i to its children are called i's out­ links. The set of its neighboring nodes along the path from the root to i are called i's predecessors. The role of the root is played by the special processor Po. Each node i (representing variable X;) has a list of possible values, denoted as Domain;, and a pairwise relation R;; 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 nede contains the following fields:

1. A value field to which it assigns either one of its domain values or the symbol "*" (to denote a dead­ end).
2. A mode field indicating the node's "belief" regard­ ing the status of the network. A node's mode is ON if its value or its ancestors' values were changed since the last time it was in a forward phase, or 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).
3. Two boolean fields called parent_tag and children_tag, which are used by the graph­ traversal protocol (Section 3.2.2).

3.2.2 Graph-traversal protocol

The graph-traversal protocol is handled by a self­ stabilizing privilege passing mechanism. According to this protocol a node obtains a 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 balance-unbalance [Dijkstra, 1974, Dolev et al., 1990]. Once a DFS-tree is established, this scheme is imple­ mented by having every state register contain two fields: parent.tag, referring to its inlink and children.tag, re­ ferring to all its outlinks. A link is balanced, if the children.tag and the parent.tag on its endpoints have the same value, and the link is unbalanced otherwise. A node, i, becomes privileged if its inlink is unbalanced and all its outlinks are balanced 2 · The privilege can be passed backwards to the parent by balancing the incom­ ing link or forward to the children by unbalancing the outgoing links (i.e. by changing the parent.:tag or the children.tag value accordingly). A node applies the NC­ protocol only when it is privileged, otherwise it leaves its state unchanged.

Denote a branch to be a tree-path from the root to a leaf. The privilege-passing mechanism eventually con­ verges to a set of legally controlled configurations, in which no more than one node is privileged on ev­ ery branch. Figure 3 shows such a configuration (the parent.tag and the children.tag of every node are spec­ ified above and below the node respectively). This prop­ erty assures that eventually a node and its ancestors can­ not reassign their values simultaneously. The privileges travel along the branches backwards and forwards. We omit the proof due to space limitations.

3.2.3 Value-assignment

The value-assignment has a forward and a backward phases, corresponding to the two phases of the sequen­ tial backtracking algorithm. During the forward phase, nodes in different subtrees assign themselves values con­ sistent with their predecessors or verify the consistency of their assigned values. When a node senses a dead­ end it assigns its value field a "*" and initiates a back­ ward phase. When the network is consistent (all the processors are in an OFF mode) the forward and back­ ward phases continue, where the forward phase is used to verify the consistency of the network and the back­ ward phase just returns the privilege to the root to start a new forward wave. Once consistency verification is violated, the node sensing the violation initiates a new value-assignment. Since the root has no ancestors, it does not check consistency. It only assigns a new value at the end of each backward phase, when needed, and then initiates a new forward phase. A more elaborate description follows.

An internal node can be in one of three situations:

• 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 an ON mode and passes the privilege to its children. If no consistent value exists, it assigns itself the "*"

2 Note that this is well defined since we prove that even­ tually all siblings have the same parent-tag.

value (a deadend) and passes the privilege to its parent (initiating a backward phase).

• Node i is activated by its parent which is in an OFF mode. In that case it verifies the consis­ tency of its current value with its predecessors. If it is consistent it stays in an OFF mode and passes the privilege to its children. If not, it assigns itself a new value, moves to an ON mode, and passes the privilege to its children 3 ·
• Node i is activated by its children (backward phase). If one of th.e children- has a "*" value, the processor selects the next consistent value from its domain and passes the privilege to the children. If no consistent value is available, it assigns itself a "*" and passes the privilege to its parent 4 · If all children have a consistent value, i passes the privilege to its parent.

The value-assignment protocol is uniform since each node has both the root's protocol and the non-root's protocol and will decide between them based on the role assigned to it by the DFS-tree protocol.

The self-stabilization property of the NC protocol is inherited from its subprotocols; DFS-tree generation, privilege-passing and value-assignment. Once the self­ stabilization of privilege-passing is established, it assures the adequacy of the control for distributedly implement­ ing DFS-based backjumping, which guarantees the con­ vergence of the network to a legal solution, if one exists, and if not it keeps checking all the possibilities over and over again.

3.3 Complexity analysis

A crude estimate of the time complexity of the NC pro­ tocol can be given by computing the maximal number of state changes from the time the privilege-passing has stabilized until final convergence. The search space that is generated by the sequential DFS-backjumping obeys the following recurrence: T m = 1 +b· k · T m-1 with To = 1, which yields Tm = (b · k)m+l where Tm stands for the search space generated by sequential DFS-backjumping with depth m or less, b is the maximal branching degree and k bounds the domain sizes. Our bound improves the one presented in [Freuder and Quinn, 1987]. Note that since bm < n we get that Tm = O(nkm+l ). Clearly, in the worst parallel execution we get a sequential behav­ ior with the same time complexity - exponential in the depth of the DFS-tree. However, often, due to parallel instantiations of different subtrees, the parallel protocol may have, on the average, a significant speedup over the sequential one. We believe that the speedup (of our pro­ tocol over the same sequential algorithm) is of O(n/m). As an extreme example, consider problem instances that have a backtrack-free solution along the DFS ordering. These will be solved in O(n) sequentially, while in O(m) in parallel. To conclude, our protocol convergence can be achieved in polynomial time for networks with a bounded depth of the DFS-tree. .

3 A leaf, having no children, is always activated by its par­ ent and always passes the privilege back to its parent (initi­ ating a backward phase).

4 Due to the privilege passing mechanism, when a parent sees one of its children in a deadend it has to wait until all of them have given him the privilege. This is done to guar­ antee that all subtrees have a consistent view regarding their predecessors' values.

The average performance of the NC protocol can be further improved by adding to it a uniform self­ stabilizing arc-consistency subprotocol [Mackworth and Freuder, 1985]. A network is said to be arc­ consistent iffor 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 neigh­ bors' 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.

4 Network Consistency for Trees

In the rest of the paper we discuss protocols for a re­ stricted class of network topologies - trees. Our aim is to see whether such a restricted class of problems can be solved using the more relaxed, uniform, distributed model, and whether it can result in a more efficient pro­ tocol.

It is well known that the sequential network consis­ tency problem on trees is tractable, and can be achieved in linear time [Mackworth and Freuder, 1985]. A special algorithm for this task is composed of an arc-consistency phase (that can be efficiently implemented on trees), fol­ lowed by value assignment in an order created by some rooted tree. It has been shown that an arc-consistent tree enables backtrack-free value assignment with no deadends [Freuder, 1982]. Applying the general NC pro­ tocol together with the arc-consistency protocol to a tree will already result in an improved performance: when arc-consistency is established, one forward phase of the value-assignment protocol will assign values to all the nodes in linear time since no deadends will be encoun­ tered (see also [Dechter and Dechter, 1988]). Therefore, the almost-uniform NC protocol if applied to trees is guaranteed to converge in a polynomial number of steps.

Since, the DFS subprotocol of our general algorithm was the source for its non-uniformity, we reexamine the possibility that for trees, a rooted directed tree can be imposed via a uniform protocol. We already showed that when using a distributed demon, a uniform, network­ consistency protocol for trees is not feasible. Therefore, the only avenue not yet explored is whether under a cen­ tral demon such a protocol does exist. We next show that this conjecture is indeed correct.

4.1 A uniform tree-consistency protocol

In principle a uniform tree-consistency (TC) protocol can be extracted from the general NC protocol by only replacing the DFS-tree protocol with a uniform rooted-tree protocol, since any rooted-tree is also a DFS-tree. Since the arc-consistency protocol, the value­ assignment protocol and the privilege-passing protocol are already uniform, the resulting TC protocol will be uniform, as desired. Nevertheless, we will show that for trees, the value-assignment protocol can be simplified as well, while there is no need to have a special privilege­ passing mechanism at all.

The TC protocol consists of the following three subprotocols:

1. arc-consistency
2. tree-directing
3. tree-value-assignment

When the arcs are consistent and the tree has been directed, value assignment is eventually guaranteed by having each node follow the rule (of the 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 proce­ dure. Since, as we will 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.

In order to direct the tree, we must break the sym­ metry reflected by the identical codes and the lack of identifiers, by exploiting the topology of the tree. For this task we use a distributed protocol for finding the centers of a tree [Korach et al., 1984]. 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 tr~.

Our protocol distributedly simulates the above algo­ rithm. If only one center exists, it plays the role of a root and all the arcs are directed towards it. When two cen­ ters exist, the direction of the link that connects them remains ambiguous and both of them can be viewed as a root since all other links are directed towards them as before. In this case, each one of the two centers consid­ ers the other one to be its parent, and the tree-directing protocol, results in a pse.udo-rooted-tree where the centers (one or two nodes) play the root role.

We claim that this ambiguity will not hurt the tree­ value-assignment protocol at all. Note that the "first" center that applies the assignment protocol, assigns it­ self a value consistent with the other. When the other one is scheduled, it is supposed to assign itself a value that is consistent with the first one. However, its cur­ rent assignment is already consistent (since the first one has taken care of that already) and thus it remains un­ changed. All other nodes assign values that are consis­ tent with their parents as before. The central demon policy assures that only one (neighboring) center will be scheduled each time.

This approach yields a relatively simple uniform tree­ directing protocol that simulates the above description. Assume the number of nodes in the network 5 is n. Every node i has the following fields:

6 We can overcome the necessity of knowing the size of the network by using dynamic memory allocation. However, for the sake of the simplicity of the code we assume the knowl­ edge of n .

• N;[O .. Ln/2J]- a vector that counts the number of i's neighbors in each phase of the sequential algorithm. N; [j] records the number of neighbors of i in phase j. If N;[j] = 1 it means that i becomes a leaf in the j­ th phase (although it may be initialized incorrectly). N; [OJ is repeatedly initialized to the number of i's neighbors in the network (so that N; [0] = 1 means that i is a leaf in the original tree).
• parent; - a variable assigned the value j if node j be­ comes the parent of i (the enumeration is local to i). When the network stabilizes, namely when all the N -vectors converge, every node has one neigh­ bor only that is eligible to be its parent, except a single center which has none, and no two nodes are parents of each other except, perhaps, the two cen­ ters.

The protocol works by having each node scan its neigh­ bors' N -vectors and compute its own accordingly. Since the j-th entry of vector N; represents the number of i's neighbors in the j-th phase, its value is recursively computed by decreasing the number of neighbors that became leaves from the entire number of neighbors in the previous phase. Each node chooses as its parent the neighbor that was not removed from the tree earlier than itself. Figure 4 presents a pseudo-code for the protocol. Recall that the code is repeated forever, although from some point on, the tree does not change.

A proper convergence of the N -vectors is guaranteed by the fact that N; [j] depends only .on N; [j - 1] and {N,~:[j-1]1 k E neighbors(i)}, which are properly updated earlier. The base of this iterative convergence is applied by assigning to N;[O] the actual number of neighbors of i in the network.

The complexity of the tree protocol is clearly linear in the network's size since all its subprotocols are, and hence it equals the sequential time complexity. However, the parallel time can be further linearly bounded by the diameter of the tree where the diameter is the longest path between any two leaves of the tree.

5 Conclusions

The results presented in this paper establish theoretical bounds on the capabilities of connectionist architectures and other distributed approaches to constraint satisfac­ tion problems.

The paper focuses on the feasibility of solving the network consistency problem using self-stabilizing dis­ tributed protocol, namely, guaranteeing a convergence to a consistent solution, if such exists, from any initial configuration. Such property is essential for dynamic environments, where unexpected changes could occur in some of the constraints.

We proved that a uniform protocol, one in which all nodes are identical, cannot solve the network consistenJ=.y problem even if only one node is activated at a time. Consequently, although such protocols have obvious ad­ ventages and are closer in spirit to neural networks ar­ chitectures, they cannot guarantee convergence to a so­ lution. On the other hand, distinguishing one node from the others is sufficient to guarantee such a convergence

procedure tree-directing Begin 1. N;[O] +-lneighbors(i)l 2. j +- 0 { j is a local counter } 3. if N;[O] :j; 1 then { when i is not a leaf} 4. while N;[j] > 1 do { i is not yet a leaf at the j-th stage } 5. j +- j + 1 { the leaves of the (j - 1 )-th stage are removed in the j-th stage } 6. N;[j] +- N;[j- 1]- l{k I kEneighbors(i) 1\ Nk[j- 1] = 1}1 od 7. if3kEneighbors(i) s.t. Nk[j] 2:::1 then {no more than one such k exists} 8. parent; +- k 9. else { i is the only center } 10. parent; +- NONE End.

even when sets of nodes are activated simultaneously. A protocol for solving the problem under such conditions is presented.

We then demonstrated that, when the network is re­ stricted to trees, a uniform, self-stabilizing protocol for solving the problem does exist, but only under asyn­ chronous control (one neighboring node is activated at a time).

It is still an open question whether a uniform proto­ col is feasible under some specific ordering of the asyn­ chronous activation.

Regarding time complexity, we have shown that in the worse-case the distributed and the sequential pro­ tocols have the same complexity bound; exponential in the depth of the DFS tree. On the average, however, a linear speed up is feasible for bounded depth networks.