Lamport defined three classes of communication registers: safe, regular, and atomic. Wait-free implementations of one register class from a weaker class abound in the literature. However, results establishing the intrinsic complexity of such implementations are relatively scarce. In this paper, we consider the problem of implementing an n -valued single reader, single writer atomic register A from two regular registers, BUF and R , where BUF is a regular register that only the writer of A can write and R is a regular register that only the reader of A can write. (Lamport proved that there cannot be an implementation without R , so R is at least 2-valued in any implementation.) We present an almost space optimal implementation. Specifically, our results are: (1) An implementation for which BUF is 2 n -valued and R is 2-valued; and (2) A lower bound stating that, in any implementation, regardless of how large R is, BUF must be at least (2 n −1)-valued.

This paper presents a suite of randomized broadcast protocols for the problem of broadcasting a message in multihop radio networks. The protocols are compared with the randomized broadcast protocol by R. Bar-Yehuda et al. (1989, 1991, 1992). The time complexity of one of the randomized broadcast protocols presented in this paper is shown, by simulation, to be much better than those of other protocols in most of the typical cases.>

The problem of collecting responses in multihop radio networks is considered. A given node is to collect a specified number of responses from nodes in a radio network. The problem arises in several applications of distributed systems. A deterministic protocol and a randomized protocol for the problem are presented. The two protocols are analyzed and their performances are compared.>

In the difficult area of distributed algorithms, it is useful to find tools that have wide application.Here we consider a model in which communication is through asynchronous, atomic reads and writes of shared memory.One of our main results is a lemma showing that a single fail-stop failure can lead to ambiguity whenever a choice must be made.Thii lemma can be used to prove a variety of impossibility results and lower bounds.We use the lemma to give a simple proof of the optimality of our solution to the f-assignment problem.The L-assignment problem requires that a group of processors compete for a pool of distinct resources with the restriction that a limited number of processors can halt unexpectedly.(The problem differs from the normal &exclusion problem in that an explicit assignment of resources must be made.)Use of the lemma is also demonstrated by giving a simple proof for the lower bound of the pure buffers version of the concurrent reading while writing problem.Some other problems where the lemma applies are mentioned.

Abstract A maximum independent set of a graph is a set of vertices with maximum cardinality such that no pair of vertices is connected by an edge. Choukhmane and Franco have presented a polynomial time approximation algorithm for the maximum independent set problem in cubic planar graphs. If M is taken as the ratio of the size of the independent set produced by their algorithm to the size of a maximum independent set of the input graph, then they show that their algorithm gives M ⩾ 6/7 for any cubic planar graph and M ⩾ 7/8 for a triangle‐free cubic planar graph. We give a new, stronger proof of thier result. The new proof shows that their algorithm actually gives M ⩾ 7/8 for all cubic planar graphs.

A self-stabilizing system has the property that, no matter how it is perturbed, it eventually returns to a legitimate configuration. Dijkstra originally introduced the self-stabilization problem and gave several solutions for a ring of processors in his 1974 Communications of the ACM paper. His solutions use a distinguished processor in the ring, which effectively acts as a controlling element to drive the system toward stability. Dijkstra has observed that a distinguished processor is essential if the number of processors in the ring is composite. We show, by presenting a protocol and proving its correctness, that there is a self-stabilizing system with no distinguished processor if the size of the ring is prime. The basic protocol uses Θ ( n 2 ) states in each processor when n is the size of the ring. We modify the basic protocol to obtain one that uses Θ ( n 2 /ln n ) states.

We present a simple and efficient algorithm for the FIFO allocation of k identical resources among asynchronous processes that communicate via shared memory. The algorithm simulates a shared queue but uses exponentially fewer shared memory values, resulting in practical savings of time and space as well as program complexity. The algorithm is robust against process failure through unannounced stopping, making it attractive also for use in an environment of processes of widely differing speeds. In addition to its practical advantages, we show that for fixed k , the shared space complexity of the algorithm as a function of the number N of processes is optimal to within a constant factor.

