We introduce, as an enhancement of self-stabilization, the concept of monotonic self-stabilization for distributed systems that ensures that a certain measure of quality of state monotonically improves when the system in an illegitimate state progresses toward a legitimate state. In the concept, the quality is measured by a real-valued function that can be chosen from a certain class of functions. The concept is applied to a multi-robot pattern formation problem in which a group of autonomous mobile robots move from their respective initial positions to the goal positions like a marching band. We solve the problem by presenting two monotonic self-stabilizing pattern formation algorithms, one of which is for FSYNC model and the other is for SSYNC model. The considered real-valued functions to measure the quality take into account both the distance to the goal location and the accuracy of the formation. We present a formal proof of the algorithms' correctness and monotonic self-stability.

A set function $f$ on a finite set $V$ is submodular if $f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y)$ for any pair $X, Y \subseteq V$. The symmetric difference transformation ( SD-transformation) of $f$ by a canonical set $S \subseteq V$ is a set function $g$ given by $g(X) = f(X \vartriangle S)$ for $X \subseteq V$, where $X \vartriangle S = (X \setminus S) \cup (S \setminus X)$ denotes the symmetric difference between $X$ and $S$. Submodularity and SD-transformations are regarded as the counterparts of convexity and affine transformations in a discrete space, respectively. However, submodularity is not preserved under SD-transformations, in contrast to the fact that convexity is invariant under affine transformations. This paper presents a characterization of SD-transformations preserving submodularity. Then, we are concerned with the problem of discovering a canonical set $S$, given the SD-transformation $g$ of a submodular function $f$ by $S$, provided that $g(X)$ is given by a function value oracle. A submodular function $f$ on $V$ is said to be strict if $f(X) + f(Y) > f(X \cup Y) + f(X \cap Y)$ holds whenever both $X \setminus Y$ and $Y \setminus X$ are nonempty. We show that the problem is solved by using $\mathrm{O}(|V|)$ oracle calls when $f$ is strictly submodular, although it requires exponentially many oracle calls in general.

Consider a set of n mobile computational entities, called robots, located and operating on a continuous cycle C (e.g., the perimeter of a closed region of R^2) of arbitrary length l. The robots are identical, can only see their current location, have no location awareness, and cannot communicate at a distance. In this weak setting, we study the classical problems of gathering (GATHER), requiring all robots to meet at a same location; and election (ELECT), requiring all robots to agree on a single one as the "leader". We investigate how to solve the problems depending on the amount of knowledge (exact, upper bound, none) the robots have about their number n and about the length of the cycle l. Cost of the algorithms is analyzed with respect to time and number of random bits. We establish a variety of new results specific to the continuous cycle - a geometric domain never explored before for GATHER and ELECT in a mobile robot setting; compare Monte Carlo and Las Vegas algorithms; and obtain several optimal bounds.

International audience

The rotor-router model is a deterministic process analogous to a simple random walk on a graph, and the discrepancy of token configurations between the rotor-router model and its corresponding random walk has been investigated in some contexts. Motivated by general Markov chains beyond simple random walks, this paper investigates a generalized model which imitates a Markov chain (of multiple tokens) possibly containing irrational transition probabilities. We are concerned with the vertexwise discrepancy of the numbers of tokens between the generalized model and its corresponding Markov chain, and present an upper bound of the discrepancy in terms of the mixing time of the Markov chain.

We consider a distributed system consisting of autonomous mobile computing entities called robots moving in the three-dimensional space (3D-space). The robots are anonymous, oblivious, fully-synchronous and have neither any access to the global coordinate system nor any explicit communication medium. Each robot cooperates with other robots by observing the positions of other robots in its local coordinate system. One of the most fundamental agreement problems in 3D-space is the plane formation problem that requires the robots to land on a common plane, that is not predefined. This problem is not always solvable because of the impossibility of symmetry breaking. While existing results assume that the robots agree on the handedness of their local coordinate systems, we remove the assumption and consider the robots without chirality. The robots without chirality can never break the symmetry consisting of rotation symmetry and reflection symmetry. Such symmetry in 3D-space is fully described by 17 symmetry types each of which forms a group. We extend the notion of symmetricity [Suzuki and Yamashita, SIAM J. Compt. 1999] [Yamauchi et al., PODC 2016] to cover these 17 symmetry groups. Then we give a characterization of initial configurations from which the fully-synchronous robots without chirality can form a plane in terms of symmetricity.

The Meeting problem for k>=2 searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order sigma (where sigma=1 corresponds to no rotational symmetry), we prove that k=sigma+1 searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with k=2 searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon's vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest.

