The design and use of scalable parallel computers is discussed. Much of the knowledge gained in the study of distributd systems is relevant, although it needs to be used in new manners. The author argues that the chal...
详细信息
ISBN:
(纸本)0897916131
The design and use of scalable parallel computers is discussed. Much of the knowledge gained in the study of distributd systems is relevant, although it needs to be used in new manners. The author argues that the challenge is to achieve maximum reuse of existing technologies, microprocessor architectures, I/O systems, programming languages, operating systems, application codes, without compromising too much parallel performance and scalability. Such skillful compromises are essential to the success of the parallel processing industry, and pose even more intellectual challenges than the 'start from scratch' approach.
This paper presents a systematic, modular technique for transforming a large class of unbounded shared-memory algorithms into bounded algorithms. We show that any unbounded algorithm based on a certain asynchronous ro...
详细信息
ISBN:
(纸本)0897916131
This paper presents a systematic, modular technique for transforming a large class of unbounded shared-memory algorithms into bounded algorithms. We show that any unbounded algorithm based on a certain asynchronous rounds structure can be `compiled' into a bounded algorithm in a way that preserves correctness and running time. As evidence that the asynchronous rounds structure is natural for wait-free algorithms, we identify a number of unbounded algorithms in the literature to which our transformation can either be applied directly, or applied after minor modifications. The running times of the resulting algorithms match these of their unbounded counterparts and hence in most cases the resulting algorithms are faster than any other known bounded solutions to the corresponding problems. In particular, we get a bounded consensus algorithm whose running time is O(n log2 n) and a bounded snapshot scan algorithm whose running time is O(n log n).
Much of modern systems programming involves designing algorithms for distributed systems in which the nodes have access to information about time. Time information can be used to estimate the time at which system or e...
详细信息
ISBN:
(纸本)0897916131
Much of modern systems programming involves designing algorithms for distributed systems in which the nodes have access to information about time. Time information can be used to estimate the time at which system or environment events occur, to detect process failures, to schedule the use of resources, and to synchronize activities of different system components. In this paper we propose a simple programming model that is based on the timed automaton model of Lynch and Vaandrager, which gives algorithms direct access to perfectly accurate time information. Unfortunately, this programming model is not realistic. In a realistic distributed system, clocks have skew and a finite granularity. Furthermore, other details neglected by the timed automaton model such as processor step times must also be considered. We provide two simulations that show how to transform an algorithm designed in the simple programming model to run in a more realistic distributed system. One of our simulations is an extension of previous results on the use of inaccurate clocks by Lamport, Neiger and Toueg, and Welch. Our extensions suggest several powerful design techniques for algorithms that are to be run in distributed systems with clocks whose divergence from real time is bounded. We demonstrate these techniques by providing a new algorithm for distributed linearizable read-write objects. This algorithm significantly improves over previous results in terms of time complexity and algorithmic simplicity.
The symposium materials contain 21 papers. The topics covered include file systems, distributed systems and networking, paradigms for structuring systems, inter-process communication, performance issues, mobile comput...
详细信息
ISBN:
(纸本)0897916328
The symposium materials contain 21 papers. The topics covered include file systems, distributed systems and networking, paradigms for structuring systems, inter-process communication, performance issues, mobile computing, memory management, and computer system security.
We present a solution to the problem of information integrity protection in distributed systems which is robust against malicious parties, is space and communication efficient, and uses cryptography in a minimal way. ...
详细信息
ISBN:
(纸本)0897916131
We present a solution to the problem of information integrity protection in distributed systems which is robust against malicious parties, is space and communication efficient, and uses cryptography in a minimal way. Our solution builds on Rabin's information dispersal algorithm (IDA). While the IDA scheme is able to deal with missing pieces of information, here we solve the more general secure information dispersal problem, in which recovery of information is possible even against modification of information shares by a possibly malicious adversary. Previous solutions to this problem suffer from space and communication blowup, or use costly cryptographic tools that limit the usefulness of the scheme. In contrast, our scheme uses cryptography in a `minimal' way. It gets rid of the need of private and public key systems and, actually, requires no secret keys at all. It permits recovery of the distributed information by any party in the system, and at the same time prevents any modification or loss of information, as long as a honest majority of parties exist. The proposed solution is space optimal and flexible enough to replace the basic IDA algorithm in most applications that contemplate general faults. Our solution introduces a new cryptographic tool called distributed fingerprints, which consists of public fingerprints for data integrity having the `paradoxical' property that everyone in the system can compute them (using the same function and no secrets!) but no one can forge them. distributed fingerprints may replace some of the (integrity) functions provided by signatures in distributed systems, but at a lower cost.
This paper investigates a new shared-memory model called immediate atomic snapshot memory. It is an extension of atomic snapshot memory in which a write operation in addition to writing, also returns an atomic snapsho...
详细信息
ISBN:
(纸本)0897916131
This paper investigates a new shared-memory model called immediate atomic snapshot memory. It is an extension of atomic snapshot memory in which a write operation in addition to writing, also returns an atomic snapshot of the memory. Unlike regular atomic snapshot, immediate snapshot is guaranteed to closely follow the write operation. This model was previously used to obtain an impossibility result. Here we investigate its utility for the design of algorithms. We first implement the one-shot version in the read-write model. We then use the model to design a new renaming algorithm. The renaming algorithm we obtain is simple and requires at worst n cycles of one-shot immediate snapshots. Since our implementation of the one-shot immediate snapshot requires O(n2) primitive read-write operations, we obtain an O(n3) renaming algorithm. Currently the best renaming algorithm is exponential. Our implementation of the immediate snapshot relies on a priori knowledge of the bound on the number of snapshots to be taken. We were not able to dispense with this condition and thus were unable to obtain an implementation of the long-lived object.
The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. A novel modular presentation of the problem is described whi...
详细信息
ISBN:
(纸本)0897916131
The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. A novel modular presentation of the problem is described which allows to deal with different assumptions for the delay of messages. We present a definition of clock synchronization under arbitrary delay assumptions, and present an optimal clock synchronization algorithm for general systems. We then show that in local systems (where delays on each link are independent of the other links) the inputs for the clock synchronization algorithm can be computed from the maximum local shifts for each pair of processors sharing a link. The maximum local shift for two processors depends only on their views. This allows our theory to deal with systems where different links adhere to different assumptions, or the same link satisfies several sets of assumptions;such mixtures are quite likely in practice. In particular, we show how to compute the maximum local shifts from the views, and hence provide optimal algorithms for systems where some links may have upper and/or lower bounds on the delay, some may have a bound on the difference between the delay in both directions, some may have both kinds of bounds and some may have no bounds. Previous results dealt only with the case where upper and lower bounds were known for all links. We introduce a new notion of optimality, that requires an algorithm to achieve the best possible precision on each instance;this notion is stronger than the previously used notion of worst case optimality. In contrast to the worst case approach, the new notion handles models where the worst-case behavior of any clock synchronization algorithm is inherently unbounded.
We describe computation migration, a new technique that is based on compile-time program transformations, for accessing remote data in a distributed-memory parallel system. In contrast with RPC-style access, where the...
详细信息
ISBN:
(纸本)0897915895
We describe computation migration, a new technique that is based on compile-time program transformations, for accessing remote data in a distributed-memory parallel system. In contrast with RPC-style access, where the access is performed remotely, and with data migration, where the data is moved so that it is local, computation migration moves part of the current thread to the processor where the data resides. The access is performed at the remote processor, and the migrated thread portion continues to run on that same processor;this makes subsequent accesses in the thread portion local. We describe an implementation of computation migra^ tion that consists of two parts: an implementation that migrates single activation frames, and a high-level language annotation that allows a programmer to express when migration is desired. We performed experiments using two applications;these experiments demonstrate that computation migration is a valuable alternative to RPC and data migration.
The symposium materials contain 25 papers. The topics covered include distributed priority algorithms, connection-based communication in dynamic networks, adaptive packet routing, computing with faulty shared memory, ...
详细信息
ISBN:
(纸本)0897914953
The symposium materials contain 25 papers. The topics covered include distributed priority algorithms, connection-based communication in dynamic networks, adaptive packet routing, computing with faulty shared memory, fault-tolerant coordination, self-stabilization, shared-memory multiprocessors, fast mutual exclusion, fast network decomposition, the weakest failure detector for solving consensus, leader election in complete networks, randomized coordinated attack protocols, distributed edge coloring, and proving probabilistic correctness statements.
暂无评论