We study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier ...
详细信息
ISBN:
(纸本)9781450320658
We study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier and can move along the barrier. The goal is to find final positions for sensors so that the entire barrier is covered. In recent years, the problem has been studied extensively in the centralized setting. In this paper, we study the problem in the distributed setting. We assume each sensor repeatedly executes a Look-Compute-Move cycle: based on what it sees in its vicinity, it makes a decision on where to move, and moves to its next position. We make two strong but realistic restrictions on the capabilities of sensors: they have a constant visibility rang e and can move only a constant distance in every cycle. In this model, we give the first two distributed algorithms that achieve barrier coverage for a line segment barrier when there are enough nodes in the network to cover the entire barrier. Our algorithms are synchronous, and local in the sense that sensors make their decisions independently based only on what they see within their constant visibility range. One of our algorithms is oblivious whereas the other uses two bits of memory at each sensor to store the type of move made in the previous step. We show that our oblivious algorithm terminates within θ(n2) steps with the barrier fully covered, while the constant-memory algorithm is shown to take θ(n) steps to terminate in the worst case. Since any algorithm that can only move a constant distance in one step requires ω(n) steps on some inputs, our second algorithm is asymptotically optimal. Finally, both our algorithms are self-stabilizing, and can be easily extended to the case of non-homogeneous sensors, and for the case when the barrier is a circle. Copyright 2013 acm.
The first version of the MPI standard was released in November 1993. At the time, many of the authors of this standard, myself included, viewed MPI as a temporary solution, to be used until it is replaced by a good pr...
详细信息
ISBN:
(纸本)9781450320658
The first version of the MPI standard was released in November 1993. At the time, many of the authors of this standard, myself included, viewed MPI as a temporary solution, to be used until it is replaced by a good programming language for distributed memory systems. Almost twenty years later, MPI is the main programming model for High-Performance computing, and practically all HPC applications use MPI, which is now in its third generation; nobody expects MPI to disappear in the coming decade. The talk will discuss some plausible reasons for this situation, and the implications for research on new programming models for Extreme-Scale computing.
We study a fundamental measure for wireless interference in the SINR model known as (weighted) inductive independence. This measure characterizes the electiveness of using oblivious power - when the power used by a tr...
详细信息
ISBN:
(纸本)9781611972511
We study a fundamental measure for wireless interference in the SINR model known as (weighted) inductive independence. This measure characterizes the electiveness of using oblivious power - when the power used by a transmitter only depends on the distance to the receiver - as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves - due to existing lower bounds - capacity that is asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems for oblivious power and for power control, including distributed scheduling, connectivity, secondary spectrum auctions, and dynamic packet scheduling.
The proceedings contain 61 papers. The topics discussed include: random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time;coalescing random walks and voting on graphs;the co...
ISBN:
(纸本)9781450314503
The proceedings contain 61 papers. The topics discussed include: random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time;coalescing random walks and voting on graphs;the cost of fault tolerance in multi-party communication complexity;the communication complexity of distributed task allocation;collaborative search on the plane without communication;universal constructions that ensure disjoint-access parallelism and wait-freedom;generalized lattice agreement;distributed selfish load balancing with weights and speeds;making evildoers pay: resource-competitive broadcast in sensor networks;distributed public key schemes secure against continual leakage;weak models of distributedcomputing, with connections to modal logic;aggregation in dynamic networks;leader election in shared spectrum radio networks;and breaking the O(nm) bit barrier, secure multiparty computation with a static adversary.
Asynchronous Verifiable Secret Sharing (AVSS) is a fundamental primitive in secure distributedcomputing. It finds significant application in problems like asynchronous Byzantine Agreement (ABA) and Asynchronous Multi...
详细信息
Version vectors (VV) are used pervasively to track dependencies between replica versions in multi-version distributed storage systems. In these systems, VV tend to have a dual functionality: identify a version and enc...
详细信息
This work considers Internet-based task computations in which a master process assigns tasks, over the Internet, to rational workers and collect their responses. The objective is for the master to obtain the correct t...
详细信息
暂无评论