Talks and Poster Presentations (with Proceedings-Entry):
M. Schwarz, K. Winkler, U. Schmid:
"Fast Consensus Under Eventually Stabilizing Message Adversaries";
Talk: 17th International Conference on Distributed Computing and Networking,
- 2016-01-07; in: "Proceedings of the 17th International Conference on Distributed Computing and Networking",
This paper is devoted to deterministic consensus in synchronous dynamic networks with unidirectional links, which are under the control of an omniscient message adversary. Motivated by unpredictable node/system initialization times and long-lasting periods of massive transient faults, we consider message adversaries that guarantee periods of less erratic message loss only eventually: We present a tight bound of 2D+1 for the termination time of consensus under a message adversary that eventually guarantees a single vertex-stable root component with dynamic network diameter D, as well as a simple algorithm that matches this bound. It effectively halves the termination time 4D+1 achieved by the fastest consensus algorithm known so far. We also introduce a generalized, considerably stronger variant of our message adversary, and show that our new algorithm, unlike the existing one, still works correctly under it.
Directed dynamic network; consensus; message adversary; stability; root component
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Created from the Publication Database of the Vienna University of Technology.