Inexpensive but accurate hardware clocks are now commonplace on many systems. A clock synchronization protocol can keep the collection of clocks for a group of networked systems roughly synchronized without the expenditure of a great deal of processor time or network bandwidth. As long as the bounded skew between clocks is taken into account, rough real time can provide an intuitive and valuable mechanism for providing a notion of order in a distributed system. This paper presents a straightforward token-based protocol for the detection of distributed deadlock under the single resource model. It uses clock values as token time stamps to ensure that exactly one process in a deadlock cycle, the process that completed the cycle, detects the deadlock and aborts, breaking the deadlock. The clock-valued time stamps also ensure that no false deadlocks are detected, without additional protocol to eliminate obsolete tokens. Arguments for the correctness of the protocol are developed.

We present the design of a systems laboratory intended for advanced undergraduates and graduate students. The laboratory provides an environment in which students are given complete (root) control of systems with essentially unrestricted access to the Internet. This is achieved without jeopardizing the security of the departmental network of which the laboratory is a part. Students in the laboratory are also given a secure environment in which to do their work. Such a laboratory is most valuable in advanced courses in operating systems and networks in which students implement and evaluate algorithms and policies subjected to real workloads. It is also valuable as a facility for research on systems and network topics, providing an open, yet safe, environment in which to work.

Recently, several flavours of UNIX have appeared which run on inexpensive personal computers. Further, the source code for these operating systems is freely available. This makes offering courses that include realistic kernel programming feasible in an academic environment. However, root access is required in order to modify a system's kernel. This poses a potential security threat both to other systems on the network and to other users of a single machine. This paper presents a lab design which securely integrates machines with untrusted users acting as root into a secured network, and which securely allows multiple users root access to the same machine.

Causality, as made concrete by Lamport's "happened before" relation, is the central underlying basis in the design of optimistic protocols for checkpoint and recovery. After the recovery of a formerly failed process, all events and messages which causally follow the events and messages discarded by restoration of a state checkpoint must be discarded also. The isomorphism between causality and vector time is well-known. That isomorphism is exploited here in order to develop and verify a simple and effective protocol which explicitly uses the causal partial order, through the use of vector time, in order to rollback a computation in response to a process failure.>

Flush channels generalize conventional asynchronous communication constructs such as virtual circuits and datagrams. They permit the programmer to specify receipt-order restrictions on a message-by-message basis, providing an opportunity for more concurrency in a distributed program. A Hoare-style partial correctness verification methodology for distributed systems which use flush channel communication is developed, and it is shown that it it possible to reason about such systems in a relatively natural way.>

Flush channels generalize more conventional asynchronous message passing protocols. A distributed system that uses flush channels allows a programmer the flexibility of specifying the delivery order of each message in relation to other messages transmitted on the channel. An implementation technique that follows directly from a verification methodology for flush channels is presented. A relatively formal argument in support of the technique is included.>

Two principles are proposed for proving and tracing distributed programs: it is necessary to assert in proofs only what can be readily traced, and trace just what can be asserted in the proofs. A proof system and tracing strategy are described for CSP programs based on these principles, using vector time and control variables, not auxiliary variables, to represent control state, and stressing local rather than global reasoning.>

The authors present a general methodology for bounding the range of sequence numbers utilized in a distributed program to order events. This methodology requires explicit knowledge of bounds on the rate at which processes may increment sequence numbers and the time required to transmit a message. It may also require the inclusion of additional synchronization in a distributed application which utilizes the bounded sequence numbers. The methodology is demonstrated in three contexts. It is shown how a scheme for bounding sequence numbers on requests for network mutual exclusion is consistent with the methodology. Sequence numbers are bound in a network mutual exclusion protocol. The methodology is utilized to bound the size of sequence numbers used in successive fault-tolerant broadcasts among a group of fail-stop processors. In all three cases, with totally different message-passing patterns and means of incrementing sequence numbers, consistent application of the methodology is stressed.>

A technique is presented by which a centralized service facility in a distributed system can honor client requests in the global order in which those requests were made. Unlike traditional approaches to this problem, the server provides immediate service to its clients. Immediate service requires that, upon receipt of a request which is the oldest unserved message, the server must grant the service immediately. No additional message passing may be used by the server in order to serve that request. The approach requires that certain information be appended to every message in the system. This piggybacked information allows the server to infer the order in which service should be granted to arriving request messages. Increased message length is thus explicitly traded for fewer messages and faster response to requests at the server. That overhead is proportional to the number of processors in the system. In time-critical distributed applications immediate service offers a means by which service response time can be substantially reduced. It is argued that, under certain reasonable assumptions about the network and process behavior, immediate service can outperform the logical timestamp approach for very large systems (and certainly for small systems).>

Concurrent Control Abstraction Language, CCAL, is an interpreted language which provides no particular control regime to the user. CCAL instead supports five primitive operations which manipulate an abstract model of inter-procedural control. This model is intrinsically concurrent, and the user is allowed to construct high-level concurrent control operations from the primitives (hence, control abstraction). The primary use of CCAL is as a vehicle by which rapid prototyping of application specific control forms may be done and as a tool for the construction and evaluation of novel control forms, especially control forms for highly concurrent and distributed systems. The CCAL interpreter is implemented as a distributed program on a network of Vaxen and Sun-3 workstations under 4.2bsd and 4.3bsd Unix1. CCAL programs appear as multi-process programs in a shared memory system. Both true and apparent concurrency are possible. This paper describes the control abstraction facilities offered by the CCAL interpreter, its use, and implementation strategies in the distributed environment.