Time-fluid field-based coordination

Danilo Pianini, Stefano Mariani

Mirko Viroli, Franco Zambonelli

What is time?

Does time even exist?

Between physics and philosophy

Pre-relativity

Immutable
Everywhere
Fine for many practical applications, but does not match reality

Between physics and philosophy

Modern views

Very much related to the search for a unifying theory
Several (conflicting) positions

Suggested readings

Carroll’s From eternity to here
Rovelli’s The order of time

Relational interpretation

Quantum systems are observer-dependent

time might be meaningful only in presence of events

time comes from causality and not vice versa

Field based coordination

Computing by evolving distributed data structures:

computational fields

Notable examples (not exhaustive):

TOTA (Mamei/Zambonelli)
Fixpoint-based computational fields (Lafuente/Loreti/Montanari)
Aggregate computing (Beal/Pianini/Viroli)

Field based coordination

Dealing with time

The designer focuses on the eventual behaviour
Computation happens in atomic rounds
Round scheduling is controlled externally
Scheduling may be:
- reactive e.g., in TOTA
- proactive/timed e.g., in Aggregate computing
- abstracted away e.g., in Fixpoint-based computational fields

Field based coordination

Dealing with time

Historical focus on space rather than time
Time is abstracted away by design whenever possible

…but in practice…

Space and time are intertwined
Propagation speed influences the evolution of fields
Dynamic systems are always in a transient state

Challenge and desiderata

why bother?

Fine grained control over transient dynamics
enables improved reactivity to changes as well as efficiency
both in communication and energy consumption

Requirement

do not force the designer to lower the abstraction level
do support all the existing coordination mechanisms
do allow for proactive and reactive policies

Time-Fluid Field Coordination

leverage field-based coordination itself and maintain a
causality field
driving the dynamics of application-level fields

Time-Fluid Field Coordination

Define a set of platform triggers $ \mathcal{T} $
- including timers and results of field computations
Associate a guard policy $ \mathbf{G} $ to every field program $ \mathbf{P} $
- inheriting the language of the field program itself
- $ \mathbf{G} $ ’s evaluation produces a boolean $b$ and a set $T_c\subseteq\mathcal{T}$
  - $b$ determines whether $ \mathbf{P} $ should execute immediately
  - $T_c$ is the causality field
- $ \mathbf{P} $ will get evaluated next if an event $t\in$ $T_c$ happens
At bootstrap, all policies are evaluated.

Time-Fluid Field Coordination

$ \mathbf{P} $ produces a local field value by consuming:

messages from neighbors $M\in\mathcal{M}$
contextual information (e.g., sensor readings) $S\in\mathcal{S}$

$ \mathbf{G} $ is a field computation locally modeled as: $$f_G\colon{}(\mathcal{S}, \mathcal{M})\to(\{0, 1\}, \mathcal{T}^{2})$$

Access to $M$ and $S$ and the ability to produce $T_c\in\mathcal{T}^{2}$
have crucial impact on the expressivity of $ \mathbf{G} $

Time-Fluid Field Coordination

Consequences

From programming space in time to programming the space-time
- Adaptation controls time rather than experience it
Adaptatation to causality by reacting to perceived events
- e.g., by accelerating or slowing down the field computation
Co-causality as field computations can depend on each other
- Of course, with great expressiveness comes great responsibility

Time-Fluid Aggregate Computing

Prototype implementation available using the Protelis programming language

No change to the syntax of Protelis
Aggregate computations have an associated guard policy
Guard policies are written in plain Protelis

Time-Fluid Aggregate Computing

guard policy code sample (more in the paper…)

import platform.EventType.* // Event types are provided by the hosting platform
let reason = env.get("platform.event") // Sensor-like access to the triggering event
// Policy guards are full fledged aggregate programs
let peopleCount = foldSum(nbr(env.get("people_count")))
let lastCount = rep(s <- [0, 0]) { [s.get(1), peopleCount] }.get(0)
let attendantsChanged = lastCount != peopleCount
[ // A policy returns a pair of:
  // A boolean, deciding whether the guarded program should run
  reason == MESSAGE_TIMEOUT || reason == MESSAGE_RECEIVED || attendantsChanged,
  [MESSAGE_RECEIVED, SENSOR("people_count")] // A list of accepted future triggering events
]

Evaluation

Scenario

40x40 irregular grid of devices with the goal of computing distance from the closest source
Sources are mobile devices and one static device located on South-West of the scenario
Mobile devices enter one at a time from North-West and exit from North-East
Devices round frequency is dynamically regulated via a guard policy