Tight Bounds for Stabilizing Uniform Consensus in Mobile Networks

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.