MABSTA: Collaborative Computing over Heterogeneous Devices in Dynamic Environments

• Main Authors: Kao, Yi-Hsuan, Wright, Kwame, Huang, Po-Han, Krishnamachari, Bhaskar, Bai, Fan
• Format: Conference Proceeding
• Language: English
• Subjects: Delays; Dynamic scheduling; Heuristic algorithms; Performance evaluation; Stochastic processes; Task analysis; Wireless communication
• ISSN: 2641-9874
• DOI: 10.1109/INFOCOM41043.2020.9155232

Collaborative computing, leveraging resource on multiple wireless-connected devices, enables complex applications that a single device cannot support individually. However, the problem of assigning tasks over devices becomes challenging in the dynamic environments encountered in real-world settings, considering that the resource availability and channel conditions change over time in unpredictable ways due to mobility and other factors. In this paper, we formulate the task assignment problem as an online learning problem using an adversarial multi-armed bandit framework. We propose MABSTA, a novel algorithm that learns the performance of unknown devices and channel qualities continually through exploratory probing and makes task assignment decisions by exploiting the gained knowledge. The implementation of MABSTA, based on Gibbs Sampling approach, is computational-light and offers competitive performance in different scenarios on the trace-data obtained from a wireless IoT testbed. Furthermore, we prove that MABSTA is 1-competitive compared to the best offline assignment for any dynamic environment without stationarity assumptions, and demonstrate the polynomial-time algorithm for the exact implementation of the sampling process. To the best of our knowledge, MABSTA is the first online learning algorithm tailored to this class of problems.