Spatial Tuples: Augmenting Reality with Tuples

We introduce Spatial Tuples, an extension of the basic tuple-based model for distributed multi-agent system coordination where (i) tuples are conceptually placed in regions of the physical world and possibly move anchored to a mobile computational device, (ii) the behaviour of standard Linda coordination primitives is extended so as to depend on the spatial properties of the coordinating agents, tuples, and the topology of space, and (iii) the tuple space can be conceived as a virtual layer augmenting physical reality. Motivated by the needs of mobile augmented-reality applications, Spatial Tuples explicitly aims at supporting space-aware and space-based coordination in agent-based pervasive computing scenarios. This paper presents the coordination model, its formalisation as a process algebra, a library of patterns of coordination it enables, and a discussion of application scenarios, challenges, and open issues for future works.