Collaboration in Distributed Systems: Robots, Ants, and Matchings
1st Edition
Published on 29. June 2015
Book
V, 142 pages
978-3-86628-538-5 (ISBN)
Description
From robots playing soccer together, through ants ensuring the survival of their colony, to nodes in a peer-to-peer network, collaboration is a corner-stone of the success of many different kind of distributed systems. The goal of this thesis is to shed more light onto various kinds of collaboration, and the advantages that individuals get from working together with others.
In the first part of the thesis, we consider a version of the Gale-Shapley stable matching setting, where each pair of n nodes is associated with a metric matching cost and the preferences are determined with respect to these costs. This stable matching version is analyzed through the Price of Anarchy (PoA) and Price of Stability (PoS) lens with the objective of minimizing the total cost of matched nodes. We show tight bounds on the PoA and PoS in such matching settings.
In the second part of the dissertation, we examine various aspects of systems of mobile robots (or agents) with restricted capabilities. We consider n robots that cannot communicate with each other and have only limited visibility and prove that an existing gathering algorithm for such robots has polynomial runtime of T(n²). We then turn our view towards n agents controlled by finite automata that search a two-dimensional integer grid for a treasure while being able to communicate with each other in a very restricted manner. We show that their collaborative performance is sufficient to locate the treasure in an optimal time, even in an asynchronous setting. We also look at small, i.e., constant numbers of agents and give upper and lower bounds on the minimal number of ants sufficient to locate the treasure for various modifications of the model.
In the last part of the thesis, we focus on the power of teamwork in systems that actively try to prevent collaboration. We investigate the feasibility of a Sybil attack, where many fake identities are created in order to get an unfair advantage, against online poker platforms by implementing such an attack using collaborating automated players (bots). Due to ethical considerations, our bots were only deployed at play money tables, where we found a linear rise in the average gain when increasing the number of bots.
On the whole, the quintessence of this dissertation is that collaboration, when implemented properly, is a versatile and effective instrument to improve the performance of all kinds of distributed systems in various ways.
In the first part of the thesis, we consider a version of the Gale-Shapley stable matching setting, where each pair of n nodes is associated with a metric matching cost and the preferences are determined with respect to these costs. This stable matching version is analyzed through the Price of Anarchy (PoA) and Price of Stability (PoS) lens with the objective of minimizing the total cost of matched nodes. We show tight bounds on the PoA and PoS in such matching settings.
In the second part of the dissertation, we examine various aspects of systems of mobile robots (or agents) with restricted capabilities. We consider n robots that cannot communicate with each other and have only limited visibility and prove that an existing gathering algorithm for such robots has polynomial runtime of T(n²). We then turn our view towards n agents controlled by finite automata that search a two-dimensional integer grid for a treasure while being able to communicate with each other in a very restricted manner. We show that their collaborative performance is sufficient to locate the treasure in an optimal time, even in an asynchronous setting. We also look at small, i.e., constant numbers of agents and give upper and lower bounds on the minimal number of ants sufficient to locate the treasure for various modifications of the model.
In the last part of the thesis, we focus on the power of teamwork in systems that actively try to prevent collaboration. We investigate the feasibility of a Sybil attack, where many fake identities are created in order to get an unfair advantage, against online poker platforms by implementing such an attack using collaborating automated players (bots). Due to ethical considerations, our bots were only deployed at play money tables, where we found a linear rise in the average gain when increasing the number of bots.
On the whole, the quintessence of this dissertation is that collaboration, when implemented properly, is a versatile and effective instrument to improve the performance of all kinds of distributed systems in various ways.