Felber, S. (2026, June 15). Characterizing Stabilizing Consensus Topologically and Epistemically [Presentation]. CELT 2026 : Epistemic logic and topological perspectives on distributed computing, Paris, France. https://doi.org/10.34726/12340
E191-02 - Forschungsbereich Embedded Computing Systems
-
Date (published):
15-Jun-2026
-
Event name:
CELT 2026 : Epistemic logic and topological perspectives on distributed computing
en
Event date:
15-Jun-2026 - 18-Jun-2026
-
Event place:
Paris, France
-
Keywords:
epistemic logic; topology
en
Abstract:
A classic result in the epistemic analysis of distributed systems is the equivalence of terminating consensus and common knowledge. Originally established for simultaneous consensus only, Gonczarowski and Moses have recently shown how to overcome the fundamental ``Halpern-Moses Paradox'', which inevitably arises in systems with timing uncertainties and plagued attempts to establish an analogous result for non-simultaneous consensus.
In this presentation we present results from our recent paper where we build on, and non-trivially extend the latter approach to establish the very first necessary and sufficient epistemic conditions for solving stabilizing consensus. Stabilizing consensus is a non-terminating variant of consensus, where agents may change their decision value finitely often before eventually stabilizing on a common value. Since it is a weaker problem than terminating consensus, stabilizing consensus can be solved in systems where the latter is unsolvable. Our results reveal that, in order to solve stabilizing consensus, agents need to establish a novel notion of common knowledge, called common foreknowledge. Moreover, we show that our epistemic characterizations of both terminating and stabilizing consensus correspond one-to-one to the respective topological characterizations. We achieve this by establishing a novel connection between the knowledge defined on the points of the runs-and-systems framework and the point-set topology defined directly on the set of runs: Dynamic common knowledge, as defined by Gonczarowski and Moses, holds in (and requires) clopen sets and our novel common foreknowledge holds in (and requires) semi-open sets.
en
Research Areas:
Mathematical and Algorithmic Foundations: 50% Computer Science Foundations: 50%