A Sufficient Epistemic Condition for Solving Stabilizing Agreement
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910350471856128 |
|---|---|
| author | Cignarale, Giorgio Felber, Stephan Galeana, Hugo Rincon |
| author_facet | Cignarale, Giorgio Felber, Stephan Galeana, Hugo Rincon |
| contents | In this paper we provide a first-ever epistemic formulation of stabilizing agreement, defined as the non-terminating variant of the well established consensus problem. In stabilizing agreements, agents are given (possibly different) initial values, with the goal to eventually always decide on the same value. While agents are allowed to change their decisions finitely often, they are required to agree on the same value eventually. We capture these properties in temporal epistemic logic and we use the Runs and Systems framework to formally reason about stabilizing agreement problems. We then epistemically formalize the conditions for solving stabilizing agreement, and identify the knowledge that the agents acquire during any execution to choose a particular value under our system assumptions. This first formalization of a sufficient condition for solving stabilizing agreement sets the stage for a planned necessary and sufficient epistemic characterization of stabilizing agreement. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_01025 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Sufficient Epistemic Condition for Solving Stabilizing Agreement Cignarale, Giorgio Felber, Stephan Galeana, Hugo Rincon Distributed, Parallel, and Cluster Computing Logic in Computer Science C.2.4; F.3.1 In this paper we provide a first-ever epistemic formulation of stabilizing agreement, defined as the non-terminating variant of the well established consensus problem. In stabilizing agreements, agents are given (possibly different) initial values, with the goal to eventually always decide on the same value. While agents are allowed to change their decisions finitely often, they are required to agree on the same value eventually. We capture these properties in temporal epistemic logic and we use the Runs and Systems framework to formally reason about stabilizing agreement problems. We then epistemically formalize the conditions for solving stabilizing agreement, and identify the knowledge that the agents acquire during any execution to choose a particular value under our system assumptions. This first formalization of a sufficient condition for solving stabilizing agreement sets the stage for a planned necessary and sufficient epistemic characterization of stabilizing agreement. |
| title | A Sufficient Epistemic Condition for Solving Stabilizing Agreement |
| topic | Distributed, Parallel, and Cluster Computing Logic in Computer Science C.2.4; F.3.1 |
| url | https://arxiv.org/abs/2403.01025 |