Advertisement
Published in:
2014 | OriginalPaper | Chapter
Tight Bounds for Stabilizing Uniform Consensus in Mobile Networks
Authors : Hung Tran-The, Luís Rodrigues
Published in: Stabilization, Safety, and Security of Distributed Systems
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper addresses the problem of solving stabilizing uniform consensus in mobile networks. In this problem, the input of nodes may change multiple times before they eventually stabilize. However, when the system stabilizes all correct nodes output a value and there are no two non-crashed nodes (whether faulty or not) that output different values. In contrast to stabilizing consensus, stabilizing uniform consensus is not solvable with Byzantine faults. So we consider here weaker kinds of faults, namely crash faults and omission faults. We show that for crash and send-omission faults,
n
> 2
t
is a necessary and sufficient condition for solving stabilizing uniform consensus, where
n
is the total number of mobile nodes, out of which
t
may be faulty. Interestingly, when the input of nodes are fixed, stabilizing uniform consensus is solvable with crash faults for
n
>
t
and with send-omission faults for
n
> 2
t
(for
t
> 1). When considering general omission faults, we show that stabilizing uniform consensus is not solvable, even for fixed inputs and
t
= 1.