Techniques for implementing the coterie scheme and for obtaining optimal coteries for a system are presented. Central to the techniques is the notion of an acceptance set, which is an alternative representation of the information contained in a coterie. Using this concept, the coterie scheme can be implemented efficiently, and an optimal coterie for a system can be obtained more directly. The problem of determining an optimal acceptance set is formulated as a sparse zero-one linear programming problem. Hence, the optimization problem can be handled using the very rich class of existing techniques for solving such problems. Experimental results indicate that the optimization approach is feasible for up to eight nodes at least. The ways in which the scheme and the optimization approach can be used for systems that distinguish between read and write operations are indicated.>

A dynamic voting scheme is presented that enhances the availability of replicated files in a distributed system in the presence of network partitions. In such situations, the proposed scheme maintains consistency of replicated files by imposing the following constraint; a node can commit a file update only if its current enclosing group is a majority of the nodes that participated in the most recent update on the file. Thus, the number of nodes that constitutes a majority is reduced dynamically upon successive partitions. Compared to other dynamic voting schemes, the proposed scheme provides higher availability by taking into account partitions that occur between successive file updates. Towards this end, each node maintains, for each file copy, a view of the network in terms of partition groups. When a file update is attempted, the node updates its view by taking into account partitions occurred since previous update. It refines the view, further using views held by other reachable nodes. Another merit of the proposed scheme is that it does not require failures and repairs of links and nodes to be detected instantaneously by all nodes. Different nodes may have different views of the network at any time.>

A replicated database system may partition into isolated groups in the presence of node and link failures. When the system has partitioned, a pessimistic scheme maintains availability and consistency of replicated data by ensuring that updates occur in at most one group. A pessimistic scheme is called a static scheme if these distinguished groups are determined only by the membership of different groups in the partitioned system. In this paper, we present a new static scheme that is more powerful than voting. In this scheme, the set of distinguished groups, called an acceptance set, is chosen at design time. To commit an update, a node checks if its enclosing group is a member of this acceptance set. Using an encoding scheme for groups, this check is implemented very efficiently. Another merit of the proposed scheme is that the problem of determining an optimal acceptance set is formulated as a sparse 0-1 linear programming problem. Hence, the optimization problem can be handled using the very rich class of existing techniques for solving such problems. Based on our experiments, we feel that this optimization approach is feasible for systems containing up to 10 nodes (copies).

There have been several proposals in the literature for communication and synchronisation primitive for distributed programs. Many of them advocate a general nondeterministic choice mechanism, using which a process waits until it sends a message to some member of a specified group of processes, or receives a message from some member of another specified group of processes. In this paper, we present a distributed synchronisation scheme for implementing this nondeterministic choice mechanism. The scheme is fair as well as quite efficient in terms of storage and control messages used for synchronisation, and is appropriate to be implemented within a kernel that acts as a runtime support for distributed programs.

A distributed system is an interconnected network of computing elements or nodes, each of which has its own storage. A distributed program is a collection of processes which execute asynchronously, possibly in different nodes of a distributed system, and they communicate with each other in order to realize a common goal. In such an environment, a group of processes may sometimes get involved in a communication deadlock. This is a situation in which each member process of the group is waiting for some member to communicate with it, but no member is attempting communication with it. The author presents an algorithm for detecting such communication deadlocks. The algorithm is distributed; i.e. processes detect deadlocks during the course of their communication, without the aid of a central controller. The detection scheme does not presume any a priori structure among processes, and detection is made `on the fly' without freezing normal activities. The scheme does not require any storage whose size is determined by the size of the network, and hence is suitable also for an environment where processes are created dynamically.

A distributed program is a collection of several processes which execute concurrently, possibly in different nodes of a distributed system, and which cooperate with each other to realize a common goal. In this paper, we present a design of communication and synchronization primitives for distributed programs. The primitives are designed such that they can be provided by a kernel of a distributed operating system. An important feature of the design is that the configuration of a process, i.e., identities of processes with which the process communicates, is specified separately from the computation performed by the process. This permits easy configuration and reconfiguration of processes. We identify different kinds of communication failures, and provide distinct mechanisms for handling them. The communication primitives are not atomic actions. To enable the construction of atomic actions, two new program components, atomic agent and manager are introduced. These are devoid of policy decisions regarding concurrency control and atomic commitment. We introduce the notion of conflicts relation using which a designer can construct either an optimistic or a pessimistic concurrency control scheme. The design also incorporates primitives for constructing nested atomic actions.

Deadlock handling is an important component of transaction management in a database system. In this paper, we contribute to the development of techniques for transaction management by presenting an algorithm for detecting deadlocks in a distributed database system. The algorithm uses priorities for transactions to minimize the number of messages initiated for detecting deadlocks. It does not construct any wait-for graph but detects cycles by an edge-chasing method. It does not detect any phantom deadlock (in the absence of failures), and for the resolution of deadlocks it does not need any extra computation. The algorithm also incorporates a post-resolution computation that leaves information characterizing dependence relations of remaining transactions of the deadlock cycle in the system, and this will help in detecting and resolving deadlocks which may arise in the future. An interesting aspect of this algorithm is that it is possible to compute the exact number of messages generated for a given deadlock configuration. The complexity is comparable to the best algorithm reported. We first present a basic algorithm and then extend it to take into account shared and exclusive lock modes, simultaneous acquisition of multiple locks, and nested transactions.

Abstract In this paper we present some issues encountered in the implementation of a kernel for a multiprocessor system using a high level language called CCNPASCAL. We present the nature of the problem concerning each issue, the solutions we adopted and possible better alternatives which we could not adopt for various reasons.