Deck 11 frames the target: "we target 'complex adaptive systems' (CASs), which are complex and large-scale — we need good abstractions, possibly platform-independent — rule-based languages (automaton-based) hardly scale with system complexity". The setting is the Internet of Things: "increasing availability of wearable / mobile / embedded / flying devices", "heterogeneous wireless connectivity", "computational resources (device/edge/cloud)", "production/analysis of data, everywhere, anytime". The canonical application is crowd evacuation upon alerts: a crowd of devices that must collectively react to an emergency. The claim of the deck: rule-based, automaton-based programming does not scale to systems of this kind — the same wall that motivated transition systems and Petri Nets in chapter 9.
The research direction is aggregate computing: "a research thread to address these problems is 'macro/collective-programming'"; "aggregate computing proposes to see collective behaviour declaratively"; "key abstraction: computational fields as sort 'spatial streams'"; "key abstraction: functional manipulation of computational fields"; "an expressive toolchain (Scafi) exists grounded on Scala(/Akka)"; "resiliency is guaranteed with a well-crafted library of reusable 'bricks'". The scientific network spans UNIBO, UNITO, UNIMORE, UNICAL, UNIBZ, BBN Technologies, Iowa University, St. Gallen, Saint Andrews, TU Wien, KU Leuven, Aarhus — a full research community around the idea.
The deck's way in is the Spark analogy: in Big Data style, one Scala specification over an RDD (map, map, reduce) runs unchanged on local[8] or on a Spark standalone cluster — "one specification can be adapted to different platforms". Aggregate computing wants the same property for spatial computation: specify the aggregate behaviour once, run it on any device infrastructure.
The informal requirements are worth reading slowly, because they are the acceptance criteria of the whole chapter:
The abstract execution platform that satisfies them: "assume an abstract notion of actor, executing locally; an 'aggregate specification' generates local aggregate actors (AA); the set of AAs transparently carries on the collective behaviour; local actors interact with the AAs for sensing/actuation". The deck closes the loop with the rest of the course: "Alchemist DSLs and DAP could be programs for AAs" — the simulator of chapter 12 and the DAP meta-model of chapter 9 are execution platforms for the same aggregate programs.
The manifesto of the lecture is a motto and three points:
"Program the aggregate, not individual devices! 1. The reference computing machine: an aggregate of devices as single 'body', fading to the actual space. 2. The reference elaboration process: atomic manipulation of a collective data structure (a so-called field). 3. The actual networked computation: a proximity-based self-organisation system hidden 'under-the-hood'."
Three shifts in one sentence: the unit of computation is no longer a device but the aggregate; the unit of data is no longer a value but a field; the network — which devices talk to which (device and neighborhood are the two structural notions) — is somebody else's problem.
Computational fields, in their traditional static view, are "a map: Space → Values": "possibly evolving over time, dynamically injected, stabilising; smoothly adapting to very heterogeneous domains; more easily 'understood' on continuous and flat spatial domains; ranging over: booleans, reals, vectors, functions, tensors". The deck's examples: a boolean channel in 2D, a numeric partition in 2D, a real-valued gradient in 3D. What unifies them: a value per location, as opposed to a value per device program state.
The static map is not enough: devices fire at different times, move, reboot. The dynamic reading defines a field as a space-time structure:
ϕ : D → V (a field as a function from events to values)Two consequences follow: "computation abstracts from/adapts to the underlying event" and "scheduling of events is essentially exogenous" — the program never says when a device computes; the platform decides. This is the exact counterpart of the asynchronous-rounds requirement of section 7, and of the exogenous scheduling of Alchemist in chapter 12.
The deck pictures the field as an event structure: each device δi produces a timeline of values vij, with a "self-message" carrying the previous value and occasional "reboot" gaps. On top of that picture sits an implicit notion of computability, the Cone Turing Machine: "full computability is the ability at a node to expose a value obtained with full power from nodes in the cone of past events" — the past cone of a device contains everything that happened before, anywhere, that could have causally reached it. A field computation is thus not a "distributed approximation": it is as expressive as a Turing machine, but space-time aware.
The programming model is "a sort of λ-calculus with 'everything is a field' philosophy!" The syntax (slightly refactored from the papers):
e ::= x | v | e(e₁, ..., eₙ) | rep(e₀){e} | nbr{e} (expr)
v ::= <standard-values> | λ (value)
λ ::= f o (x)=>e (functional value)
F ::= def f(x) {e} (function definition)v includes numbers, booleans, strings, "..tuples/vectors/maps/any-ADT (of expressions)";f is a user-defined function — "the key aggregate computing abstraction";o is a built-in local operator — "pure math, local sensors,..".Four constructs, four intuitions (the global-level, denotational semantics):
v — "a field constant in space and time, mapping any event to v";e(e₁, ..., eₙ) — "e evaluates to a field of functions, assume it ranges to λ₁, ..., λₙ; this naturally induces a partition of the domain D₁, ..., Dₙ; now, join the fields: ∀i, λᵢ(e₁, ..., eₙ) restricted in Dᵢ" — the restriction mechanism that will make branch possible;rep(e₀){eλ} — "the value of e₀ where the restricted domain 'begins'; elsewhere, unary function eλ is applied to previous value at each device" — time embeds state;nbr{e} — "at each event gathers most recent value of e in neighbours (in restriction)... what is neighbour is orthogonal (i.e., physical proximity)".The restriction trick deserves attention: branch(e-bool){e-then}else{e-else} is "a space-time branching construct" equivalent to (e-bool ? ()=>{e-then} : ()=>{e-else})() — the boolean field partitions the domain, and each branch evaluates only within its region. "More advanced patterns: spread code, in different versions in different regions; have different regions/devices run different programs."
The deck's mini-tutorial teaches the four constructs by example — 17 expressions, each doing something spatial or temporal. Read them as a graduated exercise (the widget below quizzes them):
1: 1
2: 2 + 3
3: pair(10, 20)
4: random()
5: sense(1)
6: sense(1) ? 10 : 20
7: mid()
8: minHood(nbrRange)
9: rep(0){ (x) => x + 1 }
10: rep(random()){ (x) => x }
11: rep(0){ (x) => x + rep(random()){ (y) => y } }
12: maxHood( nbr{ sense(1) } )
13: sumHood( nbr{ 1 } )
14: rep(0){ (x) => max( sense(1), maxHood( nbr{ x } ) ) }
15: rep(Infinity) { (d) => sense(1) ? 0 : minHood( nbr{d} + 1 ) }
16: rep(Infinity) { (d) => sense(1) ? 0 : minHood( nbr{d} + nbrRange ) }
17: branch(sense(2)){Infinity}{ rep(Infinity) { (d) => sense(1) ? 0 : minHood( nbr{d} + nbrRange ) }}Line 8 is the distance to the nearest neighbour; line 9 is a per-device counter; lines 14–16 are the key trio: 14 gossips the maximum sensor value over the network (with maxHood folding the neighbour field), 15 computes a hop-count gradient from the source where sense(1) is true, 16 the same with physical distances (nbrRange), and 17 restricts the gradient to the region where sense(2) is false — the space-time branching of section 4. These three lines are the seed of everything in the rest of the chapter.
ScaFi is the Scala incarnation: "a Scala DSL to mimic the field calculus" with "an actor system, a JavaFX simulator, an Alchemist incarnation, ScafiWeb". The core API is a trait of seven constructs:
trait Constructs {
// the unique identifier of the local device
def mid(): ID
// applies fun to the previous result, or to init at first call
def rep[A](init: A)(fun: (A) => A): A
// evaluation of expr at the currently-considered neighbour
def nbr[A](expr: => A): A
// accumulates available evaluations of expr, with acc / init monoid
def foldhood[A](init: => A)(acc: (A, A) => A)(expr: => A): A
// splits computation: th where cond is true, el everywhere/time else
def branch[A](cond: => Boolean)(th: => A)(el: => A): A
// perception of local sensor
def sense[A](name: LSNS): A
// perception of neighbourhood sensor
def nbrvar[A](name: NSNS): A
...
}Note how rep is "the previous result" (time), nbr is "the currently-considered neighbour" (space), foldhood collapses a neighbour field with a monoid (min, max, sum, Set union), and sense/nbrvar read local and neighbourhood sensors. In ScaFi the mini-tutorial becomes Scala: minHood(nbrRange), rep(0){ x => x + 1 }, the gradient rep(Infinity){ d => sense(1) ? 0 : minHood(nbr{d} + nbrRange) }, and so on.
Is the language expressive enough for real applications? The lecture's answer is a composition exercise: build a channel — the region of space between a source and a destination with a given width — purely by functional composition of reusable fields. The building blocks:
def gradient(source) { ;; reifying minimum distance from source
rep(Infinity) { ;; distance is infinity initially
(distance) => source ? 0 : minHood( nbr{distance} + nbrRange )
}
}
def distance(source, dest) { ;; minimum distance between source and dest
snd( ;; returning the second component of the pair
rep(pair(Infinity, Infinity)) { ;; a field of pairs (distance, value)
(distanceValue) => source ? pair(0, gradient(dest)) :
minHood( ;; propagating as a gradient, first component
pair(fst(nbr{distanceValue}) + nbrRange, snd(nbr{distanceValue})))
} ) )
}
def dilate(region, width) { ;; a field of booleans
gradient(region) < width
}
;; Here the "aggregate" nature of our approach gets revealed
def channel(source, dest, width) {
dilate( gradient(source) + gradient(dest) <= distance(source,dest), width )
}Read the channel: gradient(source) + gradient(dest) is the sum of the two distance fields — an ellipse-like scalar field; distance(source,dest) is the geodesic distance between the two; the inequality selects the points where the sum of the distances is within the true distance (an ellipse with foci source and dest), and dilate thickens it by width. The built-in vocabulary: the ternary ?:, nbrRange (neighbour field of estimated distances), minHood/sumHood (collapse a neighbour field), pointwise math, and pair/fst/snd.
The second example is crowd evacuation — the application of section 1 — again by composition:
def broadcast(source, v) { ;; propagate value v outward from source
snd( rep(pair(Infinity, v)) {
(distanceValue) => source ? pair(0, distance-to(v)) :
minHood( pair(fst(nbr{distanceValue}) + nbrRange, snd(nbr{distanceValue}))) } ) }
def collect-or(potential, value) { ;; collect 'value' by descending 'potential', by 'or'
rep(value) {
(v) => anyHood( nbr{ find-parent potential() = uid ? nbr{v} : false } ) or value
} }
def evacuation-alert(zone, coordinator, alert) {
distance-to(
if (zone) { false } else {
broadcast(coordinator, collect-or(distance-to(coordinator), alert)) }) }The pattern is the same at every level: a few well-chosen reusable functions (gradient, distance-to, broadcast, collect-or) compose into an application-level behaviour (evacuation alerts propagate out of the danger zone but not into it, coordinated by a coordinator device). This is "reusing and composing global-level, aggregate specs" — the compositionality requirement of section 1 fulfilled in code.
gradient, distance, dilate — are composed with pointwise arithmetic and comparison into a boolean field selecting the corridor between source and destination. The same construction style scales to crowd evacuation.How does a single device execute a field program? The network model: "a node state θ (value-tree) updated at asynchronous rounds; at the end of the round, θ is made accessible to the neighbourhood; a node state is updated 'against' recently received neighbours' trees". The evaluation of an expression produces not just a value but a tree — the evaluation tree — which is exactly what is shipped to neighbours ("nodes send their evaluation tree to neighbours at the end of each computation round"). The value of nbr{e} at a device is found by matching the corresponding subtree in the incoming neighbour trees.
The core mechanisms of the operational semantics:
e(e₁, ..., eₙ): "evaluates body against a filtered set of neighbours... i.e., only those which evaluated e to same result" — the operational reading of the denotational partition of section 4;This is the blueprint for platform support. The requirements on any platform are minimal: "a notion of neighbourhood must be defined — wireless connectivity, physical proximity..; nodes execute in asynchronous rounds, and emit a 'round result'; a node needs recent round results of neighbours". And crucially: "by construction we tolerate losses of messages; by construction we tolerate various round frequencies. Platform details are very orthogonal to our programming model! the above requirements can be met by various platforms; programming remains mostly unaltered!" — this is the Spark promise of section 1, delivered at the level of the execution semantics. Alchemist's Scafi incarnation (chapter 12, section 10) is exactly such a platform: a discrete-event engine that decides when each device fires a round.
Is the field calculus expressive enough? The deck's answer is strong: "Practically, we can express: complex spreading / aggregation / decay functions; spatial leader election, partitioning, consensus; distributed spatio-temporal sensing; splitting in parallel independent subprocesses; dynamic deployment/spreading of code (via lambda); implicit/explicit device selection of what code execute; 'collective teams' forming based on the selected code — actually, it is 'space-time' universal!"
But expressiveness is not engineering. The deck organises the engineering stack in layers: application code (e.g. Crowd Management) on top of API-level building blocks (Perception: summarize, average, regionMax; Action: distanceTo, broadcast, partition; State: timer, lowpass, recentTrue), on top of the resilient coordination operators G, C, T, on top of the field calculus constructs (nbr, rep, restriction, sensors, actuators). The GCT combinator set is the deck's answer to "how to engineer complex apps out of basic constructs":
def distance(source) { G(source, 0, ()=>nbrRange(), (x)=>x+nbrRange()) }
def broadcast(source, v) { G(source, v, ()=>nbrRange(), (x)=>x) }
def sum(source, field) { broadcast(source, C(source, distance(source), +, 0)) }
def timer(timeout) { T(timeout, 0, (t)=>t-dt()) == 0 }Everything in the previous section is a specialisation: the gradient is G with a summing en-route function, broadcast is G with identity, sum is a C collected towards the source and then broadcast back, the timer is a T counting down. The deck's crowd service shows the API layer on top of GCT — a crowd estimation service after Fruin (1971), whose pedestrian level-of-service thresholds (LoS) enter the code directly:
;; Density Estimation: density of neighbours within a short 3.0 mt range
def densityEstimation() {
countHood(nbrRange < 3.0) / (3.0 * 3.0 * 3.14)
}
;; More than 2.17 density and 'threshold' overcame in a 'partition' region
def dangerousDensity(partition, threshold) {
average(partition, densityEstimation()) > 2.17 ;; Fruin LoS
&& count(partition) > threshold ;; and many people...
}
;; Crowd levels: Level 1 (low): density > 1.08 in the last 60 seconds
;; Level 2 (high): in a 30mt-range partition, L1 > 300 with density > 2.18
;; Level 0 (none): others
def crowdTracking() {
if (recentlyTrue(densityEstimation() > 1.08, 60) { ;; note restriction here..
dangerousDensity(randomPartition(30), 300) ? high : low
} else { none }
}"Resilience: the ability to adapt well in the face of adversity." In aggregate computing: "the ability of a functional component to properly work in the face of changes to inputs and environment". The deck splits it in two — and this distinction is one of the most examinable ideas of the chapter:
(Other notions are left for future work: "resilience to change of computational infrastructure, to varying requirements on computational load, to malicious attacks".)
Self-stabilisation for computational fields [SASO 2015]: "given an environment (inputs: sensor fields, and network topology), computing e results in a stable unique field in finite time". The implications are deep: "after fixing a topology, a field computation is an I/O space problem; occasional env. changes do not affect the result of computation; we can somehow get rid of time and evolution in design". The lecture adds the honest theoretical note: "self-stabilisation is undecidable, but can identify sufficient conditions" — and the GCT set is a set of sufficient conditions: G, C and T "always guaranteeing self-stabilisation". The gradient widget of section 5 demonstrates it: remove a source, add a source, the field reconverges to the unique stable field in a finite number of rounds.
Controlling dynamics is "a very hard problem in general": "how is self-stabilisation reached? sometimes we need this to happen quickly; sometimes we need this to happen smoothly". The state of research: "no formal understanding of the entire problem; A – proposed substituted GCT for ad-hoc situations; B – proposed meta-techniques to improve self-stabilisation". The bad news example: dilate under ongoing changes — the field keeps shifting and never settles; and the deck's test: "(impact of a malicious change in the code)".
The methodological workflow [SASO 2015] operationalises the substitution idea: the GCT set is "conceived to be very general"; "specialised and optimised replacements of G, C and T can be designed — one just needs to check they are I/O-equivalent"; "selectively using them can improve overall performance". The pipeline: Self-Organising System Specification → Decompose into Building Blocks (a "Building Block Library") → Minimal Resilient Implementation → Substitution Library → Optimise by substitution → Optimised Implementation. Three specialised alternatives from the literature:
The evacuation scenario is the evaluation: "global error in reacting to an alert, with different GCT sets" — G′C′T′-based crowd evacuation measurably reduces the reaction error. The line of work continues in the emerge testbed and Macro Swarm (scafi.github.io/macro-swarm).
The lab deck (11-Lab) sums up: "AC: everything is a computational field, manipulated functionally (as in pure FP); execution is delegated to the platform, transparently deciding on sensors, neighbours, scheduling; as executor we mostly play with a simulator. Field calculus: functional composition + rep (to deal with time) + nbr (to deal with space). ScaFi: Scala incarnation, largely used in many applications, also integrates with Alchemist, RL, ..."
asmd-public-scafi from Virtuale; import it in IntelliJ as an SBT project; also play with the examples of ScafiWeb (scafi.github.io/web). Run the built-in examples and the simulator.Builtins.Bounded.*; propagate a pair (distance, source's mid) as in case 8; "fortunately minHoodPlus already works for pairs"; then "just project on the second component and activate multiple sources, and you have your partitions, each labelled by a different ID" — and synthesise a reusable partition function.broadcast ("just a variation of partition: inputs source field, input field; output: the result of broadcasting input field outward sources") → block distance ("achieved by broadcast the result of gradient at destination") → the channel of section 6.| Task | What it asks |
|---|---|
| RESILIENT-GOSSIP | Case 14's warning is the seed: a naive maxHood gossip "won't correctly repair upon network changes". Investigate why (the field keeps the historical maximum), and design a repair mechanism — e.g. a T-based decay (timeout) resetting the gossip, or the lowpass/recentTrue state blocks of section 8 — then verify self-stabilisation in the simulator. |
| PARTITION-SERVICE | Turn the partition block into a reusable API function and use it to implement a regional service: e.g. dangerousDensity(randomPartition(30), 300) of the crowd example — density estimation with Fruin thresholds inside dynamically formed partitions. |
| CHANNEL-IN-ALCHEMIST | Run the channel (or the evacuation-alert) in the Alchemist Scafi incarnation — the bridge to chapter 12, section 10 — over 10 000 nodes; measure the rounds to self-stabilisation after adding/removing a source (the widget of section 5 at scale). |
| RL-AGGREGATE | Deck 09's promise: "will allow to combine with other owned technologies (scafi, that is)". Use a Q-learned policy (from chapter 13) to decide device-level parameters of an aggregate program — e.g. the width of the channel or the threshold of crowdTracking — and evaluate the learned policy in the simulator. |
The arc of this chapter is the arc from abstraction to engineering: the requirements of section 1, the field as the data structure, the four constructs of the field calculus, the three combinators G, C, T, and the two faces of resilience. A strong presentation takes one program — the gradient, or the channel — and walks it through every level: field-calculus expression, ScaFi code, operational semantics (rounds, alignment), GCT classification, and self-stabilisation argument, ending with the platform story (Alchemist as executor) and the learning story (RL as the controller of chapter 13).
Specify overall behaviour, not individual device programs; abstract from infrastructure shape and interactions; adapt automatically to environment changes; global output from global inputs; spatial and temporal patterns; a compositional model; an abstract notion of executing platform. The platform: an abstract actor executing locally; an aggregate specification generates local aggregate actors (AAs) that transparently carry the collective behaviour; local actors interact with the AAs for sensing/actuation.
Motto: "program the aggregate, not individual devices". (1) The reference computing machine is an aggregate of devices as a single body fading to the actual space; (2) the reference elaboration process is the atomic manipulation of a collective data structure, a field; (3) the actual networked computation is a proximity-based self-organisation system hidden under the hood. A field is a map Space → Values, possibly evolving, over booleans, reals, vectors, functions, tensors.
An event is a triple ⟨δ, t, p⟩ — device δ firing at time t in position p. The events domain is a coherent set of events (devices cannot move too fast); a field is a function ϕ : D → V; scheduling is exogenous. Full computability at a node is the ability to expose a value obtained with full power from nodes in the cone of past events — the causal horizon of the device.
e ::= x | v | e(e₁,...,eₙ) | rep(e₀){e} | nbr{e}. Value v: a field constant in space and time. Application e(e₁,...,eₙ): e evaluates to a field of functions inducing a partition of the domain; each λᵢ is applied within its region. rep(e₀){eλ}: e₀ where the domain begins, else eλ applied to the previous value at each device. nbr{e}: at each event, gathers the most recent values of e in the neighbours (in restriction).
branch(e-bool){e-then}else{e-else} ≈ (e-bool ? ()=>{e-then} : ()=>{e-else})(): the boolean field partitions the domain, and each branch evaluates only within its region (restriction). Advanced patterns: spread code in different versions in different regions; have different regions run different programs.
14: rep(0){x => max(sense(1), maxHood(nbr{x}))} gossips the maximum of the sensor over the network (each device keeps the max of its own and its neighbours'). 15: rep(Infinity){d => sense(1) ? 0 : minHood(nbr{d} + 1)} computes a hop-count gradient from the source where sense(1) is true. 16: the same with nbrRange instead of 1 — a Euclidean (distance-weighted) gradient.
mid() (device id), rep[A](init)(fun) (time/state), nbr[A](expr) (neighbour evaluation), foldhood[A](init)(acc)(expr) (neighbourhood fold with a monoid — minHood, maxHood, sumHood), branch[A](cond)(th)(el) (space-time branching), sense[A](LSNS) (local sensor), nbrvar[A](NSNS) (neighbourhood sensor).
channel(source, dest, width) = dilate(gradient(source) + gradient(dest) <= distance(source, dest), width). gradient reifies the minimum distance from a source; distance(source,dest) is the geodesic distance between the two (a pair-carrying gradient returning its second component); the inequality selects the ellipse with foci source and dest; dilate thickens it by width. Builtins: ?:, nbrRange, minHood/sumHood, pointwise math, pair/fst/snd.
A node state is a value-tree updated at asynchronous rounds; at the end of a round the tree is made accessible to the neighbourhood. Application evaluates the body against the neighbours that evaluated the same expression (alignment); rep applies eλ to the previous value-tree's root if available, else evaluates e₀; nbr gathers values from aligned neighbour trees plus the local evaluation. Platform requirements: a neighbourhood notion, asynchronous rounds emitting round results, recent neighbour results — tolerating message losses and varying round frequencies by construction.
G (spreading) spreads and en-route computes information outwards a source; C (collecting) collects and en-route aggregates information inwards a destination; T (time decay) locally iterates computations with termination. distance(source) = G(source, 0, ()=>nbrRange(), (x)=>x+nbrRange()); broadcast(source, v) = G(source, v, ()=>nbrRange(), (x)=>x); sum(source, field) = broadcast(source, C(source, distance(source), +, 0)); timer(timeout) = T(timeout, 0, (t)=>t-dt()) == 0.
Resilience: the ability of a functional component to properly work in the face of changes to inputs and environment. Self-stabilisation: given an environment (inputs and topology), computing e results in a stable unique field in finite time — an I/O space problem, so occasional changes do not affect the result; undecidable in general, but GCT provides sufficient conditions. Dynamics control: how self-stabilisation is reached under ongoing changes — sometimes quickly, sometimes smoothly; hard in general; approached by substituting I/O-equivalent specialised combinators (Flex gradient, multi-path C, exponential filter T).
Step 1: get asmd-public-scafi running (and ScafiWeb). Step 2: perform the variations — branch vs mux (restriction), foldhood to a Set[Int] of neighbour ids (interoperability), minHoodPlus on pairs (closest neighbour), gossiping with repair (dynamics), stretched gradient (nbrRange tweaking). Step 3: build partition from a pair-carrying gradient. Step 4: do the channel via gradient, broadcast, distance.