We develop a characterization for m-fault-tolerant extensions, and for optimal m-fault-tolerant extensions, of a complete multipartite graph. Our formulation shows that this problem is equivalent to an interesting combinatorial problem on the partitioning of integers. This characterization leads to a new procedure for constructing an optimal m-fault-tolerant extension of any complete multipartite graph, for any m/spl ges/0. The proposed procedure is mainly useful when the size of the graph is relatively small, because the search time required is exponential. This exponential search, however, is not always necessary. We prove several necessary conditions that help us, in several cases, to identify some optimal m-fault-tolerant extensions without performing any search.>

Abstract Advances in computer technology have made the construction of complex networks with many processors economically feasible. Because of the complexity of such networks, reliability has become a major concern. In some applications, it is critical that the system must be able to operate correctly despite the presence of certain faults. To achieve this fault‐tolerance capability, some spare processors and interconnection links need to be added. In this case, when some of the basic components of the network fail, their tasks can be dynamically transferred to the spare components and the network can continue to operate. The three main criteria that it is desirable to minimize in a fault‐tolerant design are the number of nodes (processors), the number of edges (links), and the maximum number of connections to a node. Minimizing these attributes is important in practice, as it is unlikely that unbounded increase in the number of nodes, edges, or connections per node would be acceptable in a real design. In this paper, we shall consider this optimization problem when the (nonredundant) network under consideration is organized as a star. We study all possible variations of the problem under the assumption that minimizing nodes has the highest priority.

The authors studied the design of a fault-tolerant extension for a graph G which can survive at most m node failures, and which contains the minimum number of nodes and the fewest possible edges when the nonredundant graph (G) is a complete multipartite graph. After developing a characterization for m-fault-tolerant extensions and for optimal m-fault-tolerant extensions of a complete multipartite graph, this characterization is used to develop a procedure to construct an optimal m-fault-tolerant extension of any complete multipartite graph, for any m>or=0. The procedure is only useful when the size of the graph is relatively small, since the search time required is exponential. Several necessary conditions on any (optimal) m-fault-tolerant extension of a complete multipartite graph are proved. These conditions allow identification of some optimal m-fault-tolerant extensions of several special cases of a complete multipartite graph without performing any search.>

Abstract The advance in VLSI technology and the continuing decline in the cost of computer hardware have made the construction of complex networks with many processors economically feasible. Due to the complexity of such systems, reliability has become a major issue. In some applications, it is critical that the system must be able to operate correctly despite the presence of certain faults. Multiprocessor networks with such capability are called fault‐tolerant networks. These networks increase reliability by replicating some of the basic components, i.e., by including spare processors and interconnection links. The problem that arises naturally is that of minimizing the spare components that are needed to tolerate failure. In this paper, we consider this problem when the network under consideration is organized in the form of a star. The paper describes how to design optimal m ‐FT (m‐fault‐tolerant) graphs with respect to the star configuration, for all values of m ≥ 0.

When the only information available about transactions is syntactic information, serializability is the main correctness criterion for concurrency control. Serializability requires that the execution of each transaction must appear to every other transaction as a single atomic step (i.e., the execution of the transaction cannot be interrupted by other transactions). Many researchers, however, have realized that this requirement is unnecessarily strong for many applications and can significantly increase transaction response time. To overcome this problem, a new approach for controlling concurrency that exploits the semantic information available about transactions to allow controlled nonserializable interleavings has recently been proposed. This approach is useful when the cost of producing only serializable interleavings is unacceptably high. The main drawback of the approach is the extra overhead incurred by utilizing the semantic information. We examine this new approach in this paper and discuss its strengths and weaknesses. We introduce a new formalization for the concurrency control problem when semantic information is available about the transactions. This semantic information takes the form of transaction types, transaction steps, and transaction break-points. We define a new class of “safe” schedules called relatively consistent (RC) schedules. This class contains serializable as well as nonserializable schedules. We prove that the execution of an RC schedule cannot violate consistency and propose a new concurrency control mechanism that produces only RC schedules. Our mechanism assumes fewer restrictions on the interleavings among transactions than previously introduced semantic-based mechanisms.

The concurrency control problem in database systems has been examined by many people and several concurrency control algorithms have been proposed. The most popular algorithms are two-phase locking and timestamp ordering. This paper shows that two-phase locking and timestamp ordering are special cases of a more general concurrency control algorithm. This general algorithm is described in detail and is proven to work correctly. We show that two-phase locking and timestamp ordering represent the two end points of a series of concurrency control algorithms. Each of them is a special case of the general algorithm proposed in this paper. Moreover, each of these special cases can be selected in advance, and can even be changed dynamically during execution.