Alafin, Oluwatobi, Mertzios, George B 
ORCID: 0000-0001-7182-585X and Spirakis, Paul G ORCID: 0000-0001-5396-3749
(2026)
Round-Asynchronous Amnesiac Flooding
In: ALGOWIN-ALGO2025, 2025-9-18 - 2025-9-19, Warsaw Poland.
|
Text
Asynchronous_amnesiac_flooding.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (528kB) | Preview |
Abstract
We present a comprehensive analysis of Round-Asynchronous Amnesiac Flooding (RAAF), a variant of Amnesiac Flooding that introduces round-based asynchrony through adversarial delays. We establish fundamental properties of RAAF, including termination characteristics for different graph types and decidability results under various adversarial models. Our key contributions include: (1) a formal model of RAAF incorporating round-based asynchrony, (2) a proof that flooding always terminates on acyclic graphs despite adversarial delays, (3) a construction showing non-termination is possible on any cyclic graph, (4) a demonstration that termination is undecidable with arbitrary computable adversaries, and (5) the introduction of Eventually Periodic Adversaries (EPA) under which termination becomes decidable. These results enhance our understanding of flooding processes in asynchronous settings and provide insights for designing robust distributed protocols.
| Item Type: | Conference Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | 46 Information and Computing Sciences |
| Divisions: | Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 04 Aug 2025 09:10 |
| Last Modified: | 04 Jan 2026 18:12 |
| DOI: | 10.1007/978-3-032-09120-8_3 |
| Related Websites: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3193903 |
| Disclaimer: | The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate. |
Altmetric
Altmetric