Creating a swarm of mobile computing entities, frequently called robots, agents, or sensor nodes, with self-organization ability is a contemporary challenge in distributed computing. Motivated by this, we investigate the plane formation problem that requires a swarm of robots moving in the three-dimensional Euclidean space to land on a common plane. The robots are fully synchronous and endowed with visual perception. But they do not have identifiers, nor access to the global coordinate system, nor any means of explicit communication with each other. Though there are plenty of results on the agreement problem for robots in the two-dimensional plane, for example, the point formation problem, the pattern formation problem, and so on, this is the first result for robots in the three-dimensional space . This article presents a necessary and sufficient condition for fully synchronous robots to solve the plane formation problem that does not depend on obliviousness, i.e., the availability of local memory at robots. An implication of the result is somewhat counter-intuitive: The robots cannot form a plane from most of the semi-regular polyhedra, while they can form a plane from every regular polyhedron (except a regular icosahedron), whose symmetry is usually considered to be higher than any semi-regular polyhedron.

We investigate the pattern formation problem that requires a swarm of autonomous mobile robots to form a given target pattern in the three-dimensional Euclidean space. We show a necessary and sufficient condition for synchronous robots to form a given target pattern from an initial configuration. We give a pattern formation algorithm for solvable instances that does not need any local memory at each robot.

We investigate pattern formation, i.e., self-organization, by a swarm of mobile robots, which is closely related with the agreement problem in distributed computing. Consider a system of anonymous mobile robots in a 2-dimensional Euclidean space in which each robot repeatedly executes a “Look-Compute-Move” cycle, to observe the positions of all the robots, to compute a route to the next position using an algorithm, and then to trace the route, where the algorithm is common to all robots. The robots are said to be fully synchronous if their Look-Compute-Move cycles are completely synchronized, and the $i$th Look, Compute, and Move of all robots start and end simultaneously. They are said to be asynchronous if no assumptions are made on their synchrony. The robots are said to be oblivious if they have no memory to memorize the execution history and hence behave based only on the robots' positions observed during the immediately preceding Look. We show that the set of geometric patterns formable by oblivious asynchronous robots is exactly the set of those formable by nonoblivious fully synchronous robots, except for a point of multiplicity 2, i.e., gathering for two robots. In short, contrary to our intuition, synchrony and memory do not help in pattern formation, except for gathering. Specifically, we propose an algorithm for oblivious asynchronous robots that, given a geometric pattern as input, forms it, as long as it is formable by nonoblivious fully synchronous robots except for a point of multiplicity 2.

In this paper we study the power of using lights, i.e. visible external memory, for distributed computation by autonomous robots moving in Look-Compute-Move (LCM) cycles. With respect to the LCM cycles, the most common models studied in the literature are the fully-synchronous (FSYNC), the semi-synchronous (SSYNC), and the asynchronous (ASYNC). In this paper we introduce in the ASYNC model, the weakest of the three, the availability of visible external memory: each robot is equipped with a light bulb that is visible to all other robots, and that can display a constant numbers of different colors, the colors are persistent, that is they are not automatically reset at the end of each cycle. We first study the relationship between ASYNC with visible bits and SSYNC. We prove hat asynchronous robots, when equipped with a constant number of colors, are strictly more powerful than traditional semi-synchronous robots. We also show that, when enhanced with visible lights, the difference between asynchrony and semi-synchrony disappears, this result must be contrasted with the strict dominance ASYNC

We consider infrastructure-less highly dynamic networks, where connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. These networks are naturally modeled as time-varying graphs. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e., it provides the nodes with store-carry-forward-like mechanisms such as local buffering) than if waiting is not feasible. We provide a quantitative corroboration of this fact in terms of the expressivity of the corresponding time-varying graph; that is in terms of the language generated by the feasible journeys in the graph. We prove that the set of languages Lnowait when no waiting is allowed contains all computable languages. On the other end, we prove that Lwait is just the family of regular languages. This gap is a measure of the computational power of waiting. We also study bounded waiting; that is when waiting is allowed at a node only for at most d time units. We prove the negative result that L wait[d] = Lnowait.

