The coverage problem is of great interest for many sensor network applications, for example, detection of intruders in the sensor field. Topological changes in sensor networks may affect qualities of sensor coverage. ...
详细信息
ISBN:
(纸本)9781595936165
The coverage problem is of great interest for many sensor network applications, for example, detection of intruders in the sensor field. Topological changes in sensor networks may affect qualities of sensor coverage. We present three suites of algorithms for dynamically maintaining the coverage and the measures of its qualities. Using only local knowledge, our algorithms capture the dynamic changes of network topology and efficiently maintain the coverage by updating the radii of sensors combined with limited sensor mobility. Our algorithms have the advantages of low communication complexity with no need of a tight bound on message propagation delay.
We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximation distributed algorithm for weighted maximum matching;whose running time...
详细信息
ISBN:
(纸本)9781595936165
We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximation distributed algorithm for weighted maximum matching;whose running time is O(log n) for any constant epsilon > 0, where n is the number of nodes in the graph. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give an algorithm that maintains a (1 + epsilon)-approximation in O(1/epsilon) time for each node insertion or deletion. For weighted dynamic graphs we give a constant-factor approximation algorithm that runs in constant time for each insertion or deletion.
The efficient distributed construction of a maximal independent set (MIS) of a graph is of fundamental importance. We study the problem in the class of Growth-Bounded Graphs, which includes for example the well-known ...
详细信息
ISBN:
(纸本)9781595936165
The efficient distributed construction of a maximal independent set (MIS) of a graph is of fundamental importance. We study the problem in the class of Growth-Bounded Graphs, which includes for example the well-known Unit Disk Graphs. In contrast to the fastest (time-optimal) existing approach [11], we assume that no geometric information (e.g., distances in the graph's embedding) is given. Instead, nodes employ randomization for their decisions. Our algorithm computes a MIS in O(log log n . log* n) rounds with very high probability for graphs with bounded growth, where n denotes the number of nodes in the graph. In view of Linial's Omega(log* n) lower bound for computing a MIS in ring networks [2] which was extended to randomized algorithms independently by Naor [18] and Linial [13], our solution is close to optimal. In a nutshell, our algorithm shows that for computing a MIS, randomization is a viable alternative to distance information.
Erasure coding can reduce the space and bandwidth overheads of redundancy in fault-tolerant data storage and delivery systems. But it introduces the fundamental difficulty of ensuring that all erasure-coded fragments ...
详细信息
ISBN:
(纸本)9781595936165
Erasure coding can reduce the space and bandwidth overheads of redundancy in fault-tolerant data storage and delivery systems. But it introduces the fundamental difficulty of ensuring that all erasure-coded fragments correspond to the same block of data. Without such assurance, a different block may be reconstructed from different subsets of fragments. This paper develops a technique for providing this assurance without the bandwidth and computational overheads associated with current approaches. The core idea is to distribute with each fragment what we call homomorphic fingerprints. These fingerprints preserve the structure of the erasure code and allow each fragment to be independently verified as corresponding to a specific block. We demonstrate homomorphic fingerprinting functions that are secure, efficient, and compact.
A canonical distributed optimization problem is solving a Covering/Packing Linear Program in a distributed environment with fast convergence and low communication and space overheads. In this paper, we consider the fo...
详细信息
ISBN:
(纸本)9781595936165
A canonical distributed optimization problem is solving a Covering/Packing Linear Program in a distributed environment with fast convergence and low communication and space overheads. In this paper, we consider the following covering and packing problems, which are the dual of each other: Passive Commodity Monitoring: minimize the total cost of monitoring devices used to measure the network traffic on all paths. Maximum Throughput Multicommodity flow: maximize the total value of the flow with bounded edge capacities. We present the first known distributed algorithms for both of these problems that converge to (1 + epsilon)-approximate solutions in poly-logarithmic time with communication and space overheads that depend on the maximal path length but are almost independent of the size of the entire network. Previous distributed solutions achieving similar approximations required convergence time, communication, or space overheads that depend polynomially on the size of the entire network. The sequential simulation of our algorithm is more efficient than the fastest known approximation algorithms for multicommodity flows, e.g., Garg-Konemann [14], when the maximal path length is small.
Currently, there are no known explicit algorithms for the great majority of graph problems in the dynamic distributed message-passing model. Instead, most state-of-the-art dynamic distributed algorithms are constructe...
详细信息
ISBN:
(纸本)9781595936165
Currently, there are no known explicit algorithms for the great majority of graph problems in the dynamic distributed message-passing model. Instead, most state-of-the-art dynamic distributed algorithms are constructed by composing a static algorithm for the problem at hand with a simulation technique that converts static algorithms to dynamic ones. We argue that this powerful methodology does not provide satisfactory solutions for many important dynamic distributed problems;and this necessitates developing algorithms for these problems from scratch. In this paper we develop a fully dynamic distributed algorithm for maintaining sparse spanners. Our algorithm improves drastically the quiescence time of the state-of-the-art algorithm for the problem. Moreover, we show that the quiescence time of our algorithm is optimal tip to a small constant factor. In addition, our algorithm improves significantly upon the state-of-the-art algorithm in all efficiency parameters, specifically, it has smaller quiescence message and space complexities, and smaller local processing time. Finally, our algorithm is self-contained and fairly simple, and is, consequently, amenable to implementation on unsophisticated network devices.
Motivation. Recommendation systems are an important ingredient of modern life, where people must make decisions with partial information [6]. Everyday examples include buying books, going to a movie, choosing an on-li...
详细信息
暂无评论