Self-stabilizing message-driven protocols are defined and discussed. The class weak exclusion that contains many natural tasks such as $\ell$-exclusion and token passing is defined, and it is shown that in any execution of any self-stabilizing protocol for a task in this class, the configuration size must grow at least in a logarithmic rate. This last lower bound is valid even if the system is supported by a time-out mechanism that prevents communication deadlocks. Then we present three self-stabilizing message-driven protocols for token passing. The rate of growth of configuration size for all three protocols matches the aforementioned lower bound. Our protocols are presented for two-processor systems but can be easily adapted to rings of arbitrary size. Our results have an interesting interpretation in terms of automata theory.

A distributed system is self-stabilizing if it can be started in any possible global state. Once started the system regains its consistency by itself, without any kind of outside intervention. The self-stabilization property makes the system tolerant to faults in which processors exhibit a faulty behavior for a while and then recover spontaneously in an arbitrary state. When the intermediate period in between one recovery and the next faulty period is long enough, the system stabilizes. A distributed system is uniform if all processors with the same number of neighbors are identical. A distributed system is dynamic if it can tolerate addition or deletion of processors and links without reinitialization. In this work, we study uniform dynamic self-stabilizing protocols for leader election under readwrite atomicity. Our protocols use randomization to break symmetry. The leader election protocol stabilizes in O(/spl Delta/D log n) time when the number of the processors is unknown and O(/spl Delta/D), otherwise. Here /spl Delta/ denotes the maximal degree of a node, D denotes the diameter of the graph and n denotes the number of processors in the graph. We introduce self-stabilizing protocols for synchronization that are used as building blocks by the leader-election algorithm. We conclude this work by presenting a simple, uniform, self-stabilizing ranking protocol.

We introduce a novel technique, the scheduler luck game (in short sl-game) for analyzing the performance of randomized distributed protocols. We apply it in studying uniform self-stabilizing protocols for leader election under read/write atomicity. We present two protocols for the case where each processor in the system can communicate with all other processors and analyze their performance using the sl-game technique.>