Anonymous mobile robots are often classified into synchronous, semi-synchronous, and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with the single exception of forming a point (i.e., the gathering) by two robots. (All patterns formable with memory are formable without memory for synchronous robots, and little is known for asynchronous robots.) However, the gathering problem for two semi-synchronous robots without memory (called oblivious robots in this paper) is trivially solvable when their local coordinate systems are consistent, and the impossibility proof essentially uses the inconsistencies in their coordinate systems. Motivated by this, this paper investigates the magnitude of consistency between the local coordinate systems necessary and sufficient to solve the gathering problem for two oblivious robots under semi-synchronous and asynchronous models. To discuss the magnitude of consistency, we assume that each robot is equipped with an unreliable compass, the bearings of which may deviate from an absolute reference direction, and that the local coordinate system of each robot is determined by its compass. We consider two families of unreliable compasses, namely, static compasses with (possibly incorrect) constant bearings and dynamic compasses the bearings of which can change arbitrarily (immediately before a new look-compute-move cycle starts and after the last cycle ends). For each of the combinations of robot and compass models, we establish the condition on deviation $\phi$ that allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the x-axis of a compass and the reference direction of the global coordinate system: $\phi < \pi/2$ for semi-synchronous and asynchronous robots with static compasses, $\phi < \pi/4$ for semi-synchronous robots with dynamic compasses, and $\phi < \pi/6$ for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.

We study the computational power of a distributed system consisting of simple autonomous robots moving on the plane. The robots are endowed with visual perception but do not have any means of explicit communication with each other, and have no memory of the past. In the extensive literature it has been shown how such simple robots can form a single geometric pattern (e.g., a line, a circle, etc), however arbitrary, in spite of their obliviousness. This brings to the front the natural research question: what are the real computational limits imposed by the robots being oblivious? In particular, since obliviousness limits what can be remembered, under what conditions can oblivious robots form a series of geometric patterns? Notice that a series of patterns would create some form of memory in an otherwise memory-less system. In this paper we examine and answer this question showing that, under particular conditions, oblivious robot systems can indeed form series of geometric patterns starting from any arbitrary configuration. More precisely, we study the series of patterns that can be formed by robot systems under various restrictions such as anonymity, asynchrony and lack of common orientation. These results are the first strong indication that oblivious solutions may be obtained also for tasks that intuitively seem to require memory.

Reaching agreement among a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize and meet at some location not determined in advance, and without the help of some global coordinate system. While very simple to express, this problem has the advantage of retaining the inherent difficulty of agreement, namely the question of breaking symmetry between robots. In previous works, it has been proved that the gathering problem is solvable in asynchronous model with oblivious (i.e., memory-less) robots and limited visibility, as long as the robots share the knowledge of some direction, as provided by a compass. However, the problem has no solution in the semi-synchronous model when robots do not share a compass, or when they cannot detect multiplicity. In this article, we define a model in which compasses may be unreliable, and study the solvability of gathering oblivious mobile robots with limited visibility in the semi-synchronous model. In particular, we give an algorithm that solves the problem in finite time in a system where compasses are unstable for some arbitrary long periods, provided that they stabilize eventually. In addition, we show that our algorithm solves the gathering problem for at most three robots in the asynchronous model. Our algorithm is intrinsically self-stabilizing.

Self-stabilization is a strong property which guarantees that a network always resume a correct behavior starting from an arbitrary initial state. Weaker guarantees have later been introduced to cope with impossibility results: probabilistic stabilization only gives probabilistic convergence to a correct behavior. Also, weak-stabilization only gives the possibility of convergence. In this paper, we investigate the relative power of weak, self, and probabilistic stabilization, with respect to the set of problems that can be solved. We formally prove that in that sense, weak stabilization is strictly stronger that self-stabilization. Also, we refine previous results on weak stabilization to prove that, for practical schedule instances, a deterministic weak-stabilizing protocol can be turned into a probabilistic self-stabilizing one. This latter result hints at more practical use of weak-stabilization, as such algorithms are easier to design and prove than their (probabilistic) self-stabilizing counterparts.

It is known that the leader election in anonymous networks is not always solvable, and solvable/unsolvable cases are characterized by the network topologies. Therefore a distributed leader election algorithm is required to elect a leader when it is possible, otherwise recognize the impossibility and stop. Although former studies proposed several leader election algorithms, the space complexity of the problem is not considered well. This paper focuses on the space complexity, that is, the necessary or sufficient number of bits on processors to execute a leader election algorithm. First we show that only one bit memory is sufficient for a leader election algorithm which is specific to a fixed n. We then show that a general algorithm can solve the leader election for arbitrary n if each processor has O(n log d) bits memory where d is the maximum degree of a processor. Finally, we give a lower bound Ω(log n) on the space complexity, that is, we show that it is impossible to construct a leader election algorithm if only log n bits are available for a processor.

In this note we make a minor correction to a scheme for robots to broadcast their private information. All major results of the paper [I. Suzuki and M. Yamashita, SIAM J. Comput., 28 (1999), pp. 1347-1363] hold with this correction.

