®®®® SIIA Público

Título del libro:
Título del capítulo: Towards Efficient Runtime Verified Linearizable Algorithms

Autores UNAM:
GILDE VALERIA RODRIGUEZ JIMENEZ;
Autores externos:

Idioma:

Año de publicación:
2025
Palabras clave:

Distributed computer systems; Asynchronous concurrent; Asynchronous concurrent algorithm; Concurrent algorithms; Distributed runtime; Distributed runtime verification; Fault-tolerant; Linearizability; Run-time verification; Runtimes; Simple++; Consensus algorithm


Resumen:

An asynchronous, fault-tolerant, sound and complete algorithm for runtime verification of linearizability of concurrent algorithms was proposed in [7]. This solution relies on the snapshot abstraction in distributed computing. The fastest known snapshot algorithms use complex constructions, hard to implement, and the simplest ones provide large step complexity bounds or only weak termination guarantees. Thus, the snapshot-based verification algorithm is not completely satisfactory. In this paper, we propose an alternative solution, based on the collect abstraction, which can be optimally implemented in a simple manner. As a final result, we offer a simple and generic methodology that takes any presumably linearizable algorithm and produces a lightweight runtime verified linearizable version of it. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.


Entidades citadas de la UNAM: