This chapter presents the concept of decentralized spatial computing (DeSC) as a way to embed dynamic spatial data capture and processing capabilities within our built urban environment. The chapter illustrates the potential of DeSC for safe- guarding privacy in a dynamic location-based services scenario: Mobile service users protect their potentially sensitive location by the use of a decentralized query algorithms, solely collaborating with peers close by and thereby excluding the privacy bottleneck of an omniscient global service provider. In an extensive set of consecutive experiments several decentralized query algorithms were tested, trading the level of privacy for the quality of service. The use of a real world test bed, — a small part of Ordnance Survey’s OS MasterMap® Integrated Transport Network™ Layer for Southampton — underlines the experiments’ validity. The chapter concludes with a research and development agenda for DeSC in the urban context.