This paper presents two distributed algorithms for detecting and resolving deadlocks. By insuring that only one of the deadlock processes will detect it, the problem of resolving the deadlock is simplified. That proce...
ISBN:
(纸本)9780897911436
This paper presents two distributed algorithms for detecting and resolving deadlocks. By insuring that only one of the deadlock processes will detect it, the problem of resolving the deadlock is simplified. That process could simply abort itself. In one version of the algorithm, an arbitrary process detects deadlock; and in a second version, the process with the lowest priority detects deadlock.
An efficient distributed algorithm to detect deadlocks in distributed and dynamically changing systems is presented. In our model, processes can request any N available resources from a pool of size M. This is a gener...
ISBN:
(纸本)9780897911436
An efficient distributed algorithm to detect deadlocks in distributed and dynamically changing systems is presented. In our model, processes can request any N available resources from a pool of size M. This is a generalization of the well-known AND-OR request model. The algorithm is incrementally derived and proven correct. Its communication, computational, and space complexity compares favorably with those of previously known distributed AND-OR deadlock detection algorithms.
Message passing is one of the primary methods of information exchange between communicating processes. Many programming languages (e.g., CSP, ADA) provide interprocess communication through a rendezvous in which a sen...
ISBN:
(纸本)9780897911436
Message passing is one of the primary methods of information exchange between communicating processes. Many programming languages (e.g., CSP, ADA) provide interprocess communication through a rendezvous in which a sender (receiver) process waits until the receiver (sender) is ready to receive (send) a message; thus there is no buffering of messages. Many of these languages also allow non-deterministic constructs by which a process may wait to communication with any of a set of other processes. In this paper we consider the problem of ensuring different fairness properties in such a system of processes. In a natural model we prove a simple lower bound on the time complexity to ensure weak fairness and present near optimal algorithms in special cases. We also give new efficient algorithms to ensure strong *** this paper we introduce a formal model for processes and consider two different fairness properties: weak fairness and strong fairness. We investigate different distributed scheduling algorithms for ensuring the various fairness properties in a model where neighboring schedulers interact with each other using shared variables. We use the time complexity measure as defined in [Ly80].
The 26 papers in this volume deal with principles of distributedcomputing. Topics covered include distributed Networks;Concurrency Controls;distributed Databases;and Operating Systems.
ISBN:
(纸本)0897911105
The 26 papers in this volume deal with principles of distributedcomputing. Topics covered include distributed Networks;Concurrency Controls;distributed Databases;and Operating Systems.
One of the simplest services of a loosely-coupled distributed system is a time service. However, the implementation of this simplest service is much more complex. The problem of keeping a set of clocks synchronized an...
详细信息
ISBN:
(纸本)0897911105
One of the simplest services of a loosely-coupled distributed system is a time service. However, the implementation of this simplest service is much more complex. The problem of keeping a set of clocks synchronized and correct is considered in this paper.
Publishing is a model and mechanism for crash recovery in a distributedcomputing environment. Published communication works for systems connected via a broadcast medium by recording messages transmitted over the netw...
详细信息
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.
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.
暂无评论