2026-09-13T04:32:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24832 2026-09-05T18:58:34Z ddc:004 open_access

Asynchronous Latency and Fast Atomic Snapshot Bezerra, João Paulo Freitas, Luciano Kuznetsov, Petr Rambaud, Matthieu Asynchronous systems time complexity atomic snapshot crash faults This paper introduces a novel, fast atomic-snapshot protocol for asynchronous message-passing systems. In the process of defining what "fast" means exactly, we spot a few interesting issues that arise when conventional time metrics are applied to long-lived asynchronous algorithms. We reveal some gaps in latency claims made in earlier work on snapshot algorithms, which hamper their comparative time-complexity analysis. We then come up with a new unifying time-complexity metric that captures the latency of an operation in an asynchronous, long-lived implementation. This allows us to formally grasp latency improvements of our atomic-snapshot algorithm with respect to the state-of-the-art protocols: optimal latency in fault-free runs without contention, short constant latency in fault-free runs with contention, the worst-case latency proportional to the number of active concurrent failures, and constant amortized latency. Schloss Dagstuhl – Leibniz-Zentrum für Informatik João Paulo Bezerra and Luciano Freitas and Petr Kuznetsov and Matthieu Rambaud 2025 Is Part Of LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2025.15 urn:nbn:de:0030-drops-248326 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.15 eng https://creativecommons.org/licenses/by/4.0/legalcode