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.
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.
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.
暂无评论