Opportunistic computing in fully decentralized and mobile networks

The interplay of social networking platforms, information retrieval techniques and dynamic wireless communications has grown exponentially over the past few years. Together, these tools are shaping new forms of fully decentralized computation and applications. These opportunities are ampli ed by the relative simplicity to set up networks of small or tiny devices, such as wireless sensors and active or passive RFIDs, that allow to extract information from the environment, to process and to share it, expanding our data access and interaction capabilities and blurring the border between the digital and physical world. These new technologies coexist with traditional ones and entail a model of communication and computation that is decentralized and opportunistic in nature, in which new challenges arise and many standard assumptions do not hold. At the same time, more mature technologies, such as cellular telephony, have evolved to the point where we have small, portable, but relatively powerful devices, often endowed with sensing capabilities, that can run sophisticated applications and can exchange data in an ad-hoc fashion using wireless technologies such as Bluetooth. As a result, a number of potential applications arise, in which users interact across the digital and physical world, exchanging and processing data extracted from their local environment in real time. While a number of theoretical models of distributed computation have been proposed in the past, new e orts have been done recently in order to describe the interaction and the computing power of networks of tiny devices with limited capabilities. One rst objective of this thesis was studying methods for the opportunistic estimation of statistics of interest in fully decentralized environments and their use to implement key tools in social networking applications. Since many scenarios of interest for this work involve dynamic networks of wireless devices with limited or very limited capabilities, another direction of research in my work was to investigate the limits of theoretical models proposed to describe them. Furthermore, many opportunistic scenarios of interest involve computations over evolving networks, dynamically formed by the interaction of wireless devices carried by humans, moving in a given area of interest. Intuitively, the performance of applications in such scenarios can be greatly a ected by the characteristics of the underlying evolving networks. In order to address this aspect and to gain an initial understanding of its impact in practice, I exploited recently proposed technologies, to perform real time tracking of social interactions occurring between individuals in the physical space. This activity resulted in the collection of mobility and interaction traces in a number of indoor scenarios. In doing this, I also investigated techniques and methods to e fficiently represent and to analyze evolving social network and to reconstruct them from real interaction traces