A problem of considerable importance in designing computations by process networks, is detection of termination. We propose a very simple algorithm for termination detection in an arbitrary network using a single mark...
详细信息
ISBN:
(纸本)0897911105
A problem of considerable importance in designing computations by process networks, is detection of termination. We propose a very simple algorithm for termination detection in an arbitrary network using a single marker. We show an application of this scheme in solving the problem of token loss detection and token regeneration in a token ring.
Algorithms are presented for selecting an element of given rank from a set of elements distributed among the nodes of a network. Network topologies considered are a ring, a mesh, and a complete binary tree. For the ri...
详细信息
ISBN:
(纸本)0897911105
Algorithms are presented for selecting an element of given rank from a set of elements distributed among the nodes of a network. Network topologies considered are a ring, a mesh, and a complete binary tree. For the ring and the mesh, upper bound tradeoffs are identified between the number of messages transmitted and the total delay due to message transmission. For the tree, an algorithm is presented that uses an asymptotically optimal number of messages.
We examine the problem of determining whether a given set of locked transactions, accessing a distributed database, is free from deadlock. A deadlock graph is used to derive a new characterization for deadlock-free tw...
详细信息
ISBN:
(纸本)0897911105
We examine the problem of determining whether a given set of locked transactions, accessing a distributed database, is free from deadlock. A deadlock graph is used to derive a new characterization for deadlock-free two-transaction systems in a distributed environment. The characterization provides a direct and efficient polynomial test for deadlock-freedom in two-transaction systems. The method is not dependent on the number of sites in a distributed database, and hence improves previously known results, which are exponential in the number of sites.
Two design rules which aid the construction of distributedcomputing systems and the provision of fault tolerance are described, namely that: (i) a distributedcomputing system should be functionally equivalent to the...
详细信息
ISBN:
(纸本)0818605014
Two design rules which aid the construction of distributedcomputing systems and the provision of fault tolerance are described, namely that: (i) a distributedcomputing system should be functionally equivalent to the individual computing systems of which it is composed, and (ii) fault tolerant systems should be constructed from generalized fault tolerant components. The reasoning behind these two 'recursive structuring principles', and the consequences of attempting to adhere to them, are discussed. Where appropriate this discussion is illustrated by reference to a distributed system based on UNIX that is now operational at Newcastle and several other locations. This system has been implemented by adding a software subsystem, known as the Newcastle Connection, to each of a set of UNIX systems. By this means the authors has constructed a distributed system which is functionally equivalent at both the user and the program level to a conventional uniprocessor UNIX system.
We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time, which we formalize as a problem of scheduling the edges of a weighted multigraph. Although the general problem ...
详细信息
ISBN:
(纸本)0897911105
We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time, which we formalize as a problem of scheduling the edges of a weighted multigraph. Although the general problem is NP-complete, we identify polynomial time solvable special cases and derive good performance bounds for several natural approximation algorithms. The above results assume the existence of a central controller, but we also show how the approximation algorithms, along with their performance guarantees, can be adapted to a distributed regime.
作者：
Mohan, C.Lindsay, B.IBM
San Jose Research Lab San Jose CA USA IBM San Jose Research Lab San Jose CA USA
This paper describes two efficient distributed transaction commit protocols, the Presumed Abort (PA) and Presumed Commit (PC) protocols, which have been implemented in the distributed data base system R. PA and PC are...
详细信息
ISBN:
(纸本)0897911105
This paper describes two efficient distributed transaction commit protocols, the Presumed Abort (PA) and Presumed Commit (PC) protocols, which have been implemented in the distributed data base system R. PA and PC are extensions of the well-known two-phase (2P) commit protocol. PA is optimized for read-only transactions and a class of multi-site update transactions, and PC is optimized for other classes of multi-site update transactions. The optimizations result in reduced inter-site message traffic and log writes, and, consequently, a better response time for such transactions. We derive the new protocols in a step-wise fashion by modifying the 2P protocol.
This paper describes an application of Byzantine Agreement to distributed transaction commit. We replace the second phase of one of the commit algorithms with Byzantine Agreement, providing certain trade-offs and adva...
详细信息
ISBN:
(纸本)0897911105
This paper describes an application of Byzantine Agreement to distributed transaction commit. We replace the second phase of one of the commit algorithms with Byzantine Agreement, providing certain trade-offs and advantages at the time of commit and providing speed advantages at the time of recovery from failure. The present work differs from that presented in left bracket DoSt82b right bracket by increasing the scope (handling a general tree of processes, and multi-cluster transactions) and by providing an explicit set of recovery algorithms. We also provide a model for classifying failures that allows comparisons to be made among various proposed distributed commit algorithms. The context for our work is the Highly Available Systems project at the IBM San Jose Research Laboratory.
The proceedings contain 30 papers. The topics discussed include: dynamic systems and their distributed termination;UIDs as internal names in a distributed file system;testing incomplete specifications of distributed s...
ISBN:
(纸本)0897910818
The proceedings contain 30 papers. The topics discussed include: dynamic systems and their distributed termination;UIDs as internal names in a distributed file system;testing incomplete specifications of distributed systems;distributed communication via global buffer;language constructs and support systems for distributedcomputing;efficient schemes for parallel communication;distributed multi-destination routing: the constraints of local information;randomized parallel communication;language concepts for distributed processing of large arrays;four combinators for concurrency;bounds on information exchange for byzantine agreement;a refinement of Kahn's semantics to handle nondeterminism and communication refinement of Kaiin's semantics to handle non-determinism and communication;understanding and using asynchronous message passing;on the distribution of an assertion;real time resource allocation in distributed systems;finding safe paths in a faulty environment;on-the-fly deadlock prevention;edge locks and deadlock avoidance in distributed systems;and a distributed algorithm for detecting resource deadlocks in distributed systems.
Complex systems (such as distributed ones) should be specified before they are implemented. Even more advantages accrue if the specifications are executable, so that behaviors of the specified systems can be tested. T...
详细信息
This paper describes a new model for dynamic distributed systems, where new processes are added and terminated at execution time. It is an extension of the static model underlying CSP. The model uses CSP I/O commands ...
详细信息
暂无评论