Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1999-01

AUTHORS

P. Krishnan, P. M. Long, J. S. Vitter

ABSTRACT

In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource for $1 per unit time or buy it once and for all for $c . In this paper we study algorithms that make a sequence of single rent-to-buy decisions, using the assumption that the resource use times are independently drawn from an unknown probability distribution. Our study of this rent-to-buy problem is motivated by important systems applications, specifically, problems arising from deciding when to spindown disks to conserve energy in mobile computers [4], [13], [15], thread blocking decisions during lock acquisition in multiprocessor applications [7], and virtual circuit holding times in IP-over-ATM networks [11], [19]. We develop a provably optimal and computationally efficient algorithm for the rent-to-buy problem. Our algorithm uses \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ O(\sqrt{t}) $ \end{document} time and space, and its expected cost for the t th resource use converges to optimal as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ O(\sqrt{ log t/t}) $ \end{document} , for any bounded probability distribution on the resource use times. Alternatively, using O(1) time and space, the algorithm almost converges to optimal. We describe the experimental results for the application of our algorithm to one of the motivating systems problems: the question of when to spindown a disk to save power in a mobile computer. Simulations using disk access traces obtained from an HP workstation environment suggest that our algorithm yields significantly improved power/ response time performance over the nonadaptive 2-competitive algorithm which is optimal in the worst-case competitive analysis model. More... »

PAGES

31-56

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/pl00009249

DOI

http://dx.doi.org/10.1007/pl00009249

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1001656938


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "Bell Laboratories, 101 Crawfords Corner Road, Holmdel, NJ 07733, USA. pk@research.bell-labs.com., US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Krishnan", 
        "givenName": "P.", 
        "id": "sg:person.013030315627.56", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013030315627.56"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National University of Singapore", 
          "id": "https://www.grid.ac/institutes/grid.4280.e", 
          "name": [
            "ISCS Department, National University of Singapore,  Singapore 119260, Republic of Singapore. plong@iscs.nus.sg., SG"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Long", 
        "givenName": "P. M.", 
        "id": "sg:person.0670067056.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0670067056.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, Durham, NC 27708-0129, USA. jsv@cs.duke.edu., US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "J. S.", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1999-01", 
    "datePublishedReg": "1999-01-01", 
    "description": "In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource for $1 per unit time or buy it once and for all for $c . In this paper we study algorithms that make a sequence of single rent-to-buy decisions, using the assumption that the resource use times are independently drawn from an unknown probability distribution. Our study of this rent-to-buy problem is motivated by important systems applications, specifically, problems arising from deciding when to spindown disks to conserve energy in mobile computers [4], [13], [15], thread blocking decisions during lock acquisition in multiprocessor applications [7], and virtual circuit holding times in IP-over-ATM networks [11], [19]. We develop a provably optimal and computationally efficient algorithm for the rent-to-buy problem. Our algorithm uses \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document} $ O(\\sqrt{t}) $ \\end{document} time and space, and its expected cost for the t th resource use converges to optimal as \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document} $ O(\\sqrt{ log t/t}) $ \\end{document} , for any bounded probability distribution on the resource use times. Alternatively, using O(1) time and space, the algorithm almost converges to optimal. We describe the experimental results for the application of our algorithm to one of the motivating systems problems: the question of when to spindown a disk to save power in a mobile computer. Simulations using disk access traces obtained from an HP workstation environment suggest that our algorithm yields significantly improved power/ response time performance over the nonadaptive 2-competitive algorithm which is optimal in the worst-case competitive analysis model.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/pl00009249", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "23"
      }
    ], 
    "name": "Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments", 
    "pagination": "31-56", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "07e46066551e3f204c5155d4bdeac52619073e75d95c0efab41e81bcc67b3171"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/pl00009249"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001656938"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/pl00009249", 
      "https://app.dimensions.ai/details/publication/pub.1001656938"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T15:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8663_00000509.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FPL00009249"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/pl00009249'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/pl00009249'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/pl00009249'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/pl00009249'


 

This table displays all metadata directly associated to this object as RDF triples.

