Skip to Main content Skip to Navigation
Conference papers

A Fixpoint-Based Calculus for Graph-Shaped Computational Fields

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-flow 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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01774933
Contributor : Hal Ifip <>
Submitted on : Tuesday, April 24, 2018 - 10:53:46 AM
Last modification on : Tuesday, February 26, 2019 - 10:54:02 AM
Long-term archiving on: : Wednesday, September 19, 2018 - 12:53:11 PM

File

978-3-319-19282-6_7_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Alberto Lafuente, Michele Loreti, Ugo Montanari. A Fixpoint-Based Calculus for Graph-Shaped Computational Fields. 17th International Conference on Coordination Languages and Models (COORDINATION), Jun 2015, Grenoble, France. pp.101-116, ⟨10.1007/978-3-319-19282-6_7⟩. ⟨hal-01774933⟩

Share

Metrics

Record views

292

Files downloads

185