Superstring: a scalable service discovery protocol for the wide-area pervasive environment

Abstract—Arguably, the world has become one large pervasive computing environment. Our planet is growing a digital skin of a wide array of sensors, hand-held computers, mobile phones, laptops, web services and publicly accessible web-cams. Often, these devices and services are deployed in groups, forming small communities of interacting devices. Service discovery protocols allow processes executing on each device to discover services of-fered by other devices within the community. These communities can be linked together to form a wide-area pervasive environment, allowing processes in one group to interact with services in an-other. However, the costs of communication and the protocols by which this communication is mediated in the wide-area differ from those of intra-group, or local-area, communication. Communica-tion is an expensive operation for small, battery powered devices, but it is less expensive for servers and workstations, which have a constant power supply and are connected to high bandwidth net-works. This paper introduces Superstring, a peer-to-peer service discovery protocol optimised for use in the wide-area. Its goals are to minimise computation and memory overhead in the face of large numbers of resources. It achieves this memory and computation scalability by distributing the storage cost of service descriptions and the computation cost of queries over multiple resolvers. Index Terms—peer-to-peer, pervasive computing, resource dis-covery, service discovery I