Asynchronous Distributed Execution of Fixpoint-Based Computational Fields

Research output: Contribution to journalJournal article – Annual report year: 2018Researchpeer-review

Documents

DOI

View graph of relations

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 µ-calculuslike 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.
Original languageEnglish
JournalLogical Methods in Computer Science
Volume13
Issue number1
Number of pages47
ISSN1860-5974
DOIs
Publication statusPublished - 2017
CitationsWeb of Science® Times Cited: No match on DOI

    Research areas

  • Distributed computing, Computational fields, Distributed graph algorithms, Coordination, Modal logics

Download statistics

No data available

ID: 127329959