This thesis explores Distributed Spatial AI -- how devices can coordinate to perform inference in a decentralised manner to enhance their Spatial AI abilities beyond each device's perceptual capabilities while achieving low-power and scalability. First, we investigate factorised computation, which aims to minimise the cost of data transfer by collocating the processing near the sensor where the data is captured. We develop a Visual Odometry (VO) system using a focal-plane sensor-processor, which enables computations such as feature extraction to occur directly on the camera's focal-plane. This enables our VO pipeline to operate at 300 FPS, making it robust against violent motions while also being low-power. We then explore the scene representation for visual Simultaneous Localisation and Mapping (SLAM). Representing the scene with many 3D Gaussian blobs, we achieve near-photorealistic fidelity 3D reconstruction online using a single moving camera. All the images captured by the camera are compressed into a 3D representation from which we can re-render the images at near original quality and perform novel-view synthesis between views. The core of this thesis is the investigation of how scalable, accurate, and robust many-device localisation can be achieved. We argue that Gaussian Belief Propagation (GBP) is a promising algorithmic candidate for Distributed Spatial AI, and using GBP, we develop Robot Web, a framework for decentralised localisation. Extending the formulation of GBP to support Lie groups, we demonstrate GBPs ability to localise 1000s of devices even under challenging situations, such as communication failures and large amounts of outlying measurements, using only ad-hoc peer-to-peer communication. The asynchronous property of GBP enables the definition of a simple communication protocol, which individual devices can implement to participate in co-localisation. Finally, we enhance the Robot Web framework to enable autocalibration of the sensors' and markers' extrinsic while simultaneously performing localisation, further improving the accuracy of localisation.