distributedcomputing has to adapt its techniques to mobile sensor networks and cope with constraints like small memory size or lack of computation power. In this paper we extend the results of Angluin et at (see [1, ...
详细信息
ISBN:
(纸本)9781595936165
distributedcomputing has to adapt its techniques to mobile sensor networks and cope with constraints like small memory size or lack of computation power. In this paper we extend the results of Angluin et at (see [1, 2, 3, 4]) by finding self-stabilizing algorithms to count the number of agents in the network. We focus on two different models of communication, with a fixed antenna or with pairwise interactions. In both models we decide if there exist algorithms (probabilistic, deterministic, with k-fair adversary) to solve the self-stabilizing counting problem.
A fundamental difficulty in proving randomized distributed algorithms correct arises due to the presence of both probabilistic choice as well as nondeterminism. The algorithm is based on the reachability graph analysi...
详细信息
ISBN:
(纸本)9780897919524
A fundamental difficulty in proving randomized distributed algorithms correct arises due to the presence of both probabilistic choice as well as nondeterminism. The algorithm is based on the reachability graph analysis, and its complexity is necessarily exponential in the number of states and linear in the size of the formula. An efficient, BDD-based, model checking procedure for the more restrictive logic is formulated.
We prove tight upper and lower bounds of Θ(t/√n log n) on the expected number of rounds needed for randomized synchronous consensus protocols for a fail-stop, full information, dynamic adversary. In particular this ...
详细信息
We prove tight upper and lower bounds of Θ(t/√n log n) on the expected number of rounds needed for randomized synchronous consensus protocols for a fail-stop, full information, dynamic adversary. In particular this proves that some restrictions are needed on the power of the adversary to allow randomized constant expected number of rounds protocols.
We present an efficient fault-tolerant solution to the distributed mutual exclusion problem. Our protocol requires log n messages in the best case and is resilient to both site and communication failures, even when su...
详细信息
ISBN:
(纸本)0897913264
We present an efficient fault-tolerant solution to the distributed mutual exclusion problem. Our protocol requires log n messages in the best case and is resilient to both site and communication failures, even when such failures lead to network partitioning. Furthermore, the protocol exhibits a property of graceful degradation, i.e., it requires more message only as the number of failures increase in the network.
We prove that the primary-partition group membership problem cannot be solved in asynchronous systems with crash failures, even if one allows the removal or killing of non-faulty processes that are erroneously suspect...
详细信息
We prove that the primary-partition group membership problem cannot be solved in asynchronous systems with crash failures, even if one allows the removal or killing of non-faulty processes that are erroneously suspected to have crashed.
Quorum systems serve as a basic tool providing a uniform and reliable way to achieve coordination in a distributed system. They are used for distributed and replicated databases, name servers, mutual exclusion, and di...
详细信息
Quorum systems serve as a basic tool providing a uniform and reliable way to achieve coordination in a distributed system. They are used for distributed and replicated databases, name servers, mutual exclusion, and distributed access control and signatures. Traditionally, two basic methods have used to evaluate quorum systems: the first is the analytical approach. The second approach is simulation. This paper proposes an empirical approach to evaluate systems. The results of the evaluation are presented.
暂无评论