Lafuente, Alberto Lluch and Loreti, Michele and Montanari, Ugo - Asynchronous Distributed Execution Of Fixpoint-Based Computational Fields

lmcs:3212 - Logical Methods in Computer Science, March 22, 2017, Volume 13, Issue 1
Asynchronous Distributed Execution Of Fixpoint-Based Computational Fields

Authors: Lafuente, Alberto Lluch and Loreti, Michele and Montanari, Ugo

Coordination is essential for dynamic distributed systems whose components exhibit interactive and autonomous behaviors. Spatially distributed, locally interacting, propagating computational fields are particularly appealing for allowing components to join and leave with little or no overhead. Computational fields are a key ingredient of aggregate programming, a promising software engineering methodology particularly relevant for the Internet of Things. In our approach, space topology is represented by a fixed graph-shaped field, namely a network with attributes on both nodes and arcs, where arcs represent interaction capabilities between nodes. We propose a SMuC calculus where mu-calculus- like modal formulas represent how the values stored in neighbor nodes should be combined to update the present node. Fixpoint operations can be understood globally as recursive definitions, or locally as asynchronous converging propagation processes. We present a distributed implementation of our calculus. The translation is first done mapping SMuC programs into normal form, purely iterative programs and then into distributed programs. Some key results are presented that show convergence of fixpoint computations under fair asynchrony and under reinitialization of nodes. The first result allows nodes to proceed at different speeds, while the second one provides robustness against certain kinds of failure. 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 recovery strategy.


Source : oai:arXiv.org:1610.00253
DOI : 10.23638/LMCS-13(1:13)2017
Volume: Volume 13, Issue 1
Published on: March 22, 2017
Submitted on: March 22, 2017
Keywords: Computer Science - Logic in Computer Science,C.2.4,D.1.3,F.1.2


Share

Consultation statistics

This page has been seen 617 times.
This article's PDF has been downloaded 101 times.