Fair k mutual exclusion algorithm for peer to peer systems

Vijay Anand Reddy, Prateek Mittal, Indranil Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

k-mutual exclusion is an important problem for resourceintensive peer-to-peer applications ranging from aggregation to file downloads. In order to be practically useful, k-mutual exclusion algorithms not only need to be safe and live, but they also need to be fair across hosts. We propose a new solution to the k-mutual exclusion problem that provides a notion of time-based fairness. Specifically, our algorithm attempts to minimize the spread of access time for the critical resource. While a client's access time is the time between it requesting and accessing the resource, the spread is defined as a system-wide metric that measures some notion of the variance of access times across a homogeneous host population, e.g., difference between max and mean. We analytically prove the correctness of our algorithm, and evaluate its fairness experimentally using simulations. Our evaluation under two settings - a LAN setting and a WAN based on the King latency data set - shows even with 100 hosts accessing one resource, the spread of access time is within 15 seconds.

Original languageEnglish (US)
Title of host publicationProceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008
Pages655-662
Number of pages8
DOIs
StatePublished - Sep 22 2008
Externally publishedYes
Event28th International Conference on Distributed Computing Systems, ICDCS 2008 - Beijing, China
Duration: Jul 17 2008Jul 20 2008

Publication series

NameProceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008

Other

Other28th International Conference on Distributed Computing Systems, ICDCS 2008
CountryChina
CityBeijing
Period7/17/087/20/08

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'Fair k mutual exclusion algorithm for peer to peer systems'. Together they form a unique fingerprint.

  • Cite this

    Reddy, V. A., Mittal, P., & Gupta, I. (2008). Fair k mutual exclusion algorithm for peer to peer systems. In Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008 (pp. 655-662). [4595939] (Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008). https://doi.org/10.1109/ICDCS.2008.76