License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2023.15
URN: urn:nbn:de:0030-drops-182086
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18208/
Go to the corresponding LIPIcs Volume Portal

Kuhn, Roland ; Melgratti, Hernán ; Tuosto, Emilio

Behavioural Types for Local-First Software

pdf-format:
LIPIcs-ECOOP-2023-15.pdf (1 MB)

Abstract

Peer-to-peer systems are the most resilient form of distributed computing, but the design of robust protocols for their coordination is difficult. This makes it hard to specify and reason about global behaviour of such systems.
This paper presents swarm protocols to specify such systems from a global viewpoint. Swarm protocols are projected to machines, that is local specifications of peers. We take inspiration from behavioural types with a key difference: peers communicate through an event notification mechanism rather than through point-to-point message passing. Our goal is to adhere to the principles of local-first software where network devices collaborate on a common task while retaining full autonomy: every participating device can locally make progress at all times, not encumbered by unavailability of other devices or network connections. This coordination-free approach leads to inconsistencies that may emerge during computations. Our main result shows that under suitable well-formedness conditions for swarm protocols consistency is eventually recovered and the locally observable behaviour of conforming machines will eventually match the global specification.
Our model elaborates on the Actyx industrial platform and provides the basis for tool support: we sketch an implemented prototype which proves this work a viable step towards reasoning about local-first and peer-to-peer software systems.

BibTeX - Entry

@InProceedings{kuhn_et_al:LIPIcs.ECOOP.2023.15,
  author =	{Kuhn, Roland and Melgratti, Hern\'{a}n and Tuosto, Emilio},
  title =	{{Behavioural Types for Local-First Software}},
  booktitle =	{37th European Conference on Object-Oriented Programming (ECOOP 2023)},
  pages =	{15:1--15:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-281-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{263},
  editor =	{Ali, Karim and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18208},
  URN =		{urn:nbn:de:0030-drops-182086},
  doi =		{10.4230/LIPIcs.ECOOP.2023.15},
  annote =	{Keywords: Distributed coordination, local-first software, behavioural types, publish-subscribe, asynchronous communication}
}

Keywords: Distributed coordination, local-first software, behavioural types, publish-subscribe, asynchronous communication
Collection: 37th European Conference on Object-Oriented Programming (ECOOP 2023)
Issue Date: 2023
Date of publication: 11.07.2023
Supplementary Material: Software (ECOOP 2023 Artifact Evaluation approved artifact): https://doi.org/10.4230/DARTS.9.2.14

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI