Back to overview

Fair P2P Computing

English title Fair P2P Computing
Applicant Guerraoui Rachid
Number 113825
Funding scheme Project funding
Research institution Laboratoire de programmation distribuée EPFL - IC - IINFCOM - LPD
Institution of higher education EPF Lausanne - EPFL
Main discipline Information Technology
Start/End 01.01.2007 - 30.06.2010
Approved amount 121'150.00
Show all

Keywords (4)

Distributed systems; publish/subscribe; fairness; reliability

Lay Summary (English)

Lay summary
The last decade has seen an evolution of computing systems to allow a large number of computing units to interact and share resources. A characteristic of such systems is that the set of units, also called participants, is dynamically changing. Participants disconnect without any notice and typically exhibit a selfish behaviour.

In order to support the scalability of such systems and provide failure resilience, there is a trend to move from traditional client-server patterns to decentralized resource management schemes. Such schemes, as considered for instance in the context of grid and peer-to-peer computing, relies on each participant that benefits from the system to provide in turn some services to other participants. While current solutions have succeeded in managing resources in a dynamic setting, they still suffer from an uneven distribution of the workload in the system. In short, some participants with low demand might have to perform as much work as other participants with high demand for resources. This is especially important when offering resources is considered to be expensive as for instance in the context of mobile computing because communication adds significant costs in terms of energy consumed.

Since participants typically act in a selfish manner, an unfair distribution of workload can lead to a high churn in a dynamic system where processes abruptly disconnect whenever they perceive to perform too much work. Such behavior can significantly impact the reliability and scalability of a decentralized system.

Not surprisingly, the success of a scalable resource sharing system is closely coupled to how fair the system is perceived in sharing the workload for managing requested services. Roughly speaking, a fair distributed system will have to provide mechanisms that can link the benefits obtained from the system by a participant (user) to the work performed by the participant (the user's machine(s)) for the community. In short, a fair system would allocate work to participants as a function of how much they actually benefit from the system. The idea is appealing and rather intuitive. Understanding its ramifications is more challenging however.

This is exactly the challenge that this project aims to take up. The goal of this project is more precisely to understand the very notion of fairness in a decentralized environment and to design distributed algorithms that correspond to this notion.

We will focus on a specific, yet powerful context of the publish/subscribe interaction paradigm. According to this paradigm, processes publish events or subscribe to topics (or specific content) and expect to receive events accordingly.

Our goal will be to study fairness in this context, devise fair publish/subscribe dissemination algorithms and establish lower and upper bounds depicting the impact of fairness on QoS parameters such as reliability, message complexity and memory complexity. The expected outcome is of a theoretical nature but driven with practical motivations.
Direct link to Lay Summary Last update: 21.02.2013

Responsible applicant and co-applicants