A model of distributed graph reduction is described that has features common to many distributedcomputing systems: a program (represented as a graph) is partitioned and dynamically distributed among an arbitrary numb...
详细信息
ISBN:
(纸本)0897911105
A model of distributed graph reduction is described that has features common to many distributedcomputing systems: a program (represented as a graph) is partitioned and dynamically distributed among an arbitrary number of processing elements having only local store, and computation takes place as tasks are propagated between vertices in the graph. Specific problems are addressed that are inherent in a computing model of this sort, including garbage collection, detecting deadlock, deleting tasks, and the dynamic prioritization of tasks. By characterizing these problems in terms of graph connectivity, a decentralized graph-marking algorithm is shown to provide an effective solution. This algorithm is unique in that it allows marking a distributed graph whose connectivity is continually changing.
A methodology for transforming sequential recursive algorithms to distributive ones is suggested. The assumption is that the program segments between recursive calls have a distributive implementation. The methodology...
详细信息
ISBN:
(纸本)0897911105
A methodology for transforming sequential recursive algorithms to distributive ones is suggested. The assumption is that the program segments between recursive calls have a distributive implementation. The methodology is applied to two k-selection algorithms and yields new distributed k-selection algorithms. Some complexity issues of the resulting algorithms are discussed.
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.
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.
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.
作者：
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.
A large array is an array whose storage is distributed among primary and secondary storage and whose processing may be distributed among several tasks in a distributed system. This paper presents a semantic model (set...
详细信息
暂无评论