Polygon search is the problem of finding mobile intruders who move unpredictably in a polygonal region. In this paper, we consider a special case of this problem, called boundary search, where the searcher is allowed to move only along the boundary of the polygon. We concentrate on a single searcher with one flashlight (called a 1-searcher), but it is known that a single boundary 1-searcher has the same searching power as a single boundary searcher with 360/spl deg/ vision. Our main result is that the movement of the searcher can be controlled by a finite-state machine having only seven states. This automaton has no built-in information about the input polygon and, for any given polygon P, if P can be searched by a boundary searcher at all, then this automaton will successfully search P, no matter where on the boundary of P it is initially placed. All information about P is acquired by the automaton online, as it searches P. We also show that if P can be searched by a boundary searcher, then our automaton searches it by circling its boundary less than three times.

A coterie is a set of subsets (called quorums) of the processes in a distributed system such that any two quorums intersect with each other and is mainly used to solve the mutual exclusion problem in a quorum-based algorithm. The choice of a coterie sensitively affects the performance of the algorithm and it is known that nondominated (ND) coteries achieve good performance in terms of criteria such as availability and load. On the other hand, grid coteries have some other attractive features: 1) a quorum size is small, which implies a low message complexity, and 2) a quorum is constructible on the fly, which benefits a low space complexity. However, they are not ND coteries unfortunately. To construct ND coteries having the favorite features of grid coteries, we introduce the transversal merge operation that transforms a dominated coterie into an ND coterie and apply it to grid coteries. We call the constructed ND coteries ND grid coteries. These ND grid coteries have availability higher than the original ones, inheriting the above desirable features from them. To demonstrate this fact, we then investigate their quorum size, load, and availability, and propose a dynamic quorum construction algorithm for an ND grid coterie.

A network partition, which makes it impossible for some pairs of processes to communicate with each other, is one of the most serious network failures. Although the notion of k-coterie is introduced to design a k-mutual exclusion algorithm that is robust against network failures, the number of processes allowed to simultaneously access the critical section may fatally decrease once network partition occurs. We discuss how to construct a k-coterie such that the k-mutual exclusion algorithm adopting it is robust against a network 2-partition. To this end, we introduce the notion of complemental k-coterie, and show that complemental k-coteries meet our requirements. We then give methods for constructing complemental k-coteries, and show a necessary and sufficient condition for a k-coterie to be complemental.

In this paper, we address a number of issues related to motion planning and analysis of rectangular metamorphic robotic systems. We first present a distributed algorithm for reconfiguration that applies to a relatively large subclass of configurations, called horizontally convex configurations. We then discuss several fundamental questions in the analysis of metamorphic systems. In particular, the following two questions are shown to be decidable: 1) whether a given set of motion rules maintains connectivity; 2) whether a goal configuration is reachable from a given initial configuration (at specified locations). In the general case in which each module has an internal state, the following is shown to be undecidable: given a set of motion rules, whether there exists a certain type of configuration called a uniform straight-chain configuration that yields a disconnected configuration.

We examine the problem of dynamic self-reconfiguration of a modular robotic system (frequently referred to as self-reconfigurable or metamorphic system), to a formation aimed at reaching a specified target position with one of the modules as quickly as possible. We present a number of high speed formations for both rectangular and hexagonal systems, and prove upper and lower bounds on the speed of locomotion. In particular, the formations presented achieve constant ratio guarantee on the time to reach a given target in the asymptotic sense.

A self-stabilizing system is a system such that it autonomously converges to a legitimate system state, regardless of the initial system state. The local mutual exclusion problem is the problem of guaranteeing that no two processes neighboring each other execute their critical sections at a time. The process identifiers are said to be chromatic if no two processes neighboring each other have the same identifiers. Under the assumption that the process identifiers are chromatic, this paper proposes two self-stabilizing local mutual exclusion algorithms; one assumes a tree as the topology of communication network and requires 3 states per process, while the other which works on any communication network, requires n + 1 states per process, where n is the number of processes in the system. We also show that the process identifiers being chromatic is close to necessary for a system to have a self-stabilizing local mutual exclusion algorithm. We adopt the shared memory model for communication and the unfair distributed daemon for process scheduling.

Suppose that a distributed system is modeled by an undirected graph G = (V, E), where V and E, respectively, are the sets of processes and communication links. Israeli and Jalfon (1990) proposed a simple self-stabilizing mutual exclusion algorithm: a token is circulated among the processes (i.e., vertices) and a process can access the critical section only when it holds the token. In order to guarantee equal access chance to all processes, the token circulation needs to be fair in the sense that all processes have the same probability of holding the token. However, the Israeli-Jalfon token circulation scheme does not meet the requirement. This paper proposes a new scheme for making it fair. We evaluate the average of the longest waiting times in terms of the cover time and show an O(deg(G)n/sup 2/) upper bound on the cover time for our scheme, where n and deg(G) are the number of processes and the maximum degree of G, respectively. The same (tight) upper bound is known for the Israeli-Jalfon scheme.

