Proportionate progress: A notion of fairness in resource allocation

S. K. Baruah; N. K. Cohen; C. G. Plaxton; D. A. Varvel

Proportionate progress: A notion of fairness in resource allocation

S. K. Baruah
, N. K. Cohen
, C. G. Plaxton
, D. A. Varvel

Department of Computer Science & Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

57 Scopus citations

Abstract

We consider the problem of sharing multiple copies of some resource among various tasks. We introduce a new notion of temporal fairness based on proportionate progress, called P-fairness. We use this notion to design an algorithm that solves the multiple-resource periodic scheduling problem. We define a related problem and show how to solve it efficiently, which in turn leads to an efficient implementation of our scheduling algorithm. To our knowledge, this work represents the first non-trivial result concerning the multiple-resource scheduling of tasks that may make recurring requests.

Original language	English
Title of host publication	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
Publisher	Publ by ACM
Pages	345-353
Number of pages	9
ISBN (Print)	0897915917
State	Published - 1993
Event	Proceedings of the 25th Annual ACM Symposium on the Theory of Computing - San Diego, CA, USA Duration: May 16 1993 → May 18 1993

Publication series

Name	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0734-9025

Conference

Conference	Proceedings of the 25th Annual ACM Symposium on the Theory of Computing
City	San Diego, CA, USA
Period	05/16/93 → 05/18/93

Cite this

@inproceedings{0e043c88c69a405980434dc30c78613e,

title = "Proportionate progress: A notion of fairness in resource allocation",

abstract = "We consider the problem of sharing multiple copies of some resource among various tasks. We introduce a new notion of temporal fairness based on proportionate progress, called P-fairness. We use this notion to design an algorithm that solves the multiple-resource periodic scheduling problem. We define a related problem and show how to solve it efficiently, which in turn leads to an efficient implementation of our scheduling algorithm. To our knowledge, this work represents the first non-trivial result concerning the multiple-resource scheduling of tasks that may make recurring requests.",

author = "Baruah, \{S. K.\} and Cohen, \{N. K.\} and Plaxton, \{C. G.\} and Varvel, \{D. A.\}",

year = "1993",

language = "English",

isbn = "0897915917",

series = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Publ by ACM",

pages = "345--353",

booktitle = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

note = "Proceedings of the 25th Annual ACM Symposium on the Theory of Computing ; Conference date: 16-05-1993 Through 18-05-1993",

}

Baruah, SK, Cohen, NK, Plaxton, CG & Varvel, DA 1993, Proportionate progress: A notion of fairness in resource allocation. in Conference Proceedings of the Annual ACM Symposium on Theory of Computing. Conference Proceedings of the Annual ACM Symposium on Theory of Computing, Publ by ACM, pp. 345-353, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, San Diego, CA, USA, 05/16/93.

Proportionate progress: A notion of fairness in resource allocation. / Baruah, S. K.; Cohen, N. K.; Plaxton, C. G. et al.
Conference Proceedings of the Annual ACM Symposium on Theory of Computing. Publ by ACM, 1993. p. 345-353 (Conference Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Proportionate progress

T2 - Proceedings of the 25th Annual ACM Symposium on the Theory of Computing

AU - Baruah, S. K.

AU - Cohen, N. K.

AU - Plaxton, C. G.

AU - Varvel, D. A.

PY - 1993

Y1 - 1993

N2 - We consider the problem of sharing multiple copies of some resource among various tasks. We introduce a new notion of temporal fairness based on proportionate progress, called P-fairness. We use this notion to design an algorithm that solves the multiple-resource periodic scheduling problem. We define a related problem and show how to solve it efficiently, which in turn leads to an efficient implementation of our scheduling algorithm. To our knowledge, this work represents the first non-trivial result concerning the multiple-resource scheduling of tasks that may make recurring requests.

AB - We consider the problem of sharing multiple copies of some resource among various tasks. We introduce a new notion of temporal fairness based on proportionate progress, called P-fairness. We use this notion to design an algorithm that solves the multiple-resource periodic scheduling problem. We define a related problem and show how to solve it efficiently, which in turn leads to an efficient implementation of our scheduling algorithm. To our knowledge, this work represents the first non-trivial result concerning the multiple-resource scheduling of tasks that may make recurring requests.

UR - https://www.scopus.com/pages/publications/0027187278

M3 - Conference contribution

AN - SCOPUS:0027187278

SN - 0897915917

T3 - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 345

EP - 353

BT - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

PB - Publ by ACM

Y2 - 16 May 1993 through 18 May 1993

ER -

Proportionate progress: A notion of fairness in resource allocation

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this