Game Theoretic Analysis of Distributed Systems: Design and Incentives

ii This dissertation studies incentive aspects of distributed systems in which limited private or public resources must be allocated among selfish autonomic participants. Our goal is to design mechanisms which ensure the efficiency and fairness of resource allocation in such systems. We employ selfish user models and we investigate the results of our proposed schemes. We also design distributed optimization algorithms intended for practical implementation. First, we target backup services in peer-to-peer systems, i.e., distributed networks of func-tionally equal peers, where users save their backup data on the underutilized storage devices of one another over the Internet. As a main characteristic, no scalability problems arise since more users provide larger overall storage space and bandwidth. Furthermore, spatial and ownership diversity of storage hosts assure the availability of backed up data. However, the management of users not willing to share their local resources with other participants is extremely important to keep the system operational. Moreover, ensuring high quality of service in such a peer-to-peer network requires careful system design. Our novel data redundancy and peer selection policie