We consider the problem of transporting a long object, such as a ladder, through a 90 degree corner in a corridor using two omnidirectional robots that do not necessarily have identical characteristics. A distributed algorithm is presented in which each robot computes its own motion based on the current and goal positions of the ladder, the locations of the walls, and the motion of the other robot observed indirectly through the link between the robot and the ladder. We evaluate the performance and robustness of the algorithm using extensive computer simulation by changing several parameter values that affect the key characteristics of the robots, including the maximum speed, the guide path through a corner, and the sensitivity and reaction to the motion of the other robot. The simulation results indicate that if the parameter values are chosen within certain reasonable ranges, then overall the algorithm works quite well even for robots having difficult characteristics. It is also shown that the robustness of the algorithm critically depends on the differences between the robots in the values of two parameters.

The coterie join operation proposed by M.L. Neilsen and M. Mizuno (1994) produces, from a k-coterie and a coterie, a new k-coterie. For the coterie join operation, this paper first shows 1) a necessary and sufficient condition to produce a nondominated k-coterie (more accurately, a nondominated k-semicoterie satisfying nonintersection property) and 2) a sufficient condition to produce a k-coterie with higher availability. By recursively applying the coterie join operation in such a way that the above conditions hold, we define nondominated k-coteries, called tree structured k-coteries, the availabilities of which are thus expected to be very high. This paper then proposes a new k-mutual exclusion algorithm that effectively uses a tree structured k-coterie, by extending Agrawal and El Abbadi's tree algorithm. The number of messages necessary for k processes obeying the algorithm to simultaneously enter the critical section is approximately bounded by k log(n/k) in the best case, where n is the number of processes in the system.

In this paper, we investigate a probabilistic local majority polling game on weighted directed graphs, keeping an application to the distributed agreement problem in mind. We formulate the game as a Markov chain, where an absorbing state corresponds to a system configuration that an agreement is achieved, and characterize on which graphs the game will eventually reach an absorbing state with probability 1. We then calculate, given a pair of an initial and an absorbing states, the absorbing probability that the game will reach the absorbing state, starting with the initial state. We finally demonstrate that regular graphs have a desirable property from the view of the distributed agreement application, by using the martingale theory. © 2000 John Wiley & Sons, Inc.

Let G be an undirected graph with a set of vertices V and a set of edges E. Given an integer r, we assign at most r labels (representing "resources") to each vertex. We say that such an assignment is an r-configuration if, for each label c, the vertices labeled by c form a dominating set for G. In this paper, we are interested in the maximum number, D r (G), of labels that can be assigned to the vertices of graph G by an r-configuration. The decision problem ``$D_1(G)\geq K$?" (known as the domatic number problem) is NP-complete. We first investigate D r (G) for general graphs and establish bounds on D r (G) in terms of D 1 (G) and the minimum vertex degree of G. We then discuss D r (G) for d-regular graphs. We clearly have $D_r (G) \leq r(d+1)$. We show that the problem of testing if D r (G) = r(d+1) is solvable in polynomial time for d-regular graphs with |V| = 2(d+1), but is NP-complete for those with |V| = a(d+1) for some integer $a \geq 3$. Finally, we discuss cubic (i.e., 3-regular) graphs. It is easy to show $2r \leq D_r (G) \leq 4r$ for cubic graphs. We show that the decision problem for D 1 (G) = K is co-NP-complete for K = 2 and is NP-complete for K = 4. Although there are many cubic graphs G with D 1 (G) = 2, surprisingly, every cubic graph has a 2-configuration with five labels, i.e., $D_2 (G) \geq 5$ and such a 2-configuration can be constructed in polynomial time. We use this fact to show $D_r (G) \geq \lfloor 5r/2 \rfloor$ in general.

The concept of k-coterie is useful for achieving k-mutual exclusion in distributed systems. A graph is said to be well covered if any of its maximal independent sets is also maximum. We first show that a graph G is well covered with independence number k if and only if G represents the incidence relation among quorums forming a k-coterie. We then discuss the problem of constructing k-coteries having some desirable properties. We also characterize the well-covered graphs with independence number 2. © 1999 John Wiley & Sons, Inc. Networks 34: 221–228, 1999

Consider a system of multiple mobile robots in which each robot, at infinitely many unpredictable time instants, observes the positions of all the robots and moves to a new position determined by the given algorithm. The robots are anonymous in the sense that they all execute the same algorithm and they cannot be distinguished by their appearances. Initially they do not have a common x-y coordinate system. Such a system can be viewed as a distributed system of anonymous mobile processes in which the processes (i.e., robots) can "communicate" with each other only by means of their moves. In this paper we investigate a number of formation problems of geometric patterns in the plane by the robots. Specifically, we present algorithms for converging the robots to a single point and moving the robots to a single point in finite steps. We also characterize the class of geometric patterns that the robots can form in terms of their initial configuration. Some impossibility results are also presented.

