Efficient allocation of communication channels is critical for the performance of wireless mobile computing systems. The centralized channel allocation algorithms proposed in literature are neither robust, nor scalabl...
详细信息
ISBN:
(纸本)9780897917100
Efficient allocation of communication channels is critical for the performance of wireless mobile computing systems. The centralized channel allocation algorithms proposed in literature are neither robust, nor scalable. distributed channel allocation schemes proposed in the past are complicated and require active participation of the mobile nodes. These algorithms are unable to dynamically adjust to spatial and temporal fluctuations in channel demand. We present a dynamic distributed channel allocation algorithm that can quickly adapt to changes in load distribution. The algorithm described in this paper requires minimal involvement of the mobile nodes, thus conserving their limited energy supply. The algorithm is proved to be deadlock free, starvation free and fair. It prevents co-channel interference and is scalable.
Recovery by checkpointing on distributed shared memory systems is investigated in this paper. The notion of consistent global states on a sequentially consistent shared memory system is defined. We investigate how con...
详细信息
ISBN:
(纸本)9780897917100
Recovery by checkpointing on distributed shared memory systems is investigated in this paper. The notion of consistent global states on a sequentially consistent shared memory system is defined. We investigate how consistent checkpoints can be obtained in these systems. In addition, a novel lazy checkpointing approach is proposed. It allows a controlled degree of concurrency and, at the same time, limits the amount of rollback propagation during recovery. Correctness requirements for efficient checkpointing are explored first and algorithms satisfying the requirements are developed subsequently. Several interesting properties of checkpointing on distributed shared memory systems are discovered. In particular, we show that for low levels of laziness, one can achieve better concurrency with more stable storage.
distributed reference counting provides timely and fault-tolerant garbage collection in large distributed systems, but it fails to collect cyclic garbage distributed across nodes. A common proposal is to migrate all o...
详细信息
ISBN:
(纸本)9780897917100
distributed reference counting provides timely and fault-tolerant garbage collection in large distributed systems, but it fails to collect cyclic garbage distributed across nodes. A common proposal is to migrate all objects on a garbage cycle to a single node, where they can be collected by the local collector. However, existing schemes have practical problems due to unnecessary migration of objects. We present solutions to these problems: our scheme avoids migration of live objects, batches objects to avoid a cascade of migration messages, and short-cuts the migration path to avoid multiple migrations. We use simple estimates to detect objects that are highly likely to be cyclic garbage and to select a node to which such objects are migrated. The scheme has low overhead, and it preserves the decentralized and fault-tolerant nature of distributed reference counting and migration.
A certificate for the k connectivity of a graph G = (V, E) is a subset E′ of E such that (V, E′) is k connected iff G is k connected. Let n = |V| and m = |E|. A certificate is called sparse if it has size O(kn). We ...
详细信息
ISBN:
(纸本)9780897917100
A certificate for the k connectivity of a graph G = (V, E) is a subset E′ of E such that (V, E′) is k connected iff G is k connected. Let n = |V| and m = |E|. A certificate is called sparse if it has size O(kn). We present a distributed algorithm for computing sparse certificate for k connectivity whose time complexity is O(k(D + n0.614)) where D is the diameter of the network. A new algorithm for identifying biconnected components is also presented. This algorithm is significantly simpler than many existing algorithms and can be implemented in distributed environment to run in O(D + n0.614) time. Both algorithms improve on the previous best known time bounds. Our main focus in this paper is the time complexity. However, no more than a polynomial number of messages, each of size O(log n), are generated by the algorithm.
In [11] a method for the analysis of the expected time complexity of a randomized distributed algorithm is presented. The method consists of proving auxiliary probabilistic time bound statements of the form U t/→p U...
详细信息
ISBN:
(纸本)9780897917100
In [11] a method for the analysis of the expected time complexity of a randomized distributed algorithm is presented. The method consists of proving auxiliary probabilistic time bound statements of the form U t/→p U′, which mean that whenever the algorithm begins in a state in set U, it will reach a state in set U′ within time t with probability at least p. However, [11] does not provide a formal methodology to prove the validity of a specific probabilistic time bound statement from scratch: each statement is proved by means of ad hoc operational arguments. Unfortunately, operational reasoning is generally error-prone and difficult to check. In this paper we overcome the problem by developing a new technique to prove probabilistic time bound statements, which consists of reducing the analysis of a time bound statement to the analysis of a statement that does not involve probability. As a consequence, several existing techniques for a non-randomized algorithms can be applied, and correctness proofs can be verified mechanically.
A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication and ...
详细信息
A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication and dissemination of information. In this paper we introduce a general class of quorum systems called Crumbling Walls and study its properties. The elements (processors) of a wall are logically arranged in rows of varying widths. A quorum in a wall is the union of one full row and a representative from every row below the full row. This class considerably generalizes a number of known quorum system constructions. The best crumbling wall is the CWlog quorum system. It has small quorums, of size O(lg n), and structural simplicity. The CWlog has optimal availability and optimal load among systems with such small quorum size. It manifests its high quality for all universe sizes, so it is a good choice not only for systems with thousands or millions of processors but also for systems with as few as 3 or 5 processors. Moreover, our analysis shows that the availability will increase and the load will decrease at the optimal rates as the system increases in size.
This paper presents a fast distributed algorithm to compute a small k-dominating set D (for any fixed k) and its induced graph partition (breaking the graph into radius k clusters centered around the vertices of D). T...
详细信息
ISBN:
(纸本)9780897917100
This paper presents a fast distributed algorithm to compute a small k-dominating set D (for any fixed k) and its induced graph partition (breaking the graph into radius k clusters centered around the vertices of D). The time complexity of the algorithm is O(k log* n). Small k-dominating sets have applications in a number of areas, including routing with sparse routing tables via the scheme of [PU], the design of distributed data structures [P2], and center selection in a distributed network (cf. [BKP]). The main application described in this paper concerns a fast distributed algorithm for constructing a minimum weight spanning tree (MST). On an n-vertex network of diameter d, the new algorithm constructs an MST in time O(√n log* n + d), improving on the results of [GKP]. The new MST algorithm is conceptually simpler than the three-phase algorithm of [GKP]. In addition to exploiting small k-dominating sets, it uses a very simple convergecast protocol to inform a center about graph edges, that avoids forwarding messages about edges that close cycles. This convergecast protocol is similar to the one used in the third phase of the algorithm of [GKP], and most of the novelty lies in a new careful analysis proving that the convergecast process is fully pipelined, and no waiting occurs at intermediate nodes. This enables the new algorithm to skip the complicated second phase of the algorithm of [GKP].
Protocols to implement a fault-tolerant computing system are described. These protocols augment the hypervisor of a virtual-machine manager and coordinate a primary virtual machine with its backup. The result is a fau...
详细信息
The proceedings contain 30 papers. The topics discussed include: hypervisor-based fault tolerance;hive: fault containment for shared-memory multiprocessors;U-Net: a user-level network interface for parallel and distri...
ISBN:
(纸本)0897917154
The proceedings contain 30 papers. The topics discussed include: hypervisor-based fault tolerance;hive: fault containment for shared-memory multiprocessors;U-Net: a user-level network interface for parallel and distributedcomputing;object and native code thread mobility among heterogeneous computers (includes sources);the HP AutoRAID hierarchical storage system;performance of cache coherence in stackable filing;exploiting weak connectivity for mobile file access;rover: a toolkit for mobile information access;managing update conflicts in bayou, a weakly connected replicated storage system;a new page table for 64-bit address spaces;CRL: high-performance all-software distributed shared memory;the performance of the container shipping I/O system;time-function scheduling: a general approach to controllable resource;a real-time upcall facility for protocol processing with QoS guarantees;and using a modified object buffer to improve the write performance of an object-oriented database.
Data-parallel languages, such as High Performance Fortran, are widely regarded as a promising means for writing portable programs for distributed-memory machines. Novel features of these languages call for the develop...
详细信息
Data-parallel languages, such as High Performance Fortran, are widely regarded as a promising means for writing portable programs for distributed-memory machines. Novel features of these languages call for the development of new techniques in both compilers and run-time systems. In this paper, we present an improved algorithm for finding the local memory access sequence in computations involving regular sections of arrays with cyclic(k) distributions. After establishing the fact that regular section indices correspond to elements of an integer lattice, we show how to find a lattice basis that allows for simple and fast enumeration of memory accesses. The complexity of our algorithm is shown to be lower than that of the previous solution for the same problem. In addition, the experimental results demonstrate the efficiency of our method in practice.
暂无评论