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.
We present energy efficient algorithms for leader election in single channel single-hop radio networks with no collision detection. We present a deterministic solution with sublogarithmic energy cost (the best previou...
详细信息
ISBN:
(纸本)9781581134858
We present energy efficient algorithms for leader election in single channel single-hop radio networks with no collision detection. We present a deterministic solution with sublogarithmic energy cost (the best previous result was O(log n)) and show a double logarithmic lower bound. We prove that this lower bound holds in a randomized case, in a certain sense. For the case, when the number n of active stations can be approximated in advance, we show a randomized algorithm with energy consumption O(log* n) that yields a result with high probability (the best previous result was O(log log n)).
In this paper, we study the inherent tradeoff between the network connectivity, phase complexity and communication complexity of perfectly reliable message transmission (PRMT) problem in undirected synchronous, networ...
详细信息
ISBN:
(纸本)9781595939890
In this paper, we study the inherent tradeoff between the network connectivity, phase complexity and communication complexity of perfectly reliable message transmission (PRMT) problem in undirected synchronous, network, tolerating a mixed adversary A(t(b), t(f)), who has unbounded computing power and can corrupt t(b) and t(f) nodes in the network in Byzantine and fail-stop fashion respectively.
It is shown that consensus hierarchy is not robust if object types are allowed to be infinite branching. To avoid the possibility of wait-free algorithms with unbounded running times when using infinite objects, a sli...
详细信息
It is shown that consensus hierarchy is not robust if object types are allowed to be infinite branching. To avoid the possibility of wait-free algorithms with unbounded running times when using infinite objects, a slightly modified definition of wait-freedom is used. Key and Lock are used to solve consensus for any number of processes, showing consensus hierarchy is not robust.
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.
暂无评论