Analyse des systèmes distribués par théorie des jeux : conception et incitation
Institution:
Paris, Télécom ParisTechDisciplines:
Directors:
Abstract EN:
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 propose distributed optimization algorithms intended for practical implementation. First, we target backup services in peer-to-peer systems, i. E. , distributed networks of functionally 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. The spatial and ownership diversity of storage hosts assure the availability of backed up data. In order to ensure high quality service in such a peer-to-peer network we propose novel data redundancy and peer selection policies. Second, we examine the potential of a dynamic spectrum management framework that enables sequential allocation of frequency bands for wireless service providers. Our allocation and pricing design achieve efficient spectrum utilization and incentive-compatibility, considering physical interference among frequency licensees. Our work provides insights on emerging optimization problems related to the spectrum allocation. We propose heuristic algorithms that can be the cornerstones of a flexible distributed dynamic allocation system
Abstract FR:
Cette thèse présente les aspects d’incitation des systèmes distribués où une quantité limitée des ressources publiques ou privées doit être répartie parmi les participants égoïstes et autonomes. Notre objectif est de concevoir des mécanismes qui assurent l’efficacité et l’équité dans l’allocation des ressources dans de tels systèmes. Nous proposons des algorithmes d’optimisation distribués destinés à la mise en œuvre dans la pratique. Premièrement, nous ciblons les services de sauvegarde dans des systèmes pair-a-pair, c’est-a-dire des réseaux distribués constitués de pairs fonctionnellement égaux, où les utilisateurs sauvegardent leurs données sur les périphériques de stockage sous-utilisés d'autres utilisateurs à travers de l'internet. La diversité spatiale et propriétaire des hotes de stockage assurent la disponibilité des données sauvegardées. Afin d'assurer une haute qualité de service dans un tel réseau pair-a-pair, nous proposons de nouvelles politiques concernant la redondance de données et la sélection des pairs de stockage. Deuxièmement, nous examinons le potentiel de la gestion du spectre de façon dynamique qui permet d’allouer des bandes de radiofréquence séquentiellement pour les fournisseurs de service sans fil. Notre conception d’allocation et de tarification établissent l’utilisation efficace du spectre et la compatibilité avec des incitations, compte tenu de l’interférence physique entre les titulaires de fréquence. Notre travail donne un aperçu sur les nouveaux problèmes d’optimisation liés à la répartition du spectre. Nous proposons des algorithmes heuristiques qui peuvent être la fondation d’un système d’allocation dynamique distribué.