An algorithm is given for the multi-writer version of the Concurrent Reading While Writing (CRWW) problem. The algorithm solves the problem of allowing simultaneous access to arbitrarily sized shared data without requiring waiting, and hence avoids mutual exclusion. This. demonstrates that a quite complicated concurrent control problem can be solved-without eliminating the efficiency of parallelism. One very important aspect of the algorithm are the tools developed to prove its correctness. Without these tools, proving the correctness of a solution to a problem of this complexity would be very difficult.

We present a simple, efficient protocol for constructing single-writer, multi-reader atomic shared values from singlewriter, multi-reader non-atomic (%egular") shared values.This solves the last open problem in the Concurrent Reading While Writing hierarchy.It is now known how to construct a multi-writer, multi-reader atomic shared value given only single-reader, single-writer non-atomic ("safe") shared bits.The protocol given here is remarkably simple and efficient.The total amount of shared space to communicate a shared value with a range of V to n readers is just O(n + log IV]) multi-reader regular bits, which is provably optimal (with very small constant factors).Similarly, the amount of communication (reading and writing of copies of the simulated shared values) required by readers and writers is also optimal.The simplicity of the protocol results in a short and easily understood proof of correctness.Great care has been taken to completely describe the protocol to avoid ambiguities.We also describe several variations of the protocol which optimize other goals.

For many students, the first chance to produce software as part of a team comes with the first work experience outside a university. The difficulties of working with others are compounded by the problems of working in a new environment and for a client with ambiguous and changing goals. Although it is difficult to approximate the "real world" accurately in an academic course, we have implemented two full-year course sequences which apparently give our students some insight into the problems they will face when they leave the university. One course requires the development and implementation of a software product by a team of undergraduates, and the other requires experienced graduate students to act as supervisors for the undergraduate projects. We describe the content and structure of these two sequences, emphasizing how they support and enhance each other. We believe other curricula would benefit from similar courses.

An analysis is made of the shared memory requirements for implementing mutual excluslon of N asynchronous parallel processes m a model where the only primitive communication mechamsm is a general test-and-set operation on a single shared variable.While two variable values suffice to tmplement simple mutual exclusion without deadlock, it is shown that any solution whJch avoids possJble lockout of processes requires at least 2~ + ½ values A technical restnctmn on the model increases this requtrement to N/2 values, while achieving a fixed bound on wamng further increases the reqmrement to N + 1 values.These bounds are shown to be nearly optimal, for algorithms are exhibited for the last two cases which use [N/2J + 9 and N + 3 values, respectively All of the lower bounds apply afortiori to the space requirements for weaker primitives, such as P and V, using busy waiting Categones and Subject Descnptors D 4 1 [Operating Systems]" Process Management--mutual exclusion; D 4 2 [Operating Systems]' Storage Management F ! ![Computation by Abstract Devices]: Models of Computation, F !.2 [Computation by Abstract Devices]" Modes ofComputaUon--parallehsm, F 2 [Theory of Computation] Analysis of Algorithms and Problem Complexity General Terms Algonthms, Performance, Theory

A new solution to the problem of deadlock-free mutual exclusion of N processes is given which uses less shared space than earlier solutions (one variable which may take on N values and N binary variables). The solution uses only indivisible reads and writes of shared variables for communication and is symmetric among the processes. Two definitions of symmetry are developed. The strong definition of symmetry requires that all processes be identically programmed and be started in identical states. However, this definition does not allow any solution to the problem of deadlock-free mutual exclusion using only reads and writes. The weaker definition admits the solution given. It is also shown that under weak symmetry N shared variables, at least one of which must be able to take on N values, are necessary.

Upper and lower bounds are proved for the shared space requirements for solution of several problems involving resource allocation among asynchronous processes. Controlling the degradation of performance when a limited number of processes fail is of particular interest.