Relaxed Model Characterization of Degree-Guided Task Assignment

Abstract

Cluster computing systems are popular in IT industries for data-intensive applications and services. In such systems, the task file is divided into data chunks, which are replicated and distributed to a number of servers. Servers have to remotely acquire necessary file chunks that are not present locally before they proceed to relevant computation. Due to the fact that network connections have inevitable latencies, servers complete tasks with local data faster than those with remote data. Therefore, task assignment with data locality constraints plays an essential role in cluster computing systems. In this research, we have proposed a degree-guided assignment algorithm that significantly outperforms the random server algorithm at light load. However, the performance of this algorithm drops sharply when the system reaches the queuing threshold. We have begun to look for enhancements that solve the problem of performance plunge at high loads. Specifically, my work in this thesis concentrates on characterizing the performance of the degree-guided algorithm in a relaxed model, where leftover tasks are considered as fresh ones in a time interval. This will allow us to characterize and analyze the degree-guided algorithm from an approaching perspective.