A Fixpoint-Based Calculus for Graph-Shaped Computational Fields

Alberto Lluch Lafuente, Michele Loreti, Ugo Montanari

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

207 Downloads (Pure)

Abstract

Coordination is essential for dynamic distributed systems exhibiting autonomous behaviors. Spatially distributed, locally interacting, propagating computational fields are particularly appealing for allowing components to join and leave with little or no overhead. In our approach, the space topology is represented by a graph-shaped field, namely a network with attributes on both nodes and arcs, where arcs represent interaction capabilities between nodes. We propose a calculus where computation is strictly synchronous and corresponds to sequential computations of fixpoints in the graph-shaped field. Under some conditions, those fixpoints can be computed by synchronised iterations, where in each iteration the attributes of a node is updated based on the attributes of the neighbours in the previous iteration. Basic constructs are reminiscent of the semiring μ-calculus, a semiring-valued generalisation of the modal μ-calculus, which provides a flexible mechanism to specify the neighbourhood range (according to path formulae) and the way attributes should be combined (through semiring operators). Additional control-How constructs allow one to conveniently structure the fixpoint computations. We illustrate our approach with a case study based on a disaster recovery scenario, implemented in a prototype simulator that we use to evaluate the performance of a disaster recovery strategy.
Original languageEnglish
Title of host publicationCoordination Models and Languages : Proceedings of the 17th IFIP WG 6.1 International Conference (COORDINATION 2015)
EditorsTom Holvoet, Mirko Viroli
PublisherSpringer
Publication date2015
Pages101-116
ISBN (Print)978-3-319-19281-9
ISBN (Electronic)978-3-319-19282-6
DOIs
Publication statusPublished - 2015
Event17th IFIP WG 6.1 International Conference, COORDINATION 2015 - Grenoble, France
Duration: 2 Jun 20154 Jun 2015
Conference number: 17
http://discotec2015.inria.fr/coordination-2015-call-for-papers/

Conference

Conference17th IFIP WG 6.1 International Conference, COORDINATION 2015
Number17
CountryFrance
CityGrenoble
Period02/06/201504/06/2015
OtherHeld as Part of the 10th International Federated Conference on Distributed Computing Techniques, DisCoTec 2015
Internet address
SeriesLecture Notes in Computer Science
Volume9037
ISSN0302-9743

Fingerprint Dive into the research topics of 'A Fixpoint-Based Calculus for Graph-Shaped Computational Fields'. Together they form a unique fingerprint.

Cite this