We develop a framework that helps in developing understanding of a fault-tolerant distributed system and so helps in designing such systems. We define a unit of computation in such systems, referred to as a molecule, that has a well defined interface with other molecules, i.e. has minimal dependence on other molecules. The smallest such unit-an indivisible molecule-is termed as an atom. We show that any execution of a fault-tolerant distributed computation can be seen as an execution of molecules/atoms in a partial order, and such a view provides insights into understanding the computation, particularly for a fault tolerant system where it is important to guarantee that a unit of computation is either completely executed or not at all and system designers need to reason about the states after execution of such units. We prove different properties satisfied by molecules and atoms, and present algorithms to detect atoms in an ongoing computation and to force the completion of a molecule. We illustrate the uses of the developed work in application areas such as debugging, checkpointing, and reasoning about stable properties.>

High performance distributed computing systems require high performance communication systems. Distributed modeling and implementation of these communication systems is important. Toward this goal, the authors refine the process-to-channel/sub agent/-to-process (PCP) model of asynchronous distributed communication. While the PCP model provides a versatile and succinct mechanism for specifying and comparing different types of channels, it is inherently centralized. The refined model presented here, the process-to-channel/sub agent/-to-channel/sub agent/-to-process (PCCP) communication model, is amenable to distributed modeling and implementation of channels. The usefulness of the PCCP model is demonstrated by presenting a distributed implementation of hierarchical F-channels.>

An F-channel can permit as much concurrency as a non-first-in-first-out (FIFO) communication channel and yet retain the properties of a FIFO channel that lead to simplicity of reasoning in design and proofs of the correctness of distributed algorithms. The author presents an implementation of an F-channel on top of a non-FIFO channel that derives its non-FIFO nature from a message taking any of the alternate paths from the source to the destination in the underlying network in which each channel is either an F-channel implemented using some other implementation or recursively using the implementation presented or a FIFO channel. The correctness of the implementation is proven.>

The problem of scheduling n independent jobs on an m-dimensional hypercube system to minimize the finish time is studied. Each job J/sub i/, where 1>

We have noticed two problems with viewing a process as a sequence of events. The first problem is the complete loss of information about potential intra-process concurrency for both sequential and distributed computations, and partial loss of information about potential inter-process concurrency for distributed computations. The second problem is that the resulting reasoning framework does not lend itself to refinement (from sequential computing or a given set of distributed processes) to a preferable set of distributed processes. We argue that it is more natural to view a computation, either distributed or sequential, as a partially ordered set of events. Doing so leads to a view, called passive-space and time view, which we propose. To aid users of the relation "Affects" in developing algorithms, we define vector clocks, that are global logical clocks, so that the relation "Affects", and hence all potential concurrency, between events can be identified from their timestamps assigned.>

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.>

A simple model of asynchronous distributed communication, the process-to-channel/sub agent/-to-process (PCP) model, is presented. This model is used as a framework for presenting channel grammars that specify channel behavior. The PCP model, in conjunction with channel grammars, provides a versatile and succinct mechanism for specifying and comparing different types of channels, as well as for designing channel implementations. The usefulness of these tools is demonstrated by presenting an implementation of hierarchical F-channels, which are channels based on hierarchical communication speeds and F-channels.>

The authors define a relation, 'affects', between every pair of events based on a relation 'locally affects' for each process between each pair of events on the process. A mechanism for timestamping events is defined such that 'affects' relation, and so potential concurrency, between events can be inferred from their timestamps. A timestamping mechanism is presented such that potential concurrency can be inferred partially/completely and the extent of such inferring depends on the costs associated with the mechanism. Inferring 'affects' relationship can be used for debugging and for inferring potential concurrency between events in traces of executions.>

An F-channel can permit as much concurrency as a nonFIFO channel and yet retain the properties of a FIFO channel that leads to simplicity of reasoning in design and proofs of the correctness of distributed algorithms. This is one of the major reasons that makes it preferable to a FIFO channel and make its implementation important. This and other reasons for its superiority over a FIFO channel are discussed, and it is proposed that systems should provide implementation of F-channels. Reasons are discussed for this proposal which are based on the principle that a system should provide an interface to the users that makes algorithm design easy and that leads to efficient user efforts and system operation. Implementation of an F-channel on top of a nonFIFO channel is presented.>

The authors define basic units of computation in distributed systems, whether communicating synchronously or asynchronously, as comprising indivisible logical units of computation that take the system from one ground state to another. It is explained how a computation can be viewed as a partial order over the basic units of the computation. The problem of detecting the basic units is considered. One algorithm for creating ground states during a computation in an asynchronously communicating system with FIFO channels is given, and an existing algorithm that implicitly creates ground states in a synchronously communicating system is referenced. The significance of the basic unit is explained, and its applications are given.>

The problem of scheduling n independent jobs on an m-dimensional hypercube system to minimize the finish time is discussed. After some preliminary definitions are given, it is shown that a simple nonpreemptive algorithm, called largest dimension first, can have an asymptotic optimal performance and an absolute bound no worse than 2-1/2/sup m/. An absolute lower bound for the schedules generated by any algorithm using decreasing dimension lists is proved. A preemptive scheduling algorithm is also given.>

A distributed algorithm based on echo algorithms is presented which constructs the minimum-weight spanning tree in a general undirected graph. In the worst case, the algorithm needs at most (2m+2(n-1) log (n/2)) messages and (2d log n) time, where d is the diameter of the network. In the best case, it needs only 2m messages and 2d time. The algorithm works in phases, and each phase consists of a down wave and an up wave. When the number of fragments is cut by at least one half in each phase, it needs at most O(log n) phases. On average, the algorithm needs only (m) messages and O(d) time. The algorithm itself is simple, so that other distributed algorithms based on it can be derived more easily.>

The authors evaluate and compare the performance of two concurrency control protocols for distributed databases with multiversioned entities, assuming that each transaction incrementally declares its access set from the successive parts of the preordered entities. The first protocol is called protocol proposed (PP). The second is a variant of the protocol proposed by D.P. Reed (1978), here called RP1. Performance results for these protocols are collected using simulations. Key performance issues of PP are studied and relative performance of PP and RP1 is compared. Extra memory requirement is the most important cost for PP, while the cost associated with abortion of transactions are most important for RP1. For slow communication networks, at all workloads except some range of low workloads, PP performs better than RP1. For fast networks, between low to very high workloads RP1 performs better for a range of parameters. At extremely high workloads, both perform poorly, but the higher memory requirement of PP is more tolerable than the high abortion rate of RP1. A protocol similar to PP is proposed that permits universioned entities and so does not have extra memory cost and has the advantages of PP.>

This paper presents a protocol for improving concurrency and preserving consistency in databases with multi-versioned entities: the database could be either centralized or distributed and may or may not have data replication. In the proposed protocol entities are assigned an order and each transaction accesses entities in this order, with possibly skipping entities that need not be accessed: the out-of-order accesses are permitted at an additional costs. Also, each transaction carries with it, as it moves along the pre-ordered entities, the state information about all preceding transactions which must execute logically before this transaction at all succeeding entities to ensure serializability of transactions. At each entity, a transaction executes logically after all the transactions in the state carried to the entity by the transaction.