Programming Distributed Collective Processes for Dynamic Ensembles and Collective Tasks

Programming Distributed Collective Processes for Dynamic Ensembles and Collective Tasks Giorgio Audrito1 , Roberto Casadei2 , Ferruccio Damiani1 , Gianluca Torta1 , Mirko Viroli2 1 Università degli Studi di Torino 2 ALMA MATER STUDIORUM – Università of Bologna June 21st, 2023 COORDINATION’23, Lisbon, Portugal https://www.slideshare.net/RobertoCasadei R. Casadei Motivation Background Contribution Wrap-up References 1/18

Outline 1 Motivation 2 Background 3 Contribution 4 Wrap-up

Motivation: macro-programming [2] collective systems Target systems: distributed networks of devices (cf. IoT, swarms, edge-fog-cloud) Target computations: collective computations (progressive, cooperative) [1] Approach: macro-programming (a single program for the whole behaviour) [1] R. Casadei, M. Viroli, G. Audrito, D. Pianini, and F. Damiani, “Engineering collective intelligence at the edge with aggregate processes,” Engineering Applications of Artificial Intelligence, 2021 [2] R. Casadei, “Macroprogramming: Concepts, state of the art, and opportunities of macroscopic behaviour modelling,” ACM Computing Surveys, Jan. 2023 R. Casadei Motivation Background Contribution Wrap-up References 2/18

Macroprogramming collective systems – e.g.: swarms R. Casadei Motivation Background Contribution Wrap-up References 3/18

Macroprogramming collective systems – e.g.: swarms move in flocking formation R. Casadei Motivation Background Contribution Wrap-up References 3/18

Macroprogramming collective systems – e.g.: swarms move in flocking formation ...while also, dynamically... R. Casadei Motivation Background Contribution Wrap-up References 3/18

Macroprogramming collective systems – e.g.: swarms move in flocking formation ...while also, dynamically... detect or estimate something R. Casadei Motivation Background Contribution Wrap-up References 3/18

Macroprogramming collective systems – e.g.: swarms move in flocking formation ...while also, dynamically... detect or estimate something elect leader R. Casadei Motivation Background Contribution Wrap-up References 3/18

Macroprogramming collective systems – e.g.: swarms move in flocking formation ...while also, dynamically... detect or estimate something elect leader organise teams for missions departing from the flock R. Casadei Motivation Background Contribution Wrap-up References 3/18

Background: the eXchange Calculus (XC) [3] System model (modellable as an event structure) network of devices working at asynchronous rounds and interacting with neighbours each round: sense – compute – (inter-)act the program maps local data to outputs and data to be shared with neighbours 1 1 1 2 1 3 2 1 2 2 2 3 2 4 2 5 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4 4 5 4 6 5 1 5 2 5 3 Devices Time [3] G. Audrito, R. Casadei, F. Damiani, G. Salvaneschi, and M. Viroli, “Functional programming for distributed systems with XC,” in ECOOP 2022, ser. LIPIcs, Schloss Dagstuhl, 2022 R. Casadei Motivation Background Contribution Wrap-up References 4/18

Background: the eXchange Calculus (XC) [3] eXchange Calculus (XC): the language A functional language (λ-calculus) + 3 key elements: 1. neighbouring values (nvalues): default + (optional) neighbour-specific data 2. a single construct for communication: exchange 3. alignment: interaction is scoped by individual behavioural modules, enabling compositionality [3] G. Audrito, R. Casadei, F. Damiani, G. Salvaneschi, and M. Viroli, “Functional programming for distributed systems with XC,” in ECOOP 2022, ser. LIPIcs, Schloss Dagstuhl, 2022 R. Casadei Motivation Background Contribution Wrap-up References 5/18

XC: neighbouring values (NValues) Neighbouring values: what collection of sent/received messages handle neighbours collectively, not individually ℓ[δ1 7→ ℓ1, . . .] default msg ℓ1 custom msg to/from δ1 Combining and summarising NValues: examples Pointwise map 2[δ1 7→ 3, δ2 7→ 1] + 20[δ1 7→ 10] = 22[δ1 7→ 13, δ2 7→ 21] Fold (in δ1) over neighbours (δ2, δ3) nfold(max, 22[δ1 7→ 13, δ2 7→ 21], 0) = max(0, 21, 22) = 22 R. Casadei Motivation Background Contribution Wrap-up References 6/18

