[Back]

K. Winkler, U. Schmid, T. Nowak:
"Valency-based Consensus under Message Adversaries without Limit-Closure";
Talk: Fundamentals of Computation Theory, Athens, Greece; 2021-09-12 - 2021-09-15; in: "Proceedings 23rd International Symposium on Fundamentals of Computation Theory (FCT'21)", Springer, Lecture Notes in Computer Science LNCS 12867 (2021), ISBN: 978-3-030-86592-4; 457 - 474.

We introduce a novel two-step approach for developing a
distributed consensus algorithm, which does not require the designer to identify and exploit intricacies of the underlying system model explicitly. In a first step, which is typically done off-line only once, labels representing valid decision values (valencies) are assigned to suitable prefixes of all possible runs. The challenge here is to assign them consistently for indistinguishable runs. The second step consists in deploying a simple generic distributed consensus algorithm, which just uses the previously computed labeling. If it observes that all runs that may lead to a local state that is indistinguishable from the current local state have the same label, it decides on the value determined by this label, otherwise it has to
keep on checking. We demonstate the power of our approach by develop-
ing a new and asymptotically optimal consensus algorithm for dynamic
networks under eventually stabilizing message adversaries for arbitrary system sizes.

dynamic networks, message adversaries, consensus, impossibility results

http://dx.doi.org/10.1007/978-3-030-86593-1_32