We present DRR-gossip, an energy-efficient and robust aggregate computation algorithm in wireless sensor networks. We prove that the DRR-gossip algorithm requires O(n) messages and O(n(3/2)/log(1/2)n) one-hop wireless...
详细信息
ISBN:
(纸本)9781605583969
We present DRR-gossip, an energy-efficient and robust aggregate computation algorithm in wireless sensor networks. We prove that the DRR-gossip algorithm requires O(n) messages and O(n(3/2)/log(1/2)n) one-hop wireless transmissions to obtain aggregates on a random geometric graph. This reduces the energy consumption by at least a factor of 1/log(n) over the standard uniform gossip algorithm. Experiments validate the theoretical results and show that DRR-gossip needs much less transmissions than other gossip-based schemes.
This paper presents two distributed algorithms for detecting and resolving deadlocks. By insuring that only one of the deadlock processes will detect it, the problem of resolving the deadlock is simplified. That proce...
详细信息
ISBN:
(纸本)0897911431
This paper presents two distributed algorithms for detecting and resolving deadlocks. By insuring that only one of the deadlock processes will detect it, the problem of resolving the deadlock is simplified. That process could simply abort itself. In one version of the algorithm, an arbitrary process detects deadlock;and in a second version, the process with the lowest priority detects deadlock.
In this paper we combine two previously disparate aspects of reliable distributedcomputing - self-stabilization, i.e., tolerance of systemic failures, and fault-tolerance, i.e., tolerance of process failures. We defi...
详细信息
ISBN:
(纸本)0897916131
In this paper we combine two previously disparate aspects of reliable distributedcomputing - self-stabilization, i.e., tolerance of systemic failures, and fault-tolerance, i.e., tolerance of process failures. We define what it means for a protocol to solve a problem while tolerating both types of failures and demonstrate a `compiler' that transforms a process failure-tolerant protocol for a synchronous system into a process and systemic failure-tolerant protocol. For asynchronous systems, we present a protocol that solves a crucial problem (Consensus) while tolerating both process and systemic failures.
A distributed move-to-front list is a data object that abstracts a temporal ordering on a set of processes in a distributed system. We present a lower bound and a matching upper bound of ®(log2n) bits on the spac...
The problem of tolerating crash/or link failures has been extensively studied. These studies focused on a single link, and how to mask failures of that link. In contrast, this paper studies lossy links in the context ...
详细信息
ISBN:
(纸本)9780897918008
The problem of tolerating crash/or link failures has been extensively studied. These studies focused on a single link, and how to mask failures of that link. In contrast, this paper studies lossy links in the context of an entire system: it is shown that the effect of lossy links depends on the proportion of faulty processes in the system. The results assume permanent process crashes, and more importantly, the effect of adding link failures on the solvability of problems in general is studied. This approach stresses the importance of the notion of correct-restricted problems.
I present the first randomized wait-free implementation of consensus from multiple writer multiple reader register in which each process takes polylog (O(log2n)) expected steps. To achieve this result, I assume a non-...
详细信息
ISBN:
(纸本)9780897918008
I present the first randomized wait-free implementation of consensus from multiple writer multiple reader register in which each process takes polylog (O(log2n)) expected steps. To achieve this result, I assume a non-standard type of adversary (from [Abr88]). I argue that this type of adversary (which is more powerful than the oblivious adversary, but weaker than the strong adversary) is powerful enough to model practical systems.
This paper introduces two new novel tools for the study of distributedcomputing and shows their utility by using them to exhibit a simple derivation of the Herlihy and Shavit characterization of wait-free shared-memo...
详细信息
This paper introduces two new novel tools for the study of distributedcomputing and shows their utility by using them to exhibit a simple derivation of the Herlihy and Shavit characterization of wait-free shared-memory computation. The first tool is the notion of the iterated version of a given model. We show that the topological structure that corresponds to an iterated model has a nice recursive structure, and that the iterated version of the atomic snapshot memory solves any task solvable by the non-iterated model. The second tool is an iterated explicit simple convergence algorithm. In the Ph.D. Thesis of the first author these tool were used to characterize models more complex than read-write shared-memory.
In a previous study, Burns and Lynch proved that at least n multi-writer-multi-reader (MWMR) registers are necessary in any mutual exclusion algorithm that uses only MWMR registers. The present work extends the techni...
详细信息
In a previous study, Burns and Lynch proved that at least n multi-writer-multi-reader (MWMR) registers are necessary in any mutual exclusion algorithm that uses only MWMR registers. The present work extends the techniques of Burns and Lynch to prove that adaptive algorithms that use both n single-writer-multi-reader (SWMR) and MWMR registers, need in addition to the Ω(n) SWMR registers a non-constant, F(n) number of MWMR registers.
A new location management strategy that employs dynamic hashing and quorums is presented. Location information of a mobile host is replicated at a subset of location servers. New location can be added to the system as...
详细信息
ISBN:
(纸本)9780897919524
A new location management strategy that employs dynamic hashing and quorums is presented. Location information of a mobile host is replicated at a subset of location servers. New location can be added to the system as the number of mobile hosts and/or location update and query rates increase. The proposed scheme requires at most two rounds of message multicasting for location update and query operations. This compares favorably with hierarchical schemes that require O(lg N) rounds of unicast messages, where N is the total number of location servers.
The distinction between safety and liveness properties is due to Lamport who gave the following informal characterization. Safety properties assert that nothing bad ever happens while liveness properties assert that s...
详细信息
ISBN:
(纸本)9781581137088
The distinction between safety and liveness properties is due to Lamport who gave the following informal characterization. Safety properties assert that nothing bad ever happens while liveness properties assert that something good happens eventually. In a well-known paper Alpern and Schneider gave a topological characterization of safety and liveness for the linear time framework. Gumm has stated these notions in the more abstract setting of V-complete Boolean algebras. Recently, we characterized safety and liveness for the branching time framework and found that neither the topological characterization nor Gumm's characterization were general enough for our needs. We present a lattice-theoretic characterization that allows us to unify previous results on safety and liveness, including the results for the linear time and branching time frameworks and for ω-regular string and tree languages.
暂无评论