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.
The proceedings contain 44 papers. The topics discussed include: a topological characterization of weakness;efficient dependency tracking for relevant events in shared-memory systems;building scalable and robust peer-...
详细信息
The proceedings contain 44 papers. The topics discussed include: a topological characterization of weakness;efficient dependency tracking for relevant events in shared-memory systems;building scalable and robust peer-to-peer overlay networks for broadcasting using network coding;skip webs: efficient distributed data structures for multi-dimensional data sets;brief announcement: an incentive-compatible capacity assignment algorithm for bulk data distribution using P2P;brief announcement: broadcast in radio networks in the presence of Byzantine adversaries;feedback control for router congestion resolution;toward a theory of transactional contention managers;and adaptive routing with stale information.
In the directed single-source reachability problem, input is a directed graph G = (V,E) and a source s is an element of V, and the objective is to identify nodes t for which there is a directed path in G from s to t. ...
详细信息
ISBN:
(纸本)9781450336178
In the directed single-source reachability problem, input is a directed graph G = (V,E) and a source s is an element of V, and the objective is to identify nodes t for which there is a directed path in G from s to t. Recently Nanongkai [2] presented a distributed algorithm that solves this problem in (O) over tilde (D + root nD(1/2)) rounds, where D and n respectively denote the network diameter and the number of nodes. This note presents an algorithm that improves the round complexity to (O) over tilde (D + root nD(1/4)), thus getting closer to the (Omega) over tilde (D + root n) lower bound of Das Sarma et al. [1].
We consider the lifetime maximization for multicast in wireless sensor networks (WSNs) and propose a new distributed algorithm that achieves a good balance on algorithm optimality and message complexity.
ISBN:
(纸本)9781595939890
We consider the lifetime maximization for multicast in wireless sensor networks (WSNs) and propose a new distributed algorithm that achieves a good balance on algorithm optimality and message complexity.
We present two distributed node coloring algorithms operating in the Signal-to-interference-and-noise-ratio (SINR) model. The first algorithm is very simple and achieves a (4 Delta)-coloring in O(Delta log n) time slo...
详细信息
ISBN:
(纸本)9781450336178
We present two distributed node coloring algorithms operating in the Signal-to-interference-and-noise-ratio (SINR) model. The first algorithm is very simple and achieves a (4 Delta)-coloring in O(Delta log n) time slots. The results of our experimental evaluation show that the algorithm is extremely fast. Combined with a new color reduction scheme, the algorithm computes a (Delta+1)-coloring in O(Delta log n) time. This improves on current distributed coloring algorithms for the SINR model either in terms of the number of colors or runtime, and matches the asymptotical runtime of one round of local broadcasting, which can be seen as a lower bound.
The proceedings contain 58 papers. The topics discussed include: near-optimal scheduling of distributed algorithms;new routing techniques and their applications;brief announcement: routing the internet with very few e...
ISBN:
(纸本)9781450336178
The proceedings contain 58 papers. The topics discussed include: near-optimal scheduling of distributed algorithms;new routing techniques and their applications;brief announcement: routing the internet with very few entries;terminating distributed construction of shapes and patterns in a fair solution of automata;fast and exact majority in population protocols;distributed house-hunting in ant colonies;brief announcement: on the feasibility of leader election and shape formation with self-organizing programmable matter;near-optimal distributed maximum flow;toward optimal bounds in the congested clique: graph connectivity and MST;fast distributed almost stable matchings;a (truly) local broadcast layer for unreliable radio networks;efficient communication in cognitive radio networks;and brief announcement: a hierarchy of congested clique models, from broadcast to unicast.
distributed storage systems often trade off strong semantics for improved scalability. This paper describes the design, implementation, and evaluation of Scatter, a scalable and consistent distributed key-value storag...
详细信息
ISBN:
(纸本)9781450309776
distributed storage systems often trade off strong semantics for improved scalability. This paper describes the design, implementation, and evaluation of Scatter, a scalable and consistent distributed key-value storage system. Scatter adopts the highly decentralized and self-organizing structure of scalable peer-to-peer systems, while preserving linearizable consistency even under adverse circumstances. Our prototype implementation demonstrates that even with very short node lifetimes, it is possible to build a scalable and consistent system with practical performance.
The atomic snapshot object is an important primitive used for the design and verification of wait-free algorithms in shared memory distributed systems. A snapshot object is a shared data structure partitioned into seg...
详细信息
ISBN:
(纸本)0897916131
The atomic snapshot object is an important primitive used for the design and verification of wait-free algorithms in shared memory distributed systems. A snapshot object is a shared data structure partitioned into segments. Processors can either update an individual segment, or instantaneously scan all segments of the object. This paper presents an efficient implementation of an atomic snapshot object, in which each high level operation (scan or update) requires O(n log n) low level operations on atomic read/write registers.
General barrier synchronization is widely used in multiprocessor programming with the introduction of multicore processors. In this paper, we describe a solution for the barrier synchronization of processes (that are ...
详细信息
ISBN:
(纸本)9781605583969
General barrier synchronization is widely used in multiprocessor programming with the introduction of multicore processors. In this paper, we describe a solution for the barrier synchronization of processes (that are not bounded or known a priori) that can dynamically join or drop out of barrier synchronization. A new process can join only in the beginning of each phase along with all the other members;that is, at the beginning of a phase everyone is aware of the other members involved in synchronization. We design a protocol using the above policy that guarantees starvation freedom, i.e., any process wanting to join phase synchronization shall do so within at most two phases.
A task is a distributed coordination problem in which each process starts with a private input value taken from a finite set, communicates with the other processes by applying operations to shared objects, and eventua...
详细信息
ISBN:
(纸本)9780897918008
A task is a distributed coordination problem in which each process starts with a private input value taken from a finite set, communicates with the other processes by applying operations to shared objects, and eventually halts with a private output value, also taken from a finite set. It is said that tasks are decidable in a given model if there exists an effective procedure for deciding whether any task has a protocol in that model. This paper uses techniques adapted from classical algebraic topology to prove undecidability results for a variety of models, and explicit constructions to prove decidability in the complimentary cases. These results are summarized and presented.
暂无评论