Collaboration in Distributed Systems: Robots, Ants, and Matchings

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 (symmetric) 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. A simple example demonstrates that in the general case, the situation is hopeless, hence we restrict our attention to metric costs. Our first result is a tight bound of Θ(nlog(3/2)) on the PoA in such metric graphs. We then use the notion of α-stability, where a pair of unmatched nodes defect only if both can thereby reduce their costs by a factor greater than α ≥ 1. Our main result is an asymptotically tight trade-off, showing that with respect to α-stable matchings, the PoS is Θ ( nlog(1+ 1 2α ) ) . The proof is constructive: we present a simple algorithm that outputs an α-stable matching satisfying this bound. In the second part of the dissertation, we examine various aspects of systems of mobile robots (or agents) with restricted capabilities. We analyze an existing gathering algorithm for n robots that cannot communicate with each other and have only limited visibility, and show that the algorithm has polynomial runtime of Θ(n2). We then turn our view towards n agents controlled by finite automata that explore a two-dimensional integer grid while being able to communicate with each other in a very restricted manner. Their goal is to locate a treasure which is located in some cell at a distance D from the common starting point of all agents. Despite the restriction to constant-size memory, we show that their collaborative performance is sufficient to locate the treasure in an optimal time of O(D + D2/n) 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 aforementioned 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. For this purpose, we implemented a large-scale attack on a poker platform in which automated players (bots) collaborate to increase their chances of winning. Due to ethical considerations, our bots were only deployed at play money tables, where we found that there is a linear rise in the average gain when increasing the number of bots. We conjecture that the essence of our findings can be generalized to real money tables and conclude that it is indeed possible to benefit from such an attack and that poker platforms are in dire need of stronger countermeasures. 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.