In this paper, we present efficient implementations of strong shared memory primitives.We use the asynchronous shar-ed memory model.In this model, processes communicate by applying primitive operations (e.g.

This paper studies the wait-free consensus problem in the asynchronous shared memory model. In this model, processors communicate by shared registers that allow atomic read and write operations (but do not support atomic test-and-set). It is known that the wait-free consensus problem cannot be solved by deterministic protocols. A randomized solution is presented. This protocol is simple, constructive, tolerates up to $n - 1$ processors crashes (where n is the number of processors), and its expected run-time is $O(n^2 )$.

Two tasks of communication in a multihop synchronous radio network are considered: Point-to-point communication and broadcast (sending a message to all nodes of a network). Efficient protocols for both problems are presented. Even though the protocols are probabilistic, it is shown how to acknowledge messages deterministically. Let n, D, and $\Delta $ be the number of nodes, the diameter and the maximum degree of our network, respectively. Both protocols require a setup phase in which a BFS tree is constructed. This phase takes $O((n + D\log n)\log \Delta )$ time. After the setup, k point-to-point transmissions require $O((k + D)\log \Delta )$ time on the average. Therefore the network allows a new transmission every $O(\log \Delta )$ time slots. Also, k broadcasts require an average of $O((k + D)\log \Delta \log n)$ time. Hence the average throughput of the network is a broadcast every $O(\log \Delta \log n)$ time slots. Both protocols pipeline the messages along the BFS tree. They are always successful on the graph spanned by the BFS tree. Their probabilistic behavior refers only to the running time. Using the above protocols the ranking problem is solved in $O(n\log n\log \Delta )$ time. The performance analysis of both protocols constitutes a new application of queueing theory.

Two implementations of a multi-writer, multi-reader, atomic register are presented. The physical registers used by the first implementation are single-writer, multi-reader, atomic registers; the physical registers used by the second implementation are single-reader, single-writer, atomic registers. Both implementations are optimal with respect to the two most important complexity criteria: In both implementation the space complexity is logarithmic, thus matching the lower bound proven by Cori and Sopena; and the time complexity is linear, thus matching the obvious lower bound. These implementations improve upon the space complexity of all previous implementations in their respective classes, by an exponential factor.

A modular hierarchical model for controlling robots is presented. This model is targeted mainly for research and development, enabling researchers to concentrate on a certain specific task of robotics, while using existing building blocks for the rest of the controller application. The problems with which robotics researchers and engineers are faced when trying to use existing commercial robots are detailed. Based on this discussion, the authors propose TERM, a general model for robot control. The viability of the model is demonstrated by implementing a general-purpose robot controller. For this purpose several building blocks were developed. Using these building blocks three robot systems were assembled: a large system for an industrial PUMA robot and two smaller ones for educational robots. The system is currently used for research in nonlinear and adaptive control, path planning and multirobot applications.>

Article Resource bounds for self stabilizing message driven protocols Share on Authors: Shlomi Dolev Dept. of Computer Science, Technion, Israel Dept. of Computer Science, Technion, IsraelView Profile , Amos Israeli Dept. of Computer Science, Technion, Israel Dept. of Computer Science, Technion, IsraelView Profile , Shlomo Moran Dept. of Computer Science, Technion, Israel Dept. of Computer Science, Technion, IsraelView Profile Authors Info & Claims PODC '91: Proceedings of the tenth annual ACM symposium on Principles of distributed computingJuly 1991 Pages 281–293https://doi.org/10.1145/112600.112624Online:01 July 1991Publication History 22citation195DownloadsMetricsTotal Citations22Total Downloads195Last 12 Months4Last 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

No abstract available.

volves the introduction of a new type of single player token games which are of an independent interest.

Two tasks of communication in a multi-hop synchronous radio network are considered: point-topoint communication and broadcast (sending a message to all nodes of a network).Efficient protocols for both problems are presented, Even though the protocols are probabilistic, it is shown how to acknowledge messages deterministically.Let n, D, and A be the number of nodes, the diameter and the maximum degree of our network, respectively.Both protocols require a setup phase in which a BFS tree is constructed.This phase takes 0 ((n + Dlogn)logA) time.After the setup, k point-to-point transmissions require 0 ((k+D)logA) time on the average.Therefore the network allows a new transmission every 0 (logA) time slots, Also, k broadcasts require an average of O((k+D)logAlogn) time.Hence the average throughput of the network is a broadcast every O(logAlogn) time slots.Both protocols pipeline the messages along the BFS tree.They are always successful on the graph spanned by 'the BFS tree.Their probabilistic behavior refers only to the running time.Using the above protocols rhc ranking problem is solved in 0 (nlognlogA) time.The performance analysis of both protocols constitutes a new application of queueing theory.

Time-stamps are numerical labels which enable a system to keep track of temporal precedence relation among its data elements. Traditionally time-stamps are used as unbounded numbers and inevitable overflows cause a loss of this precedence relation. In this paper we develop a complete theory of bounded time-stamps. Time-stamp systems are defined and the complexity of their implementation is fully analyzed. This theory gives a very general tool for converting timestamp based protocols to bounded protocols. The generality of this theory is demonstrated by novel, conceptually simple, protocols for a multiuser atomic registers, as well as by proving for the first time a non-trivial lower bound for such a register.

We investigate an asynchronous model of concurrent computations, where processors communicate by shared registers that allow atomic read and write operations (but do not support atomic test-and-set).For this model, we define a general notion of processor coordination, and study the possibility and complexity of achieving coordination.Our definition includes, as special cases, mutual exclusion and asynchronous agreement.It is shown that the coordination problem cannot be solved by means of a deterministic protocol even if the system consists of only two processors.This impossibility result holds for the most powerful type of shared atomic registers and does not assume symmetric protocols.The impossibility result is contrasted by a variety of eficient randomized protocols, that achieve fast coordination for systems of arbitrary number of processors n.These protocols are all fairly simple, constructive, and their ezpectedrun-time is polynomial in n, even in the presence of an adaptive

A parallel algorithm for finding Euler circuits in graphs is presented. Its depth is log |E| and it employs |E| processors. The computational model considered is the PRAM (the shared memory model).