Output Stability Versus Time Till Output (Extended Abstract)

摘要

Consider a network whose inputs change rapidly, or are subject to frequent faults. This is expected often to be the case in the foreseen huge sensor networks. Suppose, that an algorithm is required to output the majority value of the inputs. To address such networks, it is desirable to be able to stabilize the output fast, and to give guarantees on the outputs even before stabilization, even if additional changes occur. We bound the instability of the outputs (the number of times the output changes) of majority consensus algorithms even before the final stabilization. We show that the instability can be traded off with their time adaptvity (how fast they are required to stabilize the output if f faults occurred). First, for the extreme point of the trade-off, we achieve instability that is optimal for the class of algorithms that are optimal in their output time adaptivity. This is done for various known versions of majority consensus problem. The optimal instability for this case is Ω(log f) and is shown to be O(log f) for most versions and O(logn) in some cases. Previous such algorithms did not have such a guarantee on the behaviour of the output before its final stabilization (and their instability was Ω(n)). We also explain how to adapt the results for other points in the trade off. The output stabilization in previous algorithms was adaptive only if the faults ceased for O(Diam) time. An additional result in this paper uses adaptations of some previous tools, as well as the new tools developed here for bounding the instability, in order to remove this limitation that is undesirable when changes are frequent.