XC: sharing via exchange (1/2) exchange: a single primitive for state management and bidirectional communication exchange(ei, (n) = return er send es) exchange exchange exchange exchange n ei . . . program. . . er es

XC: sharing via exchange (2/2) Example: distanceTo (a.k.a. gradient) 1 def distanceTo(src) { // has type scheme: (bool) → num 2 exchange(∞, (n) = retsend mux(src, 0, distanceEstimate(n)) ) 3 } 1 1 0 1 2 2 3 3 1

XC: composition and alignment a program evaluation yields a sort of tree of exchanges different exchanges −→ separate messages alignment means that data is exchanged only between corresponding nodes in the tree i.e. match by: • position in program • stack trace −→ enables composition XC program tree distanceInServiceProvisioning distanceTo distanceTo if/else distanceEstimate exchange nfold distanceEstimate exchange nfold δ1 δ2 δ3 devices time partial alignment of expressions R. Casadei Motivation Background Contribution Wrap-up References 9/18

XC: example ⊥ ⊥ ⊥ ⊥ ⊥ channel = 3 3 3 3 3 3 3 3 3 + 5 4 4 3 4 3 3 5 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 width + broadcast 1 1 1 1 2 2 3 3 0 4 3 3 2 2 1 0 2 3 distanceTo distanceTo ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ src ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ dest R. Casadei Motivation Background Contribution Wrap-up References 10/18

Proposed abstraction: distributed collective process What do we mean for a (distributed collective) process? R. Casadei Motivation Background Contribution Wrap-up References 11/18

Proposed abstraction: distributed collective process What do we mean for a (distributed collective) process? • generative a process is an activity that can be spawned locally in a given round (generative) R. Casadei Motivation Background Contribution Wrap-up References 11/18

Proposed abstraction: distributed collective process What do we mean for a (distributed collective) process? • generative • dynamic domain a process is an activity that may spread to neighbours, expanding its range (dynamic domain) R. Casadei Motivation Background Contribution Wrap-up References 11/18

Proposed abstraction: distributed collective process What do we mean for a (distributed collective) process? • generative • dynamic domain • concurrent processes may overlap (concurrency) R. Casadei Motivation Background Contribution Wrap-up References 11/18

Proposed abstraction: distributed collective process What do we mean for a (distributed collective) process? • generative • dynamic domain • concurrent • collective activity any process defines both how the domain evolves and the collective activity carried out within that evolving domain e.g., in a smart city: red: resource recruitment process green: monitoring process blue: access control process R. Casadei Motivation Background Contribution Wrap-up References 11/18

Proposed abstraction: distributed collective process What do we mean for a (distributed collective) process? • generative • controllable, dynamic domain • concurrent • collective activity device may quit processes, making them shrink and finally terminate (transience), while other processes may go on indefinitely (long-running) R. Casadei Motivation Background Contribution Wrap-up References 11/18

Distributed Collective Processes (DCP): elements We distinguish a DCP type P from its running instances Pi R. Casadei Motivation Background Contribution Wrap-up References 12/18

Distributed Collective Processes (DCP): elements We distinguish a DCP type P from its running instances Pi Elements of a process instance Process ID (PID): identifies the instance, and also holds init data Domain: the set of devices running it Local result: a pair (local output, status) ∠ status: an NValue mapping neighbours to a Boolean (to control process expansion!) true: the neighbour will receive the process false: the neighbour won’t be involved in the process R. Casadei Motivation Background Contribution Wrap-up References 12/18

Distributed Collective Processes (DCP): elements We distinguish a DCP type P from its running instances Pi Elements of a process instance Process ID (PID): identifies the instance, and also holds init data Domain: the set of devices running it Local result: a pair (local output, status) ∠ status: an NValue mapping neighbours to a Boolean (to control process expansion!) true: the neighbour will receive the process false: the neighbour won’t be involved in the process Defining process types Generator expression GP : returns a (possibly empty) set of PIDs Process logic P: the (complex) expression producing the output-state pair R. Casadei Motivation Background Contribution Wrap-up References 12/18

Distributed Collective Processes (DCP): spawning Spawning processes spawnXC (P, GP ) where spawnXC is a new XC primitive responsible of managing execution of a sets of processes of the same type ( big-step opsem in the paper) P is a function expressing the process logic GP is the generation set of PIDs R. Casadei Motivation Background Contribution Wrap-up References 13/18

Distributed Collective Processes (DCP): spawning Spawning processes spawnXC (P, GP ) where spawnXC is a new XC primitive responsible of managing execution of a sets of processes of the same type ( big-step opsem in the paper) P is a function expressing the process logic GP is the generation set of PIDs Example: resource look-up via limited multi-gradient Goal: get IDs of devices (in the surrounding) offering a set of desired resources GP : for each resource request, yield a PID of form (sourceId, reqId, maxDist, {R1 : qty1, ..., Rn : qtyn}) P.status = ( distanceTo(sourceId) ≤ maxDist ∨ ¬(isSource ∧ done) ⊥ otherwise P.logic: collect map of pairs (devId, {Ri}) into source R. Casadei Motivation Background Contribution Wrap-up References 13/18

Proof-of-Concept Implementation FCPP implementation [4] 1 template .... 2 std::unordered_mapK, R 3 spawn(node_t node, trace_t call_point, 4 G process, S key_set, Ts const... xs) time aproc tvar = 10, dens = 10, hops = 20, speed = 0 0 5 10 15 20 25 30 35 40 45 50 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 spherical (xc) ∠ multiple wave-like propagations ∠ aproc: average number of active process instances Scala implementation [5] 1 def spawn[K,A,R](process: K = A = (R,Boolean), 2 newKeys: Set[K], 3 args: A): Map[K,R] [4] G. Audrito, “FCPP: an efficient and extensible field calculus framework,” in International Conference on Autonomic Computing and Self-Organizing Systems (ACSOS), IEEE, 2020 [5] R. Casadei, M. Viroli, G. Aguzzi, and D. Pianini, “Scafi: A scala DSL and toolkit for aggregate programming,” SoftwareX, 2022 R. Casadei Motivation Background Contribution Wrap-up References 14/18

Conclusion A distributed collective process abstraction, formalised in the eXchange Calculus (XC) R. Casadei Motivation Background Contribution Wrap-up References 15/18

Conclusion A distributed collective process abstraction, formalised in the eXchange Calculus (XC) Generalisation over earlier work ∠ implementation in field calculus R. Casadei, M. Viroli, G. Audrito, D. Pianini, and F. Damiani, “Aggregate processes in field calculus,” in COORDINATION 2019, ser. LNCS, Springer, 2019 ∠ an investigation of different domain evolution techniques G. Audrito, R. Casadei, and G. Torta, “On the dynamic evolution of distributed computational aggregates,” in ACSOS-C 2022, IEEE, 2022 R. Casadei Motivation Background Contribution Wrap-up References 15/18

Conclusion A distributed collective process abstraction, formalised in the eXchange Calculus (XC) Generalisation over earlier work ∠ implementation in field calculus R. Casadei, M. Viroli, G. Audrito, D. Pianini, and F. Damiani, “Aggregate processes in field calculus,” in COORDINATION 2019, ser. LNCS, Springer, 2019 ∠ an investigation of different domain evolution techniques G. Audrito, R. Casadei, and G. Torta, “On the dynamic evolution of distributed computational aggregates,” in ACSOS-C 2022, IEEE, 2022 Support for programming collective adaptive / self-organising behaviour ∠ space-based coordination – e.g. situated tuples R. Casadei, M. Viroli, A. Ricci, and G. Audrito, “Tuple-based coordination in large-scale situated systems,” in COORDINATION 2021, ser. LNCS, Springer, 2021 ∠ self-organising structures – e.g. SCR (Self-organising Coordination Regions) pattern R. Casadei, D. Pianini, M. Viroli, and A. Natali, “Self-organising coordination regions: A pattern for edge computing,” in COORDINATION 2019, ser. LNCS, Springer, 2019 ∠ definition of dynamic ensembles ∠ epidemic processes others (future work) R. Casadei Motivation Background Contribution Wrap-up References 15/18

Thanks! time aproc tvar = 10, dens = 10, hops = 20, speed = 0 0 5 10 15 20 25 30 35 40 45 50 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 spherical (xc) ⊥ ⊥ ⊥ ⊥ ⊥ channel = 3 3 3 3 3 3 3 3 3 + 5 4 4 3 4 3 3 5 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 width + broadcast 1 1 1 1 2 2 3 3 0 4 3 3 2 2 1 0 2 3 distanceTo distanceTo ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ src ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ dest ℓ[δ1 7→ ℓ1, . . .] default msg ℓ1 custom msg to/from δ1 1 def spawn[K,A,R](process: K = A = (R,Boolean), 2 newKeys: Set[K], 3 args: A): Map[K,R] R. Casadei Motivation Background Contribution Wrap-up References 16/18

References (1/2) [1] R. Casadei, M. Viroli, G. Audrito, D. Pianini, and F. Damiani, “Engineering collective intelligence at the edge with aggregate processes,” Engineering Applications of Artificial Intelligence, vol. 97, p. 104 081, 2021. [2] R. Casadei, “Macroprogramming: Concepts, state of the art, and opportunities of macroscopic behaviour modelling,” ACM Computing Surveys, Jan. 2023. DOI: 10.1145/3579353. [Online]. Available: https://doi.org/10.1145/3579353. [3] G. Audrito, R. Casadei, F. Damiani, G. Salvaneschi, and M. Viroli, “Functional programming for distributed systems with XC,” in ECOOP 2022, ser. LIPIcs, vol. 222, Schloss Dagstuhl, 2022, 20:1–20:28. DOI: 10.4230/LIPIcs.ECOOP.2022.20. [4] G. Audrito, “FCPP: an efficient and extensible field calculus framework,” in International Conference on Autonomic Computing and Self-Organizing Systems (ACSOS), IEEE, 2020, pp. 153–159. DOI: 10.1109/ACSOS49614.2020.00037. [5] R. Casadei, M. Viroli, G. Aguzzi, and D. Pianini, “Scafi: A scala DSL and toolkit for aggregate programming,” SoftwareX, vol. 20, p. 101 248, 2022. DOI: 10.1016/j.softx.2022.101248. [Online]. Available: https://doi.org/10.1016/j.softx.2022.101248. [6] R. Casadei, M. Viroli, G. Audrito, D. Pianini, and F. Damiani, “Aggregate processes in field calculus,” in COORDINATION 2019, ser. LNCS, vol. 11533, Springer, 2019, pp. 200–217. DOI: 10.1007/978-3-030-22397-7_12. [Online]. Available: https://doi.org/10.1007/978-3-030-22397-7_12. R. Casadei Motivation Background Contribution Wrap-up References 17/18

References (2/2) [7] G. Audrito, R. Casadei, and G. Torta, “On the dynamic evolution of distributed computational aggregates,” in ACSOS-C 2022, IEEE, 2022, pp. 37–42. DOI: 10.1109/ACSOSC56246.2022.00024. [8] R. Casadei, M. Viroli, A. Ricci, and G. Audrito, “Tuple-based coordination in large-scale situated systems,” in COORDINATION 2021, ser. LNCS, vol. 12717, Springer, 2021, pp. 149–167. DOI: 10.1007/978-3-030-78142-2_10. [9] R. Casadei, D. Pianini, M. Viroli, and A. Natali, “Self-organising coordination regions: A pattern for edge computing,” in COORDINATION 2019, ser. LNCS, vol. 11533, Springer, 2019, pp. 182–199. DOI: 10.1007/978-3-030-22397-7_11. R. Casadei Motivation Background Contribution Wrap-up References 18/18

Programming Distributed Collective Processes for Dynamic Ensembles and Collective Tasks

More Related Content

Similar to Programming Distributed Collective Processes for Dynamic Ensembles and Collective Tasks

More from Roberto Casadei

Recently uploaded

Programming Distributed Collective Processes for Dynamic Ensembles and Collective Tasks