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.
The proceedings contain 16 papers. The topics discussed include: implementing remote procedure calls;an asymmetric stream communication system;resource management in a decentralized system;a file system supporting coo...
ISBN:
(纸本)0897911156
The proceedings contain 16 papers. The topics discussed include: implementing remote procedure calls;an asymmetric stream communication system;resource management in a decentralized system;a file system supporting cooperation between programs;the LOCUS distributed operating system;a nested transaction mechanism for LOCUS;and a message system supporting fault tolerance.
LOCUS Is a distributed operating system which supports transparent access to data through a network wide fllesystem, permits automatic replication of storage, supports transparent distributed process execution, suppli...
详细信息
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.
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.
Grapevine is a distributed, replicated system that provides message delivery, naming, authentication, resource location, and access control services in an internet of computers. The system, described in a previous pap...
详细信息
The distributed V kernel is a message-oriented kernel that provides uniform local and network interprocess communication. It is primarily being used in an environment of diskless workstations connected by a high-speed...
详细信息
作者：
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.
R∗ is an experimental prototype distributed database management system. The computation needed to perform a sequence of multisite user transactions in R∗ is structured as a tree of processes communicating over virtual...
详细信息
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.
暂无评论