Scheduling divisible loads in heterogeneous distributed systems

Wydział Matematyki i Informatyki: Zakład Algorytmiki i ProgramowaniaCelem rozprawy jest analiza pewnych zagadnień szeregowania zadań jednorodnie podzielnych w heterogenicznych systemach rozproszonych i konstrukcja algorytmów rozwiązujących te problemy. Jako pierwszy rozważany był problem jednoetapowego szeregowania zadań jednorodnie podzielnych w topologii gwiazdy. Zaproponowano w pełni wielomianowe schematy aproksymacji i algorytmy aproksymacyjne dla tego problemu. Następnie rozważany był problem wieloetapowego szeregowania zadań jednorodnie podzielnych. Przeprowadzono analizę eksperymentalną własności problemu. Na podstawie otrzymanych wyników skonstruowano algorytmy heurystyczne. Zostały one ocenione i porównane eksperymentalnie. Teoria zadań jednorodnie podzielnych została także zastosowana do modelowania, analizy i szeregowania aplikacji MapReduce. Skonstruowano model matematyczny i algorytmy szeregowania takich obliczeń. Przeprowadzono ocenę efektywności MapReduce. Model został następnie uogólniony na aplikacje wielowarstwowe. Podano algorytmy szeregowania takich aplikacji i przeanalizowano wpływ parametrów systemu na strukturę uszeregowania.The main goal of this work is the analysis of several divisible load scheduling problems in heterogeneous distributed systems and the construction of algorithms solving these problems. First, single-round divisible load scheduling in star networks is analyzed. Fully polynomial time approximation schemes and approximation algorithms are proposed for this problem. Then, multi-round divisible load scheduling with memory limits is investigated. An extensive computational study of the features of the problem is provided. These results are used to construct heuristic algorithms solving the problem. The algorithms are evaluated and compared based on the experimental results. The divisible load theory is also applied to model, analyze and schedule computations in the MapReduce framework. A mathematical model of such computations is constructed and scheduling algorithms are proposed. Performance limits of the proposed organization of computations are investigated. Afterwards, the model is generalized to handle multilayer applications. Scheduling algorithms for multilayer applications are given and the influence of the system parameters on the schedule structure is studied