Resource allocation in selfish and cooperative distributed systems

W poniższej rozprawie badamy algorytmy zarządzania zasobami w systemach rozproszonych. Przedstawiamy kompleksowe spojrzenie na tę tematykę: rozważamy różne systemy---od ogólnych, abstrakcyjnych modeli, przez bardziej konkretne, dedykowane modele, po rzeczywiste systemy rozproszone. Rozważane systemy różnią się specyfiką problemów zarządzania zasobami oraz metodologią, którą jest dla tych problemów najbardziej adekwatna.Efektywne zarządzanie zasobami w systemach rozproszonych jest problemem o fundamentalnym znaczeniu. Systemy komputerowe wymagają dobrych mechanizmów zarządzania zasobami aby zapewnić odpowiednią jakość usług dla użytkowników. Również w naszym codziennym życiu często uczestniczymy w mechanizmach zarządzania zasobami. Przykłady takich mechanizmów to między innymi podział tortu na przyjęciu urodzinowym, czy referenda, a nawet wybory parlamentarne (w tym przypadku możemy utożsamiać kandydatów startujących w wyborach z zasobami).W pierwszej części rozprawy rozważamy ogólny, abstrakcyjny model który opisuje problem wyboru podzbioru pewnych obiektów, które następnie będą współdzielone przez grupę użytkowników. Ten model jest bardzo ogólny ponieważ nie specyfikujemy kim (lub czym) dokładnie jest użytkownik i czym dokładnie są owe obiekty. W rezultacie, rozwiązania oparte o ten model możemy zaaplikować do wielu rzeczywistych problemów, takich jak przydział studentów, w oparciu o ich preferencje, do uniwersyteckich kursów, czy znajdowanie właściwych rekomendacji. Takie rekomendacje mogą dotyczyć, na przykład, wyboru zbioru filmów dostępnych na pokładzie samolotu. Nasze algorytmy znajdują także zastosowanie w znajdowaniu proporcjonalnej reprezentacji dla grupy ludzi, czyli np. aby znaleźć zwycięzców w niektórych nowoczesnych systemach wyborów parlamentarnych. W niniejszej rozprawie analizujemy wiele specyficznych wariantów tego ogólnego zagadnienia .W drugiej części rozprawy rozważamy bardziej specyficzne modele opisujące systemy komputerowe. W tych modelach pojawiają się nowe elementy, takie jak zadania, procesory, czy sieć komputerowa. Każdy z tych elementów może być opisany przez zbiór parametrów: zadania mają swoje czasy powstania, wymagania zasobów, czy czasy wykonania. Długość trwania zadania może ponadto zależeć od rodzaju procesora na którym zadanie zostało uruchomione: procesory mogą być identyczne lub heterogeniczne. Połączenia sieciowe mogą być opisane przez przepustowość lub/i latencję komunikacji. Naturalnie w tych modelach zadajemy również bardziej specyficzne pytania. Pytamy jak uszeregować zadania, aby zminimalizować ich zagregowany czas zakończenia. Specyficzne warianty tego pytania różnią się w zależności od metody agregacji oraz w zależności od cech charakterystycznych wybranych elementów modelu. W rozważanych modelach badamy złożoność obliczeniową różnych wariantów problemu szeregowania, w szczególności pokazując efektywne algorytmy do optymalizacji uszeregowania zadań. W tej części rozprawy analizujemy również inne cechy naszych algorytmów, takie jak odporność na błędy czy (teorio-growa) stabilność. W ostatniej części rozprawy rozważamy problemy zarządzania zasobami w rzeczywistych, złożonych, komputerowych systemach rozproszonych. Rozważamy dwa rzeczywiste systemy przechowywania danych: HYDRAstor, który jest komercyjnym, rozproszonym, skalowalnym systemem przechowywania danych, oraz naszą prototypową implementację systemu do tworzenia kopii zapasowych danych, opartego o architekturę P2P. Wyjaśniamy czym różni się projektowanie mechanizmów zarządzania zasobami dla takich systemów od poprzednio rozważanych przypadków. W tej części prezentujemy relatywnie bardziej złożone mechanizmy zarządzania zasobami: mechanizmy te składają się z wielu elementów, a nawet z wielu podsystemów zarządzania zasobami. Co więcej takie podsystemy mogą mieć czasami sprzeczne ze sobą cele.

In this dissertation we take an algorithmic view on resource allocation problems in distributed systems. We present a comprehensive perspective by studying a variety of distributed systems---from abstract models of generic distributed systems, through more specific and detailed models, to real distributed computer systems. These systems differ with respect to the nature of the resource allocation problems and with respect to the methodologies required to effectively solve them.Effective resource allocation in distributed systems is a fundamental problem. Computer systems require good resource management mechanism to ensure expected functionality and expected quality of service. Even in our everyday life we often participate in resource allocation mechanisms. The examples range from cutting a cake at the birthday party to parliamentary elections and referendums (where the participating candidates can be viewed as resources).We start our discussion from considering a general computational model that describes the problem of selecting a collective set of items for the shared use by a group of agents. This model is very general; it does not specify what is an agent and what is an item, and, thus, can be applied to many different scenarios. Indeed, we show that our model captures many real-life resource allocation problems. For instance, our algorithms for this general model can be applied to recommendation systems, e.g., to select a collection of movies for a plane, or to allocate students to sport classes based on their preferences. Our algorithms are also applicable to the problem of finding a proportional representation of a society in some collective decision-making body, i.e., to find winners in some modern parliamentary election systems. We analyze multiple variants of our general problem of selecting a collective set of items. Next, we move to more specific models of computer systems. In these models we introduce several new elements such as jobs, processors, and the network. Each of these elements can be further described by a set of parameters. For instance, jobs have their release times, resource requirements, and durations; further, their durations might depend on the processors on which they are run; the processors might be identical or heterogeneous. The network connections can be described, e.g., by bandwidth and communication latencies. Consequently, in these models we focus on several variants of a more general problem. We ask how to schedule jobs to minimize their aggregated completion time, with specific variants of this question depending on the aggregation method and on the characteristics of the elements of the model. We establish computational complexity of variants of this scheduling problem and, in particular, we show effective algorithms optimizing jobs' schedules. We also provide analysis of other properties of our algorithms, such as their fault-tolerance and their game-theoretic stability.In the last part of this dissertation we consider resource allocation problems in real implementations of complex distributed systems. We consider two storage-based systems: HYDRAstor, which is a commercial, distributed, scalable, high-performance, secondary storage system targeted for the enterprise market, and our prototype implementation of a P2P backup system. We explain how the design of resource allocation mechanisms for such complex systems is different from our previous approaches. In this part we present and discuss relatively more complex resource allocation mechanisms; these mechanisms consist of multiple elements and even of whole resource allocation subsystems. Further, they aim at achieving multiple (sometimes contradicting) goals.