Specifying Distributed Hash Tables with Allen Temporal Logic
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 AprDisplayed 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 30mTalk | 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 30mTalk | 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 30mTalk | Detecting Redundant Preconditions Research Track Nicola Thoben University of Oldenburg, Heike Wehrheim Carl von Ossietzky Universität Oldenburg / University of Oldenburg |