Asynchronous Distributed Execution Of Fixpoint-Based Computational Fields
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. Compu...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2017-03-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/3212/pdf |
| _version_ | 1797268641507442688 |
|---|---|
| author | Alberto Lluch Lafuente Michele Loreti Ugo Montanari |
| author_facet | Alberto Lluch Lafuente Michele Loreti Ugo Montanari |
| author_sort | Alberto Lluch Lafuente |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:35:43Z |
| format | Article |
| id | doaj.art-8c77370e08eb4dd3b76cb998ebc62980 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:43Z |
| publishDate | 2017-03-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-8c77370e08eb4dd3b76cb998ebc629802024-03-08T09:49:43ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742017-03-01Volume 13, Issue 110.23638/LMCS-13(1:13)20173212Asynchronous Distributed Execution Of Fixpoint-Based Computational FieldsAlberto Lluch Lafuentehttps://orcid.org/0000-0001-7405-0818Michele LoretiUgo MontanariCoordination 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.https://lmcs.episciences.org/3212/pdfcomputer science - logic in computer sciencec.2.4d.1.3f.1.2 |
| spellingShingle | Alberto Lluch Lafuente Michele Loreti Ugo Montanari Asynchronous Distributed Execution Of Fixpoint-Based Computational Fields Logical Methods in Computer Science computer science - logic in computer science c.2.4 d.1.3 f.1.2 |
| title | Asynchronous Distributed Execution Of Fixpoint-Based Computational Fields |
| title_full | Asynchronous Distributed Execution Of Fixpoint-Based Computational Fields |
| title_fullStr | Asynchronous Distributed Execution Of Fixpoint-Based Computational Fields |
| title_full_unstemmed | Asynchronous Distributed Execution Of Fixpoint-Based Computational Fields |
| title_short | Asynchronous Distributed Execution Of Fixpoint-Based Computational Fields |
| title_sort | asynchronous distributed execution of fixpoint based computational fields |
| topic | computer science - logic in computer science c.2.4 d.1.3 f.1.2 |
| url | https://lmcs.episciences.org/3212/pdf |
| work_keys_str_mv | AT albertolluchlafuente asynchronousdistributedexecutionoffixpointbasedcomputationalfields AT micheleloreti asynchronousdistributedexecutionoffixpointbasedcomputationalfields AT ugomontanari asynchronousdistributedexecutionoffixpointbasedcomputationalfields |