Space, situatedness and mobility

Distribution is spatial distribution

M7 opens with a plain claim: distribution is first of all physical distribution, which basically means spatial distribution. Just as Ch. 2 asked what time is, we must ask what space is and how we represent it in reasoning and in computing, because a huge number of application scenarios now require spatial reasoning and spatial computing. (The deck borrows from the EASSS 2016 tutorial “Spatial Multi-Agent Systems”.)

For early humans, awareness of the environment was the premise to self-awareness [Martelet, 1998], and modelling and measuring it the premise to goal-driven action. Space is a conceptual tool to model where we live and to organise resources, activities and their dynamics. How we represent space and how we reason about it affect each other, in ways not yet well understood; [Li & Gleitman, 2002] and [Levinson et al., 2002] state two clearly contrasting views. Humans have their own ways to process spatial information [Byrne & Johnson-Laird, 1989], and are not alone in reasoning spatially [Gentner, 2007; Haun et al., 2006]. Human spatial reasoning may be either qualitative or quantitative, but is mostly approximated [Dutta, 1988]; Clements & Battista [1992] survey how humans learn it.

Space in mathematics and logic

Geometry: from measuring land to axioms

Geometry abstracts away from perception: basic concepts (point, line, angle, circle) and shapes (triangle, rectangle, trapezoid), from Babylonian astronomy through the Egyptians to Greek geometry. With Euclid's Elements [Kline, 1972] it stops being “a set of empirical observations and practical methods for measuring distances, area of land, etc.” and becomes “an abstract mathematical theory” with “its own, absolute right of existence and development” [Aiello et al., 2012], built on axioms, theorems and proofs. Physical space may not satisfy Euclid's fifth postulate, and non-Euclidean geometries follow: elliptic (Riemann) and hyperbolic (Bolyai, Lobachevsky). Aiello et al. call this “an unsurpassed manifestation of the superiority of the abstract, logical approach of mathematics over the empirical approach”.

From Euclid to Tarski

Kline asks what geometrical knowledge “must be the logical starting point for a science of space” [Russell, 1956, foreword]. The slides trace three answers [Aiello et al., 2012]:

1. Axiomatic. From Euclid to Peano, axiom systems are related to basic geometric notions; Hilbert gives a sound axiomatic foundation [Hilbert, 1950].
2. Analytic. Descartes coordinatises space, so geometric problems are solved algebraically. Klein's Erlangen program studies not figures but transformations preserving fundamental properties [Balbiani et al., 2007]: an abstract algebraic foundation.
3. Logical. Tarski makes elementary geometry a first-order theory with just two relations, betweenness and equidistance [Tarski, 1959]. Via coordinates it is like the field of reals, whose first-order theory is complete and decidable: an algorithm decides any statement of elementary Euclidean geometry, though not efficiently.

Modal logics of topology

Modal logics are particularly interesting among non-classical logics of space: they can be more specific and have better computational behaviour, very often being decidable. The route goes through topology. The basic spatial problem is distance, handled with metrics; neighbourhood generalises metric, and leads to topology [Singer & Thorpe, 1967], now “one of the fundamental branches of contemporary mathematics”.

A point is in □X when some neighbourhood of it lies inside X, in ◇X when every neighbourhood touches X.

Mathematical morphology (MM) analyses shape and spatial information, as in image processing; any mathematical theory of shapes can contribute to it. Modal morphology comes from the similarity between the algebraic properties of MM operators and of modal operators. It is efficient for spatial reasoning: to guide the exploration of space in a focus-of-attention process, and for recognition and interpretation. In short, we can compute about space and its organisation with diverse levels of efficiency.

Physical space in computational systems

Read spatially, distributed systems give software components a new space: computational units, channels and data are physically distributed. Local networks built the first virtual spaces, the Internet and IP-based locations the first “global” ones, and the WWW the first global space shared by agents and humans, a knowledge-intensive one.

Middleware (Ch. 1), the operating system of distributed systems, gives that space structure. It possibly supports mobility [Fuggetta et al., 1998], the second half of this chapter, and through EAI (enterprise application integration) it integrates applications horizontally into aggregated environments. Above all, it provides topological notions and maps logical distribution upon physical distribution: JADE's containers and platforms represent locality for agents [Bellifemine et al., 2007]. Sometimes, however, physical distribution is what actually matters.

Examples: disaster recovery, environmental monitoring, crowd steering. IoT makes the need unescapable. The slides sum up:

1. Distributed systems originate from the physical distribution of computation, communication and data.
2. Middleware provides a logical topology upon physical distribution.
3. Pervasive systems and IoT make situated computation a requirement, and situated distributed systems the only viable approach.
4. Nowadays non-trivial computational systems need to be space-aware.

Computing about space

Space can also be what a computation is about.

Computational geometry and GIS

Computational geometry [de Berg et al., 2000] uses space to represent problems, spatial or not, geometry to make them computable, and algorithms to solve them. The slides' example: find the nearest coffee shop on the Cesena campus, then for any point, by dividing the campus into regions containing all the points for which each shop is the nearest. How do we compute this?