We model a distributed system by a graph G=(V, E), where V represents the set of processes and E the set of bidirectional communication links between two processes. G may not be complete. A popular (distributed) mutual exclusion algorithm on G uses a coterie C(/spl sube/2/sup V/), which is a nonempty set of nonempty subsets of V (called quorums) such that, for any two quorums P, Q/spl isin/C, 1) P/spl cup/Q/spl ne/0 and 2) P/spl nsub/Q hold. The availability is the probability that the algorithm tolerates process and/or link failures, given the probabilities that a process and a link, respectively, are operational. The availability depends on the coterie used in the algorithm. This paper proposes a method to improve the availability by transforming a given coterie.

In the networks considered in this paper, processors do not have distinct identity numbers. On such a network, we discuss the leader election problem and the problem of counting the number of processors having the same identity number. As the communication mode, we consider port-to-port, broadcast-to-port, port-to-mail box, and broadcast-to-mailbox. For each of the above communication modes, we present: an algorithm for counting the number of processors with the same identity number; an algorithm for solving the leader election problem; and a graph theoretical characterization of the solvable class for the leader election problem.

We present a distributed algorithm for converging autonomous mobile robots with limited visibility toward a single point. Each robot is an omnidirectional mobile processor that repeatedly: 1) observes the relative positions of those robots that are visible; 2) computes its new position based on the observation using the given algorithm; 3) moves to that position. The robots' visibility is limited so that two robots can see each other if and only if they are within distance V of each other and there are no other robots between them. Our algorithm is memoryless in the sense that the next position of a robot is determined entirely from the positions of the robots that it can see at that moment. The correctness of the algorithm is proved formally under an abstract model of the robot system in which: 1) each robot is represented by a point that does not obstruct the view of other robots; 2) the robots' motion is instantaneous; 3) there are no sensor and control error; 4) the issue of collision is ignored. The results of computer simulation under a more realistic model give convincing indication that the algorithm, if implemented on physical robots, will be robust against sensor and control error.

Using a model based on the omni-directional robots developed at the Institute of Physical and Chemical Research (RIKEN), we discuss the possibility of automatically generating a collision avoidance algorithm for autonomous mobile robots. To this end, we show that an effective collision avoidance algorithm for two robots can be generated by a very simple learning algorithm that simulates a naive human trial-and-error learning process, using only the robots' sensor outputs and a suitable reward function, where the exact form of the reward function is also learned autonomously by the robots. We also discuss how a robot can use its "experience" gained in a simple environment to adjust itself to a more complex environment, by automatically generating a collision avoidance algorithm for a three-robot situation utilizing a reduced state space resulting from the learning process for the case of two robots. The results of computer simulation and the experiments conducted at RIKEN using physical robots demonstrate the effectiveness of the collision avoidance algorithms generated and our learning-based approach.

A distributed system is said to be self-stabilizing if it will eventually reach a legitimate system state regardless of its initial state. Because of this property, a self-stabilizing system is extremely robust against failures; it tolerates any finite number of transient failures. The ring orientation problem for a ring is the problem of all the processors agreeing on a common ring direction. This paper focuses on the problem of designing a deterministic self-stabilizing ring orientation system with a small number of processor states under the distributed daemon. Because of the impossibility of symmetry breaking, under the distributed daemon, no such systems exist when the number n of processors is even. Provided that n is odd, the best known upper bound on the number of states is 256 in the link-register model, and eight in the state-reading model. We improve the bound down to 6/sup 3/=216 in the link-register model.

Let C and D be two distinct coteries under the vertex set V of a graph G=(V,E) that models a distributed system. Coterie C is said to G-dominate D (with respect to G) if the following condition holds: For any connected subgraph H of G that contains a quorum in D (as a subset of its vertex set), there exists a connected subgraph H' of H that contains a quorum in C. A coterie C on a graph G is said to be G-nondominated (G-ND) (with respect to G) if no coterie D(/spl ne/C) on G G-dominates C. Intuitively, a G-ND coterie consists of irreducible quorums. This paper characterizes G-ND coteries in graph theoretical terms, and presents a procedure for deciding whether or not a given coterie C is G-ND with respect to a given graph G, based on this characterization. We then improve the time complexity of the decision procedure, provided that the given coterie C is nondominated in the sense of Garcia-Molina and Barbara (1985). Finally, we characterize the class of graphs G on which the majority coterie is G-ND.

