Gainer, Paul, Linker, Sven ORCID: 0000-0003-2913-7943, Dixon, Clare ORCID: 0000-0002-4610-9533, Hustadt, Ullrich ORCID: 0000-0002-0455-0267 and Fisher, Michael
(2020)
Multi-Scale Verification of Distributed Synchronisation.
Formal Methods in System Design, 55 (3).
pp. 171-221.
This is the latest version of this item.
Text
sync_journal.pdf - Author Accepted Manuscript Download (620kB) | Preview |
|
Text
1809.10655v1.pdf - Submitted version Download (456kB) |
Abstract
Algorithms for the synchronisation of clocks across networks are both common and important within distributed systems. We here address not only the formal modelling of these algorithms, but also the formal verification of their behaviour. Of particular importance is the strong link between the very different levels of abstraction at which the algorithms may be verified. Our contribution is primarily the formalisation of this connection between individual models and population-based models, and the subsequent verification that is then possible. While the technique is applicable across a range of synchronisation algorithms, we particularly focus on the synchronisation of (biologically-inspired) pulse-coupled oscillators, a widely used approach in practical distributed systems. For this application domain, different levels of abstraction are crucial: models based on the behaviour of an individual process are able to capture the details of distinguished nodes in possibly heterogenous networks, where each node may exhibit different behaviour. On the other hand, collective models assume homogeneous sets of processes, and allow the behaviour of the network to be analysed at the global level. System-wide parameters may be easily adjusted, for example environmental factors inhibiting the reliability of the shared communication medium. This work provides a formal bridge across the “abstraction gap” separating the individual models and the population-based models for this important class of synchronisation algorithms.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Synchronisation, Pulse-coupled oscillators, Abstraction, Probabilistic verification, Weak bisimulation |
Depositing User: | Symplectic Admin |
Date Deposited: | 21 Oct 2020 12:00 |
Last Modified: | 18 Jan 2023 23:26 |
DOI: | 10.1007/s10703-020-00347-z |
Open Access URL: | https://link.springer.com/article/10.1007%2Fs10703... |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3104727 |
Available Versions of this Item
-
Multi-Scale Verification of Distributed Synchronisation. (deposited 10 Jul 2020 08:19)
- Multi-Scale Verification of Distributed Synchronisation. (deposited 21 Oct 2020 12:00) [Currently Displayed]