Processor failures not leading to a network partition are considered, and the issue of computing associative functions in spite of processor failures is addressed. An intuitive and fundamental result formally proved is that failure detection and computing associative functions are equivalent in faulty networks: one can be performed if and only if the other can be performed. Protocols and impossibility results in various system models are presented in the context of computing associative functions and solving topological problems.>

The problem of correctly identifying the faulty processors and links in a distributed system where faulty behavior is unrestricted (Byzantine) is examined. A very general class of algorithms called evidence-based diagnosis algorithms is proposed that encompasses all past approaches to the diagnosis problem. An algorithm is presented which is proven optimal in this class. It is further shown that, in the worst case, no evidence-based diagnosis algorithm can guarantee that its diagnosis is both correct and complete, when evidence can be false. It is argued both analytically and from experimental data that in systems of N processors of which t can be faulty, the complexity of this algorithm is O(max(2 to the power of t/sup 2/, N/sup 2/)).>

Environments where read-only transactions predominate update transactions are considered. The notion of a group in replicated databases, the recognition of which maximizes the data availability for read-only transactions in error-prone environments, is developed. It is shown that the group identification problem is NP-complete. Replica control algorithms that attempt to approximately determine groups are presented. In one algorithm, groups are determined dynamically; in the other techniques, groups are predefined. It is shown formally that both approaches yield algorithms that preserve the consistency of the database. In the environments considered, the approaches presented are shown to yield significant improvements over other fault-tolerant replica control algorithms.>

An analytic model is presented for the performance of a commit protocol which considers both the communication and local processing. It is shown that the local queuing delays are significant when the number of atomic actions is sufficiently large. The single most important parameter in determining the effect of commit protocols on the system performance is believed to be the heavy dependence on logging and hence the high performance penalities exacted by I/O operations.>

The problem of recognizing whether a given network is a tree, ring, star, complete graph, or bipartite graph is considered. Unified algorithms to recognize if the network is any one of the above are presented in each of three classes of algorithms-with centralized, decentralized, and noncentralized initiations. It is shown that the communication and time complexities of the centralized algorithm are linear in e and d, respectively, while those for decentralized algorithm are O(e+n log n) and O(n), respectively (e is the number of edges, n is the number of processors, and d is the diameter of the graph). The complexities for noncentralized algorithms are, respectively O(e+n log k), where k is the level number, and O(n).>

A study is made of the network partition failure and the necessary and sufficient conditions are determined for the implementation of atomic transactions in the presence of partitions. Two aspects are explored: properties of the distributed system and the topology of the communication network. The essence of the results reported is that protocols to implement atomic actions in spite of partitions exist only under unrealistically strong conditions.>

Network partition is among the hardest failure types in a distributed system even if all processors and links are of fail-stop type. We address the transaction commitment problem in a partitioned distributed database. It is assumed that partitions are detectable. The approach taken is conservative - that is, the same transaction cannot be committed by one site and aborted by another.

The class of evidence-based diagnosis algorithms is developed to identify Byzantine (and any other faulty) processors. Such algorithms are said to be fair if they identify no failure-free processor as faulty. This paper makes two significant contributions: (i) it introduces a very general and simple formal model of the evidence-based diagnosis algorithms; and (ii) it derives a simple fair diagnosis algorithm, which is proved optimal for a large class of algorithms. It is further demonstrated that no fair evidence-based diagnosis algorithm can guarantee the identification of all faulty processors (completeness). Several insights into the behavior of the algorithm are presented.>

A straight-line-topology local area network (LAN) to which a number of nodes are connected either in series or in parallel is considered. A file F is arbitrarily partitioned among these sites. The problem studied is that of rearranging the records of the file such that the keys of records at lower-ranking sites are all smaller than those at higher-ranking sites. Lower bounds on the worst-case communication complexity are given for both the series and parallel arrangements, and algorithms optimal for all networks and files are presented.>

Many iterative algorithms for the solution of large linear systems may be effectively vectorized if the diagonal of the matrix is surrounded by a large band of zeroes, whose width is called the zero stretch. In this paper, a multicolor numbering technique is suggested for maximizing the zero stretch of irregularly sparse matrices. The technique, which is a generalization of a known multicoloring algorithm for regularly sparse matrices, executes in linear time, and produces a zero stretch approximately equal to n /2σ, where 2σ is the number of colors used in the algorithm. For triangular meshes, it is shown that σ ≤ 3, and that it is possible to obtain σ = 2 by applying a simple backtracking scheme.

A Distributed Database Management System should guarantee the consistency of databases at all sites in the system. In particular when the databases are replicated, mutual consistency among all copies of an item should be maintained. Concurrency control mechanisms achieve this when there are no failures, but they fail when failures occur. Network partitioning is a hard kind of failure to deal with and mutual consistency among copies of items cannot be taken for granted in presence of a partitioning. A simple scheme is presented in this paper to detect mutual inconsistency when partitioned databases merge. This scheme is similar to that of Parker et al [7] in spirit and is more general than theirs. In contrast to Davidson's [3] where some amount of information is maintained about each transaction run after the partition, we maintain some information with each data item accessed after the partition.

We consider the failure atomicity problem of distributed transactions in conjunction with the maximization of database availability. We propose a new information-based model for the distributed transaction-execution, which explicitly expresses the information at each stage during a protocol. In addition to rederiving certain existing results, we prove a fundamental relation among the site failures and the network partitioning. We propose a realistic model for site failures under which we show that the costs of commit and termination protocols can be greatly reduced. Finally, we explore the possible recovery strategies for a failed site and show how they are improved under our site failure model.

We address the problem of maintaining the distributed database consistency in presence of failures while maximizing the database availability. Network Partitioning is a failure which partitions the distributed system into a number of parts, no part being able to communicate with any other. Formalizations of various notions in this context are developed and two measures for the performances of protocols in presence of a network partitioning are introduced. A general optimality theory is developed for two classes of protocols—centralized and decentralized. Optimal protocols are produced in all cases.

In this sport paper, we report the

Commit protocols guarantee the consistency of distributed databases in absence of any failures. A commit protocol is resilient to a class of failures if it is possible to guarantee that a) databases at all operational sites in presence of these failures are consistent and b) other sites can be recovered consistently with these sites when the failure is repaired. Such a commit protocol is called nonblocking if no operational site needs to wait on a transaction which is incomplete at the time of the failure. It is known that no nonblocking commit protocol resilient to network partitioning exists. In this paper, the possible termination protocols of commit protocols are studied in the context of network partitioning. A formal model for termination protocols is introduced and a general logical interpretation of termination protocols is presented. The model makes use of all the information that is available in a component of the partition --- namely, the constituent sites and their respective states at the time of partition. Optimality measures for the termination protocols in terms of the number of waiting components and average number of waiting sites are introduced and protocols optimal under these measures are produced for all the possible centralized and decentralized commit protocols. It is proved that quorum-based termination protocols indeed perform very well in the presence of network partitioning. If the central site(s) is reliable, we can prove that centralized commit protocols indeed perform better than all decentralized ones. Thus, the general preference for centralized commit protocols is justified.