Abstract

Nowadays, distributed computing (DC) applications such as ubiquitous participatory sensing, wireless sensor networks (WSNs), and in-network DC are available everywhere due to the low cost of small-sized devices which have processing and wireless communication capabilities. These scenarios impose new constraints to DC, namely, a highly dynamic topology, a considerable number of computing elements (CEs), with restricted computing-power and limited amount of power for consumption. The success of this new class of applications is closely related to scalability issues and to the efficient use of both the limited energy resources and computing power of the CEs. To do so, control mechanisms must be provided to applications and CEs so that they can deal with the problem of smartly and transparently distributing and executing applications among the CEs. This research effort tackles the problem of efficiently allocating applications onto the available CEs of a distributed computing system (DCS). Here, the specific class of DC applications where hand-held devices and wireless sensors collect, process and disseminate spatial, temporal and/or environmental information, at different time scales, will be considered. The resource allocation problem regarded here aims to answer the questions of: How to efficiently map an application onto a finite number of CEs, while considering their energy consumption, their limited and heterogeneous computing power, the highly dynamic behavior of both the communication network as well as the CEs, and the scalability of the solutions to be provided. By answering this research question, control mechanisms may be provided to applications and CEs so that they can efficiently and transparently distribute and execute applications among the CEs. Methodology. This project consists in a theoretical and an experimental effort. The theoretical effort aims to develop scalable mathematical models for both the DCS and its applications, and resource allocation algorithms for improving the performance of applications executed on a DCS. The major tools to employ in the modeling are graph theory, optimization, and probability theory. The key ideas for achieving scalability are: (i) organizing applications and the DCS in a hierarchical fashion; and (ii) limiting the amount of communication exchanged among the CEs. The experimental effort consists in implementing prototype DC applications and resource allocation algorithms of interest to the Chilean users of WSNs and pervasive systems. This effort considers also the experimental characterization of the CEs and the implemented applications. Such characterization will be fed into the theoretical models to obtain more practical versions of the theoretical models. Goals. The main goals of this research proposal are: to develop novel simple and scalable mathematical models for large-scale, energy-constrained DCS; to develop novel off-line scalable resource allocation algorithms for partitioning DC applications on a finite number of computing grids to develop novel computationally cheap resource allocation algorithms which can be implemented on-line at the CEs; and (iv) to implement prototype applications over WSNs and pervasive computing systems composed of smart-phones and tablets. Expected outcomes. By developing scalable, energy-efficient algorithms and models for DCSs it is expected also to contribute to the field of scalable pervasive computing. The research effort to conduct would enable the analytical optimization of DC applications and the practical implementation of prototype WSNs and smart-phone– and tablet–based DCSs.