80 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/pl00009249 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author Nb87cd737143346faa66535bbf7b1f729
4 schema:datePublished 1999-01
5 schema:datePublishedReg 1999-01-01
6 schema:description In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource for $1 per unit time or buy it once and for all for $c . In this paper we study algorithms that make a sequence of single rent-to-buy decisions, using the assumption that the resource use times are independently drawn from an unknown probability distribution. Our study of this rent-to-buy problem is motivated by important systems applications, specifically, problems arising from deciding when to spindown disks to conserve energy in mobile computers [4], [13], [15], thread blocking decisions during lock acquisition in multiprocessor applications [7], and virtual circuit holding times in IP-over-ATM networks [11], [19]. We develop a provably optimal and computationally efficient algorithm for the rent-to-buy problem. Our algorithm uses \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ O(\sqrt{t}) $ \end{document} time and space, and its expected cost for the t th resource use converges to optimal as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $ O(\sqrt{ log t/t}) $ \end{document} , for any bounded probability distribution on the resource use times. Alternatively, using O(1) time and space, the algorithm almost converges to optimal. We describe the experimental results for the application of our algorithm to one of the motivating systems problems: the question of when to spindown a disk to save power in a mobile computer. Simulations using disk access traces obtained from an HP workstation environment suggest that our algorithm yields significantly improved power/ response time performance over the nonadaptive 2-competitive algorithm which is optimal in the worst-case competitive analysis model.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N40e35c5770ce416186ba1813262d59ca
11 N97d618f8b3d1414996b6d5818d693164
12 sg:journal.1047644
13 schema:name Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments
14 schema:pagination 31-56
15 schema:productId Na8e5458c792d4f3fa511cd83e5d4333d
16 Nc9e8328bc74b4ae8899bf76fadba817b
17 Nf85512754641448d992474d108255a2e
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001656938
19 https://doi.org/10.1007/pl00009249
20 schema:sdDatePublished 2019-04-10T15:00
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N7b6ca0b99ff943588ba5eb1170d34e47
23 schema:url http://link.springer.com/10.1007%2FPL00009249
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N16440491a63c4017bf28a12c6c63914a rdf:first sg:person.0613677314.28
28 rdf:rest rdf:nil
29 N40e35c5770ce416186ba1813262d59ca schema:volumeNumber 23
30 rdf:type schema:PublicationVolume
31 N63d28cc0f2c544a3b4bbd09cdd2f1edc rdf:first sg:person.0670067056.62
32 rdf:rest N16440491a63c4017bf28a12c6c63914a
33 N7b6ca0b99ff943588ba5eb1170d34e47 schema:name Springer Nature - SN SciGraph project
34 rdf:type schema:Organization
35 N97d618f8b3d1414996b6d5818d693164 schema:issueNumber 1
36 rdf:type schema:PublicationIssue
37 Na8e5458c792d4f3fa511cd83e5d4333d schema:name dimensions_id
38 schema:value pub.1001656938
39 rdf:type schema:PropertyValue
40 Nb87cd737143346faa66535bbf7b1f729 rdf:first sg:person.013030315627.56
41 rdf:rest N63d28cc0f2c544a3b4bbd09cdd2f1edc
42 Nc028f836f5094dc7ab924176e0654855 schema:name Bell Laboratories, 101 Crawfords Corner Road, Holmdel, NJ 07733, USA. pk@research.bell-labs.com., US
43 rdf:type schema:Organization
44 Nc9e8328bc74b4ae8899bf76fadba817b schema:name readcube_id
45 schema:value 07e46066551e3f204c5155d4bdeac52619073e75d95c0efab41e81bcc67b3171
46 rdf:type schema:PropertyValue
47 Nf85512754641448d992474d108255a2e schema:name doi
48 schema:value 10.1007/pl00009249
49 rdf:type schema:PropertyValue
50 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
51 schema:name Mathematical Sciences
52 rdf:type schema:DefinedTerm
53 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
54 schema:name Applied Mathematics
55 rdf:type schema:DefinedTerm
56 sg:journal.1047644 schema:issn 0178-4617
57 1432-0541
58 schema:name Algorithmica
59 rdf:type schema:Periodical
60 sg:person.013030315627.56 schema:affiliation Nc028f836f5094dc7ab924176e0654855
61 schema:familyName Krishnan
62 schema:givenName P.
63 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013030315627.56
64 rdf:type schema:Person
65 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
66 schema:familyName Vitter
67 schema:givenName J. S.
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
69 rdf:type schema:Person
70 sg:person.0670067056.62 schema:affiliation https://www.grid.ac/institutes/grid.4280.e
71 schema:familyName Long
72 schema:givenName P. M.
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0670067056.62
74 rdf:type schema:Person
75 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
76 schema:name Department of Computer Science, Duke University, Durham, NC 27708-0129, USA. jsv@cs.duke.edu., US
77 rdf:type schema:Organization
78 https://www.grid.ac/institutes/grid.4280.e schema:alternateName National University of Singapore
79 schema:name ISCS Department, National University of Singapore, Singapore 119260, Republic of Singapore. plong@iscs.nus.sg., SG
80 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...