Distribution is first of all physical distribution, which fundamentally means spatial distribution. When we place computers in different rooms, cities, or continents, we are making a spatial decision. The network cables, wireless signals, and data paths all occupy physical space and are subject to its constraints — latency, signal degradation, interference, and the speed of light.
As with time, we must first understand what space is, what we mean when we think and speak of space, and how we represent space in our reasoning and in computing. Only then can we design systems that are truly space-aware.
Nowadays, a huge number of application scenarios require spatial reasoning and spatial computing: environmental monitoring, disaster recovery, crowd steering, autonomous vehicles, the Internet of Things — all of them fundamentally depend on the spatial organisation of computation, communication, and data.
This lesson traces the concept of space from its mathematical and logical foundations through to modern computational frameworks, showing how each layer builds on the one before it and how the result is a rich landscape of spatial computing approaches.
For early humans, awareness of the surrounding environment was the premise to self-awareness [Martelet, 1998]. Modelling and measuring the environment were the premises to goal-driven actions — hunting, gathering, navigating, building. Space is thus a conceptual tool that humans use to model the environment where we live, to organise resources and activities, and to understand their dynamics.
The way in which we represent space mutually affects the way we can reason about it — in ways not yet fully understood. There are two clearly contrasting views [Li and Gleitman, 2002; Levinson et al., 2002]: does language shape spatial reasoning, or does spatial cognition precede language?
| View | Position |
|---|---|
| Linguistic relativity | The language we speak shapes how we perceive and reason about space (Levinson et al.) |
| Cognitive universalism | Spatial cognition is a universal human faculty; language merely reflects it (Li & Gleitman) |
Humans have their own ways to represent space and to process spatial information [Byrne and Johnson-Laird, 1989]. Spatial reasoning is a feature of intelligent processes — and humans are not alone in this [Gentner, 2007; Haun et al., 2006]. Human spatial reasoning is mostly qualitative or approximate rather than exact [Dutta, 1988].
For a well-organised account of how humans (learn to) represent and reason about space, see [Clements and Battista, 1992]. This cognitive foundation underpins the computational models we will explore.
Geometry is the first systematic attempt to model space by abstracting away from our perception of reality. Basic geometric concepts (point, line, angle, circle) and shapes (triangle, rectangle, trapezoid) were developed from Babylonian astronomy through Egyptian land surveying to Greek geometry.
Euclid's Elements [Kline, 1972] marked a turning point: geometry was no longer seen as a set of empirical observations and practical methods for measuring distances and areas. Instead, it was conceived as an abstract mathematical theory which, while rooted in perceived reality, had its own absolute right of existence and development [Aiello et al., 2012].
This axiomatic approach — representing space and reasoning on space through axioms, theorems, and proofs — is the foundation of all subsequent spatial modelling in mathematics and computer science.
that which has no part— Euclid
breadthless lengththe first dimension
length and breadthtwo dimensions
three dimensionsthe world we inhabit
The discovery that physical space may not satisfy Euclid's fifth postulate (the parallel postulate) led to non-Euclidean geometries: Riemann's elliptic geometry and Bolyai & Lobachevsky's hyperbolic geometry. These geometries represent true physical space beyond our direct sensorial-cognitive perception [Aiello et al., 2012].
| Geometry | Parallel postulate | Curvature | Example surface |
|---|---|---|---|
| Euclidean | Exactly one parallel through a point | Zero | Flat plane |
| Elliptic (Riemann) | No parallel lines exist | Positive | Sphere surface |
| Hyperbolic (Bolyai-Lobachevsky) | Infinitely many parallels | Negative | Saddle surface |
That discovery was an unsurpassed manifestation of the superiority of the abstract, logical approach of mathematics over the empirical approach underpinning the natural sciences — at least when it comes to comprehending such fundamental physical concepts as space and time.
Morris Kline's foreword to Russell's Essay on the Foundations of Geometry [Russell, 1956] asks: "What geometrical knowledge must be the logical starting point for a science of space and must also be logically necessary to the experience of any form of externality?"
The axiomatic approach to geometry evolved from Euclid through Peano to Hilbert's sound axiomatic foundation for geometry [Hilbert, 1950]. Then came Descartes's coordinatisation of Euclidean space — using coordinate systems to solve purely geometric problems with algebraic methods. Klein's Erlangen program reframed geometry as the study of transformations that preserve fundamental geometrical properties [Balbiani et al., 2007].
The culmination of this trajectory is Tarski's logical foundation of geometry [Tarski, 1959]. Elementary geometry is developed as a first-order theory using just two geometric relations:
Tarski's elementary geometry can be developed axiomatically using just two primitive relations: betweenness (point B lies between points A and C) and equidistance (segment AB is congruent to segment CD). Via coordinatisation, elementary geometry becomes the theory of the field of real numbers.
This is a landmark result: the completeness and decidability of the first-order theory of the field of reals implies an explicit decision procedure for elementary Euclidean geometry. That is, there exists an algorithm for deciding the truth of any statement in Euclidean geometry — though not an efficient one.
Tarski's result shows that elementary Euclidean geometry is decidable. Why does this matter for computing with space? What are the practical limitations of this result?
Beyond classical first-order logic, non-classical logics have proven particularly valuable for modelling, analysing, and reasoning about space. Modal logics stand out because they can be more specific and have better computational behaviour — they are very often decidable.
The key insight [McKinsey and Tarski, 1944] is that the modal operators can be reinterpreted spatially:
| Modal operator | Traditional reading | Spatial (topological) reading |
|---|---|---|
□P (necessarily P) | P is necessarily true | The interior of the region where P holds |
◇P (possibly P) | P is possibly true | The closure of the region where P holds |
The modal logic S4 [Bull and Segerberg, 1984] is sound and complete with respect to topological semantics: S4 is the modal logic of any Euclidean space. This means that the theorems of S4 correspond exactly to the topological truths of Euclidean space — a profound connection between logic and geometry.
S4 is the modal logic of Euclidean space. The box operator corresponds to the topological interior, the diamond to topological closure. Reasoning about space is, at a fundamental level, modal reasoning.
A basic problem in spatial reasoning is distance. Approaches based on the notion of metric give us quantitative measures. But topology generalises metric: the concept of neighbourhood can be defined without reference to numerical distance [Singer and Thorpe, 1967].
Topology studies the properties of space that are preserved under continuous transformations (stretching, bending, but not tearing or gluing). A topological space is defined by its open sets — collections of points that formalise the notion of "nearness" without requiring a metric.
Alongside algebra and geometry, topology became one of the fundamental branches of contemporary mathematics [Aiello et al., 2012]. For computing with space, topology provides tools to reason about connectivity, boundaries, and continuity without the overhead of exact coordinates.
The progression is: distance (metric) → neighbourhood (topology's primitive notion) → open sets (the axiomatic foundation of topology). Each step abstracts further from concrete measurement, enabling reasoning about space at higher levels of generality.
Metric space: d(x,y) defines distance
↓ generalise
Topological space: neighbourhoods define "closeness"
↓ axiomatise
Open sets: collections closed under finite intersection and arbitrary unionMathematical morphology (MM) analyses shape, spatial information, and image processing. Any mathematical theory dealing with shapes can contribute to MM [Aiello et al., 2012].
The connection to modal logic comes from the similarity between the algebraic properties of MM operators and those of modal operators. This yields modal morphologic — an approach that is efficient for spatial reasoning tasks such as guiding the exploration of space in a focus-of-attention process, and for recognition and interpretation tasks.
| MM operation | Effect | Modal analogue |
|---|---|---|
| Dilation | Expand a shape outward | ◇ (possibility / closure) |
| Erosion | Shrink a shape inward | □ (necessity / interior) |
| Opening | Erosion then dilation (smoothing) | □◇ |
| Closing | Dilation then erosion (fill gaps) | ◇□ |
Mathematical morphology is widely used in image processing and computer vision, but its logical foundations connect directly to the modal logics of space we discussed above. This cross-fertilisation between logic, topology, and computation is a recurring theme in spatial computing.
Physical distribution of computational systems creates a new space for software components. The key milestones in this spatial evolution:
Middleware acts as an operating system for distributed systems, providing topological notions and mapping logical distribution onto physical distribution. For example, JADE [Bellifemine et al., 2007] provides agent programmers with the topological notions of container and platform to represent locality for agents.
Sometimes, physical distribution is what actually matters. No amount of logical abstraction can eliminate the physical constraints of space — latency, bandwidth, energy, and the speed of light remain fundamental.
Physical distribution of computational systems is essential to cope with the distributed nature of many working environments — as well as with the need for situated computation. That is, computations occurring locally where either perception or action are taking place, either elaborating on perception, driving action, or both.
A situated computation is a computation that occurs locally where perception or action takes place. When system requirements mandate situated computations within a distributed physical environment, situated distributed systems are the only way out.
The Internet of Things (IoT) makes the need for situated computation unescapable. Why? Give concrete examples of IoT scenarios where centralised computation is infeasible and explain why situated computation is the only viable alternative.
Computational geometry [de Berg et al., 2000] deals with computing with geometry to solve problems: using space to represent problems (both spatial and non-spatial ones), using geometry to make them computable, and using algorithms to compute solutions.
Suppose you need to find the nearest coffee shop for any point on campus. You divide the campus into regions around each coffee shop — a Voronoi diagram — where each region contains all the points for which that shop is the nearest. This is a canonical problem in computational geometry. How do we compute this?
GIS represent, capture, store, check, and display data representing positions on the Earth (and possibly other planets in the near future). The notion of space is clearly defined in GIS [Huisman and de By, 2009]:
A geographic information system is a computer-based system that supports the study of natural and man-made phenomena with an explicit location in space. To this end, the GIS allows data entry, data manipulation, and production of interpretable output that may provide new insights about the phenomena.
Virtual reality (VR) creates artificial worlds with artificial space — digitally-created environments represented exclusively as computational spaces where real people can perform sensorimotor and cognitive activity [Fuchs et al., 2011]:
Virtual reality is a scientific and technical domain that uses computer science and behavioural interfaces to simulate in a virtual world the behaviour of 3D entities, which interact in real time with each other and with one or more users in pseudo-natural immersion via sensorimotor channels.
In VR, interaction and immersion are the key concepts. The virtual space must respond to user actions in real time, maintaining the illusion of a coherent spatial environment.
Gaming is the most prominent application of VR. Platforms like Unity3D and Unreal Engine provide the means for building whole virtual worlds that can be explored from a wide range of diverse devices. Microsoft Kinect is one of the most well-known VR applications that brought spatial interaction to mainstream gaming.
Physical space → Virtual space (modelled computationally)
User action → Sensor capture → Spatial update → Render response
(real world) (Kinect/camera) (game engine) (display)LBS add a virtual layer to physical space, using information about the position of a user or device to provide information, entertainment, or security. Examples range from practical (Around Me, Mobike) to playful (BotFighters, Ingress, Pokemon Go, Harry Potter: Wizards Unite, Minecraft Earth).
Augmented reality goes further by merging real-world information with context-sensitive digital content in a meaningful way [Furht, 2011]. The key point is that the virtual and physical layers mutually affect each other dynamically.
| Aspect | LBS | AR |
|---|---|---|
| Virtual layer | Overlaid on physical space | Integrated with physical space |
| Interaction | User queries for information | Bidirectional, real-time |
| Dynamics | Static mapping | Mutual influence |
| Example | "Find nearby restaurants" | Pokemon Go — creatures appear in real locations |
Gamification in AR can easily lead to any sort of relevant application — medical, civic, educational, touristic. GeoZombie [Prandi et al., 2016] was a step forward (and a predecessor to Pokemon Go) that used AR for civic engagement.
During the "Computing Media and Languages for Space-Oriented Computation" workshop at Dagstuhl (2006), three classes of spatial systems were identified:
Space is either a means or a resource. These systems use the spatial distribution of computation but do not represent space explicitly.
Space is fundamental to the application problem, is explicitly represented and manipulated, and is essential to express the result of a computation.
A spatial computer (or spatial computing system) is a computational system where (the logic of) space is essential in representing the problem, defining computation, and expressing the result [Beal et al., 2011]. Spatial computing is any form of computation where (the logic of) space is relevant to express and perform computation.
Spatial Computing Languages (SCL) were born to address the issue of bringing space into programming languages, allowing programmers to explicitly deal with space-related aspects at the language level.
The interactive widget below simulates a tuplespace coordination model — a concrete example of spatial computing where data is organised by spatial location (tuples in a shared space) and processes interact through that space.
The annotated code below illustrates a spatial coordination pattern using a Linda-like tuplespace. Click each line for explanation.
A long list of SCL are available, which can be analysed and compared through the conceptual framework of [Beal et al., 2013]. The key dimensions of comparison include: how space is represented (continuous vs discrete, metric vs topological), how computation interacts with space (mobile agents, gradient propagation, field computation), and what guarantees the language provides (consistency, timeliness, fault tolerance).
We have traced the concept of space from its mathematical and logical foundations through to modern computational systems. The key takeaways:
| Layer | Key tools / concepts | Application areas |
|---|---|---|
| Mathematical | Geometry, topology, metric spaces | Foundations of spatial modelling |
| Logical | Modal logics (S4), Tarski's geometry | Spatial reasoning, decidability |
| Computational | Computational geometry, GIS, VR | Problem solving with spatial data |
| Distributed | Middleware, situated systems, IoT | Physical distribution of computation |
| Spatial computing | SCL, tuplespaces, spatial coordination | Unified framework for spatial systems |
Different types of code mobility are possible (mobile agents, code-on-demand, remote evaluation), each exploiting the spatial structure of the distributed system in different ways. Spatial computing provides the framework to understand, compare, and design them coherently.
Distributed systems (coping with space): space is a means or resource, used but not explicitly represented. Example: a load-balanced web server farm that routes requests to the closest server, without explicitly modelling the geometry of the data centre. Situated systems (embedded in space): location in space and time is essential for computation. Example: a wildfire monitoring sensor network that only reports data from sensors in the fire's vicinity. Spatial systems (representing space): space is fundamental to the problem, explicitly represented and manipulated. Example: a GIS system computing the optimal evacuation route through a city, where the road network geometry is essential to the answer.
McKinsey and Tarski (1944) proved that S4 is sound and complete with respect to topological semantics — the interior operator corresponds to the box (necessity) and the closure operator to the diamond (possibility). Since Euclidean space is a topological space, all theorems of S4 hold in Euclidean space. For spatial computing, this means that modal logic provides a natural language for expressing and reasoning about spatial properties, and that computational tools from modal logic (decision procedures, model checking) can be applied to spatial problems.
Computing with space refers to using computational geometry, geographic information, or virtual spaces to solve problems — geometry, GIS, VR, gaming. Space is the medium or tool for computation. Spatial computing is a broader framework where (the logic of) space is essential in representing the problem, defining computation, and expressing the result. Spatial computing encompasses computing with space but also includes situated systems, distributed systems with spatial awareness, and Spatial Computing Languages that bring space into the programming model itself.
Tarski showed that elementary Euclidean geometry can be developed as a first-order theory using only two primitive relations (betweenness and equidistance). Via coordinatisation, it becomes the theory of the field of real numbers. The completeness and decidability of the first-order reals implies an explicit decision procedure — an algorithm exists to decide any statement in elementary geometry. However, the algorithm is not efficient: it has non-elementary complexity, meaning it is impractical for all but the smallest problems. This illustrates the gap between theoretical computability and practical spatial computing.
Mathematical morphology operations (dilation, erosion, opening, closing) have algebraic properties that mirror modal operators. Dilation corresponds to the diamond (◇, closure/possibility), erosion to the box (□, interior/necessity). This similarity yields modal morphologic, where spatial reasoning tasks (shape analysis, image processing, space exploration) can be expressed and solved using modal logic techniques. The benefit is that modal logic provides efficient reasoning tools — decision procedures, axiomatisations, and model-checking algorithms — that can be applied to spatial problems.
IoT involves billions of devices (sensors, actuators, smart objects) embedded in the physical environment. Sending all data to a central server for processing would require enormous bandwidth and introduce unacceptable latency. For example, an autonomous car must locally process camera and LIDAR data to avoid obstacles in milliseconds — there is no time to send data to a cloud server and wait for a response. Similarly, a smart factory's safety system must shut down a dangerous machine locally upon detecting a human nearby. The spatial distribution and real-time requirements of IoT make centralised computation infeasible, forcing computation to be situated where perception and action occur.
Euclidean geometry assumes the parallel postulate: through a point not on a line, exactly one parallel line exists. Non-Euclidean geometries (elliptic: no parallels; hyperbolic: infinitely many) showed that multiple consistent geometries exist, each describing different types of space. The importance beyond mathematics: it demonstrated that abstract logical reasoning can discover truths about the physical world that our senses cannot directly perceive. For spatial computing, it means that the "correct" spatial model depends on the application — the geometry of GPS coordinates (spherical/Elliptic) differs from the geometry of a building floor plan (Euclidean).
Middleware provides topological notions for distributed systems, mapping logical distribution upon physical distribution. This is a form of spatial computing at the infrastructure level — middleware defines a computational space with its own structure. JADE (Java Agent DEvelopment Framework) provides the concepts of container (a logical location hosting agents) and platform (a group of containers). Agents can move between containers, and agent communication respects this spatial structure. This allows programmers to write agent systems that are aware of location without needing to know the physical network topology.