Distributed Workload Dissemination for Makespan Minimization in Disruption Tolerant Networks

Mobile devices are undergoing explosive proliferation today. Although they are gaining more and more capabilities, they still fall short to execute complex applications. One possible solution to alleviate this limitation is offloading tasks to remote clouds. However, it may require persistent connectivity to the Internet and thus is not always available or affordable. An alternative solution is taking advantage of pervasive mobile devices and their pairwise encounters. In this paradigm, complex tasks from mobile devices are processed in a distributed and collaborative fashion on all mobile devices that are loosely-connected. Working towards this vision, this paper studies the following problem: given a task that originates at some node in a Disruption Tolerant Network (DTN), how are we to disseminate the task's workload during the pairwise contacts among mobile devices to achieve makespan minimization? We first imagine access to an oracle that has global and future knowledge of node mobility, and we design a provably-optimal centralized polynomial-time solution as the benchmark for comparison. With the insights obtained from the centralized solution, we then develop a distributed dissemination algorithm, D2, which maintains certain neighborhood information at individual nodes. D2 makes dissemination decisions based on the estimations of the potential computational capacities and the future workloads of mobile nodes. Extensive trace-driven simulations confirm the effectiveness of D2.