FormaliSE 2025
Sun 27 - Mon 28 April 2025 Ottawa, Ontario, Canada
co-located with ICSE 2025
Sun 27 Apr 2025 16:00 - 16:30 at 203 - Session 3 - Temporal Logic and Contracts Chair(s): Domenico Bianculli

Distributed Hash Tables (DHTs) remain to this day a central component of modern peer-to-peer (P2P) systems, which rely on complex DHTs protocols to scale to millions of nodes. Consequently, the correct operation of DHTs is essential for the proper functioning of many practical and P2P systems. For this reason, formal methods have been employed to model and verify a range of correctness properties of various DHT protocols. However, these verification efforts have focused on protocol-specific properties, such as topological invariants, instead of functional properties. This focus limits our understanding of the precise guarantees offered by each protocol. To improve the current state of the art, in this paper we propose a protocol-independent axiomatization of DHT properties using Allen Temporal Logic (ATL). To validate our axiomatization, we have implemented it in the Alloy analyser and used our implementation to establish a number of DHT-derived properties and generate a set of DHT execution traces that cover an exhaustive list of DHT corner case behaviours.

Sun 27 Apr

Displayed time zone: Eastern Time (US & Canada) change

16:00 - 17:30
Session 3 - Temporal Logic and ContractsResearch Track at 203
Chair(s): Domenico Bianculli University of Luxembourg
16:00
30m
Talk
Specifying Distributed Hash Tables with Allen Temporal Logic
Research Track
Nuno Policarpo Instituto Superior Técnico, University of Lisbon, José Fragoso Santos INESC-ID; Instituto Superior Técnico - University of Lisbon, Alcino Cunha University of Minho; INESC TEC, João Leitão NOVA LINCS & FCT, NOVA University of Lisbon, Pedro Ákos Costa NOVA LINCS & DI-FCT-UNL
16:30
30m
Talk
Temporal Logics Meet Real-World Software Requirements: A Reality Check
Research Track
Roman Bögli University of Bern, Atefeh Rohani University of Bern, Thomas Studer University of Bern, Christos Tsigkanos University of Athens, Greece, Timo Kehrer University of Bern
17:00
30m
Talk
Detecting Redundant Preconditions
Research Track
Nicola Thoben University of Oldenburg, Heike Wehrheim Carl von Ossietzky Universität Oldenburg / University of Oldenburg