The partition is the Voronoi diagram of the shops. Once computed, “which shop is nearest?” becomes “which region am I in?”.

GIS capture, store, check and display data on positions on the Earth (maybe other planets soon), so in GIS the notion of space is clearly defined.

Virtual reality and gaming

VR builds artificial worlds, represented exclusively as computational environments, where “real people” perform sensorimotor and cognitive activity.

Interaction and immersion are the key concepts. Gaming is VR's most prominent application: the slides cite Microsoft Kinect as a well-known VR application, and Unity3D and Unreal Engine for building whole virtual worlds.

Physical space meets computational space

Mixed reality is an old term possibly coming back into use, yet with an uncertain meaning. Gamification leads from AR to applications of any sort: medical, civic, educational, touristic. GeoZombie [Prandi et al., 2016] went a step further than Pokémon Go, and before it.

Spatial computing

Spatial computing is about systems where space cannot be abstracted away from computation [Shekhar et al., 2016]. The Dagstuhl workshop “Computing Media and Languages for Space-Oriented Computation” (06361) identified three classes of spatial systems:

1. Distributed systems, where space is either a means or a resource: intensive computing, or coping with space.
2. Situated systems, where location in space (and time) is essential for computation: embedded in space.
3. Spatial systems, where space is fundamental to the application problem, is explicitly represented and manipulated, and is essential to express the result of a computation: representing space.

Class 2 is situated computation; class 3 is computing about space.

Spatial computing languages (SCL) bring space into programming languages, letting programmers deal explicitly with space-related aspects at the language level. Spatial computing is a “landscape framework” for the many sorts of spatial computations and systems; the already-long list of SCLs can be analysed and compared through the conceptual framework of [Beal et al., 2013].

M7 closes with four points:

1. Maths and logic tools to represent, analyse and reason about space.
2. Computing about space and its organisation.
3. Different types of code mobility are possible.
4. Spatial computing as a framework for spatial computations and systems.

The third point is the hinge. If computation is situated, where it runs is part of its meaning and its cost, so we should be able to change it: that is the middleware “possibly supporting mobility”.

Moving the computation

C6 draws mostly on Fuggetta, Picco & Vigna [1998]. Sometimes passing data is not enough: we want to change where code executes (for load balancing, security, scalability…), or we do not want to separate data from the code that runs on them (objects, agents). Then code should be passed. Traditionally code moves with its whole computational context, so moving code is moving processes: process migration [Milojicic et al., 2000].

Why migrate code

1. Load balancing.
2. Minimising communication.
3. Optimising perceived performance.
4. Improving scalability.
5. Flexibility through dynamic configurability.
6. Improving fault tolerance.

But what moves with a program? Execution status, pending signals, data. A process has actions to execute, a state, and an environment (a computational context). Hence:

Alternatives for code migration

Two more questions: who starts the move, and what happens at the target.

Target vs separate process. Weakly mobile code may run in the target process or a separate one. Java applets run in the browser's address space, so no inter-process communication is needed at the target; the main problem is protection against malicious or buggy code, solved by running mobile code in a separate process.

Migrate vs clone. Strong mobility can also be supported by remote cloning: an exact copy of the process runs on the target machine in parallel with the original, as when a UNIX process forks a child that executes on a remote machine. Cloning is an alternative to migration, and in some sense improves distribution transparency: processes are transparently replicated on many machines.

Resources that do not move

Resources may not be as easy to move as code and variables: a huge database could in theory cross the network, but in practice it will not. Either references are updated or resources are moved, and two issues decide which.

How does the resource segment refer to resources? Process-to-resource binding

1. By identifier: the process needs the resource with a given name, e.g. via a URL or a local ID.
2. By value: it needs a resource based on its value, e.g. code libraries.
3. By type: it needs a resource based on its type, typically local devices like printers and monitors.

How does the resource relate to the hosting machine? Resource-to-machine binding

1. Unattached: easily moved between machines, like files associated with the migrating code.
2. Fastened: can be moved, but at a cost, like a local database.
3. Fixed: bound to a specific machine, like a monitor.

The slide crosses the two in a table of actions on references to local resources when migrating code [Tanenbaum & van Steen, 2017], using four actions:

1. MV: move the resource along with the code.
2. GR: establish a global, system-wide reference to the resource, which stays where it is.
3. CP: copy the value of the resource to the target.
4. RB: rebind the process to a locally available resource of the same type.

By columns: unattached resources travel cheaply, so MV and CP are open; a fixed resource never leaves its machine, so only GR or RB. By rows: a binding by identifier demands that very resource, so CP and RB never appear; a fixed resource bound by identifier gets a GR to the same resource, not a different local one. A binding by type accepts any resource of that type, so RB always comes first. GR is the common fallback, but every later access then crosses the network. As C6 concludes, code may move for many good reasons, and which type of mobility fits depends on application needs or technology constraints.