Collaboration in distributed systems

Meer over het boek

Collaboration is essential for the success of various distributed systems, from robots playing soccer to ants in a colony. This thesis explores different forms of collaboration and the benefits of working together. The first part examines a version of the Gale-Shapley stable matching problem, where pairs of nodes have associated metric matching costs. Analyzing this through the Price of Anarchy (PoA) and Price of Stability (PoS), we establish tight bounds on both metrics while aiming to minimize the total cost of matched nodes. In the second part, we focus on mobile robots with limited capabilities. We prove that a gathering algorithm for n robots, which cannot communicate and have restricted visibility, operates with a polynomial runtime of T(n²). We also analyze n agents using finite automata searching a 2D grid for treasure, demonstrating that their limited communication allows them to locate the treasure optimally, even asynchronously. Additionally, we investigate the minimal number of ants required to find treasure under various model modifications. Finally, we study teamwork in systems designed to thwart collaboration, specifically examining the feasibility of a Sybil attack on online poker platforms using collaborating bots. Our findings indicate a linear increase in average gains with more bots deployed at play money tables. Overall, this dissertation highlights that effective collaboration can significantly enhanc