caa a22 4500 445805501 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9398-9 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9398-9 Topological Implications of Selfish Neighbor Selection in Unstructured Peer-to-Peer Networks [Elektronische Daten] [Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer] Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem. However, the selfish behavior of peers has aspects which go beyond resource sharing. This paper studies the effects on the topology of a P2P network if peers selfishly select the peers to connect to. In our model, a peer exploits locality properties in order to minimize the latency (or response times) of its lookup operations. At the same time, the peer aims at not having to maintain links to too many other peers in the system. By giving tight bounds on the price of anarchy, we show that the resulting topologies can be much worse than if peers collaborated. Moreover, the network may never stabilize, even in the absence of churn. Finally, we establish the complexity of Nash equilibria in our game theoretic model of P2P networks. Specifically, we prove that it is NP-hard to decide whether our game has a Nash equilibrium and can stabilize. Springer Science+Business Media, LLC, 2010 Game theory nationallicence Peer-to-peer nationallicence Price of anarchy nationallicence NP-hardness nationallicence Metric spaces nationallicence Moscibroda Thomas Distributed Systems Research Group, Microsoft Research, Redmond, USA aut Schmid Stefan Deutsche Telekom Laboratories and Technical University of Berlin, 10587, Berlin, Germany aut Wattenhofer Roger Computer Engineering and Networks Laboratory, ETH Zurich, 8092, Zurich, Switzerland aut Algorithmica Springer-Verlag 61/2(2011-10-01), 419-446 0178-4617 61:2<419 2011 61 453 https://doi.org/10.1007/s00453-010-9398-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9398-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Moscibroda Thomas Distributed Systems Research Group, Microsoft Research, Redmond, USA aut NATIONALLICENCE 700 1- Schmid Stefan Deutsche Telekom Laboratories and Technical University of Berlin, 10587, Berlin, Germany aut NATIONALLICENCE 700 1- Wattenhofer Roger Computer Engineering and Networks Laboratory, ETH Zurich, 8092, Zurich, Switzerland aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 419-446 0178-4617 61:2<419 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer