Processes in concurrent logic programs communicate and synchronize using shared single-assignment variables. Communication is performed via unification operations, while synchronization is performed through input matc...
详细信息
ISBN:
(纸本)9780897914048
Processes in concurrent logic programs communicate and synchronize using shared single-assignment variables. Communication is performed via unification operations, while synchronization is performed through input matching. The more expressive concurrent logic languages employ atomic unification as the basic communication primitive. Atomic unification can be thought of as an atomic transaction that either fails with no trace or succeeds in writing on all of the necessary writable variables occurring in the unification instance. This paper presents a distributed variable server algorithm that can be used as the key component in a distributed implementation of concurrent logic languages with atomic unification. The variable server provides an abstraction in which processes can act as if all of the shared variables are local. It thus allows programs to be written for a shared memory model and executed in a system in which memory is distributed. We rigorously specify the requirements the variable server must fulfill, present an algorithm satisfying the specification, and prove its correctness with respect to the specification. The algorithm has been implemented for the language Flat Concurrent Prolog (FCP) and is incorporated in the distributed version of the Logix system.
The main contribution of this paper is the Cancelback Protocol, an extension of the Time Warp mechanism that handles storage management. It includes both fossil collection, the recovery of storage for messages and sta...
详细信息
The main contribution of this paper is the Cancelback Protocol, an extension of the Time Warp mechanism that handles storage management. It includes both fossil collection, the recovery of storage for messages and states that can never again influence the computation, and cancelback, the recovery of storage assigned to messages and states at times so far in the future that their memory would be better used for more immediate purposes. It guarantees that Time Warp is optimal in its storage requirements when run in shared memory, i.e. Time Warp will successfully complete a simulation using no more space than it would take to execute the same simulation with the sequential event list algorithm. This is better by a factor of two than the only previously published result. Without this protocol (or equivalent) Time Warp's behavior can be unstable;hence it should be considered an essential part of Time Warp mechanism, rather than simply a refinement. In addition we also prove that asynchronous conservative algorithms, including all of the Chandy-Misra-Bryant (CMB) mechanisms, are not optimal;they cannot necessarily execute a simulation in the same amount of space as a sequential execution. In some cases a simulation requiring space n+k when executed sequentially might require O(nk) space when executed on n processors by CMB.
To provide high availability for services such as mail or bulletin boards, data must be replicated. One way to guarantee consistency of replicated data is to force service operations to occur in the same order at all ...
详细信息
ISBN:
(纸本)089791404X
To provide high availability for services such as mail or bulletin boards, data must be replicated. One way to guarantee consistency of replicated data is to force service operations to occur in the same order at all sites, but this approach is expensive. In this paper, we propose lazy replication as a way to preserve consistency by exploiting the semantics of the service's operations to relax the constraints on ordering. Three kinds of operations are supported: operations for which the clients define the required order dynamically during the execution, operations for which the service defines the order, and operations that must be globally ordered with respect to both client ordered and service ordered operations. The method performs well in terms of response time, amount of stored state, number of messages, and availability. It is especially well suited to applications in which most operations require only the client-defined order.
Programming nonshared memory systems is more difficult than programming shared memory systems, since there is no support for shared data structures. Current programming languages for distributed memory architectures f...
详细信息
A high-speed network is a new environment motivated by recent advances in transmission technology. The high-speed environment requires that the network node operate (fast) based solely on local information (at least m...
详细信息
ISBN:
(纸本)089791404X
A high-speed network is a new environment motivated by recent advances in transmission technology. The high-speed environment requires that the network node operate (fast) based solely on local information (at least most of the time). This fact implies properties that are much different than those existing in current architectures and algorithms for traditional large-area networks. The new environment poses new challenges for the network architect and the algorithm designer. In this paper we present principles of operation for the basic control functions of a high-speed network with an arbitrary topology, we then suggest a design of such a network. In the architecture we design, on one hand a node can try to transmit asynchronously, without reservation, as much as it can, and on the other hand the network access and flow control will ensure no loss, fair access to the network, no deadlocks and self-routing. The switching over this network requires only a single buffer on each side of the full-duplex links. The transmission via the receiving buffer can be 'cut through', i.e., the incoming packet can be sent to the next link before the entire packet has arrived (unlike 'store-and-forward'). A dynamic self-routing technique is implemented, in which the packet header contains only the destination identification when it leaves the source. This information is sufficient for reaching the destination, not necessarily on the same route each time, and to overcome congrestion and failures. All these properties are implemented in a distributed manner. The system is asynchronous and designed for transmission of variable size packets.
We present a new checkpointing scheme for a distributed database system. Our scheme records the states of some selected data items and can be executed at any time without stopping other activities in the database syst...
ISBN:
(纸本)0897913523
We present a new checkpointing scheme for a distributed database system. Our scheme records the states of some selected data items and can be executed at any time without stopping other activities in the database system. It makes use of “shadows” of data items to make sure that the collected data item values are “transaction-consistent”. Storage overhead is low, since at most one shadow is needed for each data item.
This conference proceedings contains 25 papers. The topics covered are: impossibility proofs;nondeterministic processes;communicating finite-state machines;bounded protocols for FIFO channels;sequence transmission pro...
详细信息
ISBN:
(纸本)0897913264
This conference proceedings contains 25 papers. The topics covered are: impossibility proofs;nondeterministic processes;communicating finite-state machines;bounded protocols for FIFO channels;sequence transmission problems;communication in the presence of faults;knowledge, probability, and adversaries;reliable message diffusion;expressivity and knowledge;ambiguity of choosing;concensus;mutual exclusion;fault-tolerant computing;parallel algorithms;distributed recovery;induction theorem;parallel programs;concurrency;Byzantine agreement;shared memory versus message passing;calling names;multishop radio networks;fault isolation;randomized concensus.
An overview is given of impossibility results in the area of distributedcomputing. The techniques used are described, and a historical perspective is given. Suggestions for future work are made.
ISBN:
(纸本)0897913264
An overview is given of impossibility results in the area of distributedcomputing. The techniques used are described, and a historical perspective is given. Suggestions for future work are made.
We present an efficient fault-tolerant solution to the distributed mutual exclusion problem. Our protocol requires log n messages in the best case and is resilient to both site and communication failures, even when su...
详细信息
ISBN:
(纸本)0897913264
We present an efficient fault-tolerant solution to the distributed mutual exclusion problem. Our protocol requires log n messages in the best case and is resilient to both site and communication failures, even when such failures lead to network partitioning. Furthermore, the protocol exhibits a property of graceful degradation, i.e., it requires more message only as the number of failures increase in the network.
It is asserted that to obtain a meaningful comparison of protocols, the adversary should be chosen not to send identical faulty messages but to 'convey' the same misinformation. In order to make sense of these...
详细信息
ISBN:
(纸本)0897913264
It is asserted that to obtain a meaningful comparison of protocols, the adversary should be chosen not to send identical faulty messages but to 'convey' the same misinformation. In order to make sense of these notions, two new ideas are introduced. First, since the information of processors is completely encoded in their states, the behavior of the faulty processors is specified according to the states which they use for transmitting, rather than the messages they actually transmit. To account for the empty and ungrammatical messages, special states which yield these messages when the message generators are applied to them are introduced.
暂无评论