A distributed system consists of a set of processes and a set of communication links, each connecting a pair of processes. A distributed system is said to be self-stabilizing if it converges to a correct system state no matter which system state it starts with. A self-stabilizing system is considered to be an ideal fault tolerant system, since it tolerates any kind and any finite number of transient failures. In this paper, we investigate uniform randomized self-stabilizing mutual exclusion systems on unidirectional rings. As far as deterministic systems are concerned, it is well-known that there is no such system when the number 6 of processes (i.e., ring size) is composite, even if a fair central-daemon (c-daemon) is assumed. A fair daemon guarantees that every process will be selected for activation infinitely many times. As for randomized systems, regardless of the ring size, we can design a self-stabilizing system even for a distributed-daemon (d-daemon). However, every system proposed so far assumes a daemon to be fair, and effectively replies on this assumption. This paper tackles the problem of designing a self-stabilizing system, without assuming the fairness of a daemon. As a result, we present a randomized self-stabilizing mutual exclusion system for any size n (including composite size) of a unidirectional ring. The number of process states of the system is 2(n-1).

We consider the problem of computing a time-optimal motion for two omnidirectional robots carrying a ladder from an initial position to a final position in a plane without obstacles. At any moment during the motion, the distance between the robots remains unchanged and the speed of each robot must be either a given constant /spl upsi/, or O. A trivial lower bound on time for the robots to complete the motion is the time needed for the robot farther away from its destination to move to the destination along a straight line at a constant speed of /spl upsi/. This lower bound may or may not be achievable, however, since the other robot may not have sufficient time to complete the necessary rotation around the first robot (that is moving along a straight line at speed v) within the given time. We first derive, by solving an ordinary differential equation, a necessary and sufficient condition under which this lower bound is achievable. If the condition is satisfied, then a time-optimal motion of the robots is computed by solving another differential equation numerically. Next, we consider the case when this condition is not satisfied, and show that a time-optimal motion can be computed by taking the length of the trajectory of one of the robots as a functional and then applying the method of variational calculus. Several optimal paths that have been computed using the above methods are presented.

A group of autonomous agents can agree on a set of "social laws" in advance in order to reduce the complexity of conflict resolution later in the field when they are dispatched to achieve the given task. However, it is conceivable that under certain situations, the agents may have to violate the social laws to carry out the task more efficiently or even survive in the field. We thus consider the issue of fusing the social laws and a set of "super rules" for handling exceptions in the context of dynamic path planning for a group of autonomous mobile robots. We report some results that indicate that a fusion of social laws and super rules can help us to design effective algorithms.

Let U be a given set of nodes of a parallel computer system and assume that each node u in U has a piece of information $t(u)$ called a token. This paper discusses the problem of each $u \in U$ broadcasting its token $t(u)$ to all nodes in U. We refer to this problem as the group-gossiping problem, which includes the (conventional) gossiping problem as a special case. In this paper, we consider the group-gossiping problem in n-cubes under a circuit-switching model and propose an optimal group-gossiping algorithm for n-cubes under the model.

A mesh-bus computer is a parallel computer in which nodes (i.e., processors) are arranged on a two-dimensional array, and nodes on each row and nodes on each column, respectively, are connected by a shared bus. The nodes communicate with each other by exchanging packets through shared buses in CREW manner. Suppose that each node initially contains a piece of information called a token. A gossiping problem is the routing problem of exchanging tokens among all nodes in the computer, which has been studied extensively as a basic communication scheme for sharing information among nodes in a parallel computer. In this paper, we propose three gossiping algorithms for mesh-bus computers assuming that each packet can carry at most l tokens in a step, where l is a function of the number of all nodes. It is shown that by selecting the fastest algorithm among them, for each given function l, a lower bound on the gossiping time can be attained asymptotically.

In anonymous networks, the processors do not have identity numbers. We investigate the following representative problems on anonymous networks: (a) the leader election problem, (b) the edge election problem, (c) the spanning tree construction problem, and (d) the topology recognition problem. On a given network, the above problems may or may not be solvable, depending on the amount of information about the attributes of the network made available to the processors. Some possibilities are: (1) no network attribute information at all is available, (2) an upper bound on the number of processors in the network is available, (3) the exact number of processors in the network is available, and (4) the topology of the network is available. In terms of a new graph property called "symmetricity", in each of the four cases (1)-(4) above, we characterize the class of networks on which each of the four problems (a)(d) is solvable. We then relate the symmetricity of a network to its 1- and 2-factors.

