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

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
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

Fingerprint

Wide area networks
Local area networks
Agglomeration

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software

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

Fair k mutual exclusion algorithm for peer to peer systems. / Reddy, Vijay Anand; Mittal, Prateek; Gupta, Indranil.

Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008. 2008. p. 655-662 4595939 (Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008).

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

Reddy, VA, 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., 4595939, Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008, pp. 655-662, 28th International Conference on Distributed Computing Systems, ICDCS 2008, Beijing, China, 7/17/08. https://doi.org/10.1109/ICDCS.2008.76
Reddy VA, Mittal P, Gupta I. Fair k mutual exclusion algorithm for peer to peer systems. In Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008. 2008. p. 655-662. 4595939. (Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008). https://doi.org/10.1109/ICDCS.2008.76
Reddy, Vijay Anand ; Mittal, Prateek ; Gupta, Indranil. / Fair k mutual exclusion algorithm for peer to peer systems. Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008. 2008. pp. 655-662 (Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008).
@inproceedings{e92191647b6f4d19b6667f02a86144f1,
title = "Fair k mutual exclusion algorithm for peer to peer systems",
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.",
author = "Reddy, {Vijay Anand} and Prateek Mittal and Indranil Gupta",
year = "2008",
month = "9",
day = "22",
doi = "10.1109/ICDCS.2008.76",
language = "English (US)",
isbn = "9780769531724",
series = "Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008",
pages = "655--662",
booktitle = "Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008",

}

TY - GEN

T1 - Fair k mutual exclusion algorithm for peer to peer systems

AU - Reddy, Vijay Anand

AU - Mittal, Prateek

AU - Gupta, Indranil

PY - 2008/9/22

Y1 - 2008/9/22

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=51849104100&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51849104100&partnerID=8YFLogxK

U2 - 10.1109/ICDCS.2008.76

DO - 10.1109/ICDCS.2008.76

M3 - Conference contribution

AN - SCOPUS:51849104100

SN - 9780769531724

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

SP - 655

EP - 662

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

ER -