Series in
Distributed Computing
edited by Roger Wattenhofer
Vol. 20
Tobias Langner
Collaboration in Distributed Systems:
Robots, Ants, and Matchings
1st edition/1. Aufl. 2015. V, 144 pages/Seiten,
€ 64,00.
ISBN 978-3-86628-538-5
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 Θ(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.
Keywords: Collaboration,
Distributed Systems, robots, ants, matchings, Price of
Anarchy (PoA), Price of Stability (PoS)
Direkt bestellen
bei / to order directly from: Hartung.Gorre@t-online.de
Series in Distributed Computing in
http://www.hartung-gorre.de
Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de
Hartung-Gorre Verlag / D-78465
Konstanz / Germany
Telefon: +49
(0) 7533 97227 Telefax: +49 (0) 7533
97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de