For pt I see ibid. In anonymous networks, the processors do not have identity numbers. In Part I of this paper, we characterized the classes of networks on which some representative distributed computation problems are solvable under different conditions. A new graph property called symmetricity played a central role in our analysis of anonymous networks. In Part II, we turn our attention to the computational complexity issues. We first discuss the complexity of determining the symmetricity of a given graph, and then that of testing membership in each of the 16 classes of anonymous networks defined in Part I. It turns out that, depending on the class, the complexity varies from P-time to NP-complete or co-NP-complete.

Presents a new structural induction theorem for rings consisting of identical components that are modeled using a Petri net and a temporal logic formula. The theorem gives a condition in terms of the behavior of the rings of sizes k/spl minus/1 and k, k/spl ges/5, under which all rings of size k/spl minus/1 or greater exhibit "similar" behavior. Using the example of demand-driven token circulation, we show how the theorem can be applied to formally infer the correctness of a ring of any large size from that of a ring having fewer components.>

Abstract A graph‐theoretical model is presented for scheduling the transmission of messages in a computer network. A related wiring problem is also discussed; connections with classical edge colorings are exhibited and optimality properties are discussed. © 1993 by John Wiley & Sons, Inc.

The distributed k-mutual-exclusion problem (k-mutex problem) is the problem of guaranteeing that at most k processes at a time can enter a critical section at a time in a distribution system. A method proposed for the solution of the distributed mutual exclusion problem (i.e., 1-mutex problem) by D. Barbara and H. Garcia-Molina (1987) is an extension of majority consensus and uses coteries. The goodness of coterie-based 1-mutex algorithm strongly depends on the availability of coterie, and it has been shown that majority coterie is optimal in this sense, provided that: the network topology is a complete graph, the links never fail, and p, the reliability of the process, is at least 1/2. The concept of a k-coterie, an extension of a coterie, is introduced for solving the k-mutex problem, and lower and upper bounds are derived on the reliability p for k-majority coterie, a natural extension of majority coterie, to be optimal, under conditions (1)-(3). For example, when k=3, p must be greater than 0.994 for k-majority coterie to be optimal.>

The problem of searching for a mobile intruder in a simple polygon by a single mobile searcher is considered. This paper investigates the capabilities of searchers having different degrees of visibility by introducing the searcher having k flashlights whose visibility is limited to k rays emanating from his position, and the searcher having a point light source who can see in all directions simultaneously. This paper presents necessary and sufficient conditions for a polygon to be searchable by various searchers. The paper also introduces a class of polygons for which the searcher having two flashlights is as capable as the searcher having a point light source, and it gives a simple necessary and sufficient condition for such polygons to be searchable by the searcher having two flashlights. The complexity of generating a search schedule under some of these conditions is also discussed. Many of the results are proved using chord systems that represent the visibility relations among the vertices and edges of the given polygon.

The problem of searching for a mobile robber in a simple polygon by a number of searchlights is considered. A searchlight is a stationary point which emits a single ray that cannot penetrate the boundary of the polygon. The direction of the ray can be changed continuously, and a point is detected by a searchlight at a given time if and only if it is on the ray. A robber is a point that can move continuously with unbounded speed. First, it is shown that the problem of obtaining a search schedule for an instance having at least one searchlight on the polygon boundary can be reduced to that for instances having no searchlight on the polygon boundary. The reduction is achieved by a recursive search strategy called the one-way sweep strategy. Then various sufficient conditions for the existence of a search schedule are presented by using the concept of a searchlight visibility graph. Finally, a simple necessary and sufficient condition for the existence of a search schedule for instances having exactly two searchlights in the interior is presented.

Article Computing on an anonymous network Share on Authors: Masafumi Yamashita Department of Electrical Engineering, Hiroshima University, 724 Japan Department of Electrical Engineering, Hiroshima University, 724 JapanView Profile , Tiko Kameda School of Computing Science, Simon Fraser University, Bumaby, B.C., Canada V5A 1S6 School of Computing Science, Simon Fraser University, Bumaby, B.C., Canada V5A 1S6View Profile Authors Info & Claims PODC '88: Proceedings of the seventh annual ACM Symposium on Principles of distributed computingJanuary 1988 Pages 117–130https://doi.org/10.1145/62546.62568Online:01 January 1988Publication History 50citation547DownloadsMetricsTotal Citations50Total Downloads547Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Three-dimensional VLSI (in short, 3-D VLSI) is a new device technology that is expected to realize high performance systems. In this paper, we propose an image processing architecture based on 3-D VLSI consisting of optically-connected layers. Since the optical inter-layer connection seems to have some of useful functions due to isotropic radiation of the light, we algebraicly formulate them as the picture processing operators. Moreover, we show that the operators are available for applications such as template matching. The availability of a proposed template matching algorithm is verified by simulation.