Adaptability and the Usefulness of Hints (Extended Abstract) View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1998

AUTHORS

Piotr Berman , Juan A. Garay

ABSTRACT

In this paper we study the problem of designing algorithms in situations where there is some information concerning the typical conditions that are encountered when the respective problem is solved. The basic goal is to assure efficient performance in the typical case, while satisfying the correctness requirements in every case. We introduce adaptability, a new measure for the quality of an algorithm, which generalizes competitive analysis and related frameworks. This new notion applies to sequential, parallel and distributed algorithms alike.In a nutshell, a “hint” function conveys certain information about the environment in which the algorithm operates. Adaptability compares the performance of the algorithm against the “specialist”—an algorithm specifically tuned to the particular hint value. From this perspective, finding that no single algorithm can adapt to all possible hint values is not necessarily a negative result, provided that a family of specialists can be constructed.Our case studies provide examples of both kinds. We first consider the “ancient” problem of on-line scheduling of jobs in m identical processors, and show that no algorithm can fully adapt to the natural hint of largest job size. In particular, for the cases m = 2, 3, we present specialists that beat the general lower bound for on-line makespan.In the domain of distributed computing, we analyze the Distributed Consensus problem under several hint functions. To fulfill the requirements of one of the cases we consider, we present the first consensus algorithm that is simultaneously optimal in number of processors, early-stopping property (that is, it runs in time proportional to the actual number of faults), and total number of communicated bits. In our new parlance, the algorithm adapts to the number of faults hint with both running time and communication. More... »

PAGES

271-282

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-68530-8_23

DOI

http://dx.doi.org/10.1007/3-540-68530-8_23

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computer Science Department Pond Lab, The Pennsylvania State University, 16802, University Park, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Computer Science Department Pond Lab, The Pennsylvania State University, 16802, University Park, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Bell Laboratories, Information Sciences Research Center, 600 Mountain Ave, 07974, Murray Hill, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.469490.6", 
          "name": [
            "Bell Laboratories, Information Sciences Research Center, 600 Mountain Ave, 07974, Murray Hill, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Garay", 
        "givenName": "Juan A.", 
        "id": "sg:person.015655737162.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015655737162.07"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "In this paper we study the problem of designing algorithms in situations where there is some information concerning the typical conditions that are encountered when the respective problem is solved. The basic goal is to assure efficient performance in the typical case, while satisfying the correctness requirements in every case. We introduce adaptability, a new measure for the quality of an algorithm, which generalizes competitive analysis and related frameworks. This new notion applies to sequential, parallel and distributed algorithms alike.In a nutshell, a \u201chint\u201d function conveys certain information about the environment in which the algorithm operates. Adaptability compares the performance of the algorithm against the \u201cspecialist\u201d\u2014an algorithm specifically tuned to the particular hint value. From this perspective, finding that no single algorithm can adapt to all possible hint values is not necessarily a negative result, provided that a family of specialists can be constructed.Our case studies provide examples of both kinds. We first consider the \u201cancient\u201d problem of on-line scheduling of jobs in m identical processors, and show that no algorithm can fully adapt to the natural hint of largest job size. In particular, for the cases m = 2, 3, we present specialists that beat the general lower bound for on-line makespan.In the domain of distributed computing, we analyze the Distributed Consensus problem under several hint functions. To fulfill the requirements of one of the cases we consider, we present the first consensus algorithm that is simultaneously optimal in number of processors, early-stopping property (that is, it runs in time proportional to the actual number of faults), and total number of communicated bits. In our new parlance, the algorithm adapts to the number of faults hint with both running time and communication.", 
    "editor": [
      {
        "familyName": "Bilardi", 
        "givenName": "Gianfranco", 
        "type": "Person"
      }, 
      {
        "familyName": "Italiano", 
        "givenName": "Giuseppe F.", 
        "type": "Person"
      }, 
      {
        "familyName": "Pietracaprina", 
        "givenName": "Andrea", 
        "type": "Person"
      }, 
      {
        "familyName": "Pucci", 
        "givenName": "Geppino", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-68530-8_23", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64848-2", 
        "978-3-540-68530-2"
      ], 
      "name": "Algorithms \u2014 ESA\u2019 98", 
      "type": "Book"
    }, 
    "keywords": [
      "number of processors", 
      "hint value", 
      "Distributed Computing", 
      "number of faults", 
      "correctness requirements", 
      "consensus algorithm", 
      "algorithm adapts", 
      "single algorithm", 
      "identical processors", 
      "line scheduling", 
      "consensus problem", 
      "related frameworks", 
      "algorithm", 
      "largest job size", 
      "respective problems", 
      "competitive analysis", 
      "job sizes", 
      "efficient performance", 
      "certain information", 
      "processors", 
      "new notion", 
      "adaptability", 
      "computing", 
      "basic goal", 
      "requirements", 
      "information", 
      "makespan", 
      "case study", 
      "scheduling", 
      "performance", 
      "bits", 
      "communication", 
      "framework", 
      "adapts", 
      "hints", 
      "new measure", 
      "environment", 
      "nutshell", 
      "faults", 
      "number", 
      "jobs", 
      "domain", 
      "goal", 
      "specialists", 
      "kind", 
      "typical case", 
      "example", 
      "quality", 
      "situation", 
      "usefulness", 
      "notion", 
      "time", 
      "function", 
      "cases", 
      "perspective", 
      "results", 
      "total number", 
      "parlance", 
      "measures", 
      "analysis", 
      "values", 
      "size", 
      "typical conditions", 
      "properties", 
      "conditions", 
      "study", 
      "negative results", 
      "family", 
      "problem", 
      "paper"
    ], 
    "name": "Adaptability and the Usefulness of Hints (Extended Abstract)", 
    "pagination": "271-282", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009493733"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-68530-8_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-68530-8_23", 
      "https://app.dimensions.ai/details/publication/pub.1009493733"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_195.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-68530-8_23"
  }
]
 

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/3-540-68530-8_23'

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/3-540-68530-8_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-68530-8_23'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-68530-8_23'


 

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

154 TRIPLES      22 PREDICATES      95 URIs      88 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-68530-8_23 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N60a21b4960c44fb4880c7491e722439d
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description In this paper we study the problem of designing algorithms in situations where there is some information concerning the typical conditions that are encountered when the respective problem is solved. The basic goal is to assure efficient performance in the typical case, while satisfying the correctness requirements in every case. We introduce adaptability, a new measure for the quality of an algorithm, which generalizes competitive analysis and related frameworks. This new notion applies to sequential, parallel and distributed algorithms alike.In a nutshell, a “hint” function conveys certain information about the environment in which the algorithm operates. Adaptability compares the performance of the algorithm against the “specialist”—an algorithm specifically tuned to the particular hint value. From this perspective, finding that no single algorithm can adapt to all possible hint values is not necessarily a negative result, provided that a family of specialists can be constructed.Our case studies provide examples of both kinds. We first consider the “ancient” problem of on-line scheduling of jobs in m identical processors, and show that no algorithm can fully adapt to the natural hint of largest job size. In particular, for the cases m = 2, 3, we present specialists that beat the general lower bound for on-line makespan.In the domain of distributed computing, we analyze the Distributed Consensus problem under several hint functions. To fulfill the requirements of one of the cases we consider, we present the first consensus algorithm that is simultaneously optimal in number of processors, early-stopping property (that is, it runs in time proportional to the actual number of faults), and total number of communicated bits. In our new parlance, the algorithm adapts to the number of faults hint with both running time and communication.
7 schema:editor Nfb023932e27c4c1e8eb5ada7498180bb
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nfd275b5fb510400c977097040456d484
11 schema:keywords Distributed Computing
12 adaptability
13 adapts
14 algorithm
15 algorithm adapts
16 analysis
17 basic goal
18 bits
19 case study
20 cases
21 certain information
22 communication
23 competitive analysis
24 computing
25 conditions
26 consensus algorithm
27 consensus problem
28 correctness requirements
29 domain
30 efficient performance
31 environment
32 example
33 family
34 faults
35 framework
36 function
37 goal
38 hint value
39 hints
40 identical processors
41 information
42 job sizes
43 jobs
44 kind
45 largest job size
46 line scheduling
47 makespan
48 measures
49 negative results
50 new measure
51 new notion
52 notion
53 number
54 number of faults
55 number of processors
56 nutshell
57 paper
58 parlance
59 performance
60 perspective
61 problem
62 processors
63 properties
64 quality
65 related frameworks
66 requirements
67 respective problems
68 results
69 scheduling
70 single algorithm
71 situation
72 size
73 specialists
74 study
75 time
76 total number
77 typical case
78 typical conditions
79 usefulness
80 values
81 schema:name Adaptability and the Usefulness of Hints (Extended Abstract)
82 schema:pagination 271-282
83 schema:productId N8b4280295cd04dea8e4ce15e6fdf30fe
84 N9c841051e2c84f9fa68f86fe7f521ae1
85 schema:publisher N05056bf6063e49fc88d54da0ba35a0b7
86 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009493733
87 https://doi.org/10.1007/3-540-68530-8_23
88 schema:sdDatePublished 2022-08-04T17:16
89 schema:sdLicense https://scigraph.springernature.com/explorer/license/
90 schema:sdPublisher N35c80a30b10844d49c5bbdfb109cbcf8
91 schema:url https://doi.org/10.1007/3-540-68530-8_23
92 sgo:license sg:explorer/license/
93 sgo:sdDataset chapters
94 rdf:type schema:Chapter
95 N05056bf6063e49fc88d54da0ba35a0b7 schema:name Springer Nature
96 rdf:type schema:Organisation
97 N31d2196aa7b64e3394edf6bc444d530e schema:familyName Italiano
98 schema:givenName Giuseppe F.
99 rdf:type schema:Person
100 N35c80a30b10844d49c5bbdfb109cbcf8 schema:name Springer Nature - SN SciGraph project
101 rdf:type schema:Organization
102 N3d43323d91f443fa96851b63eb6f8567 rdf:first N4f2380baecf04a6ebaf4119ab40e9700
103 rdf:rest rdf:nil
104 N4eaf90eb85ad41acae8c10c2ca7742af rdf:first Ne06da5f4a1ae47339826a715c6354596
105 rdf:rest N3d43323d91f443fa96851b63eb6f8567
106 N4f2380baecf04a6ebaf4119ab40e9700 schema:familyName Pucci
107 schema:givenName Geppino
108 rdf:type schema:Person
109 N56683ea76309436ca832a291ed7637bf rdf:first N31d2196aa7b64e3394edf6bc444d530e
110 rdf:rest N4eaf90eb85ad41acae8c10c2ca7742af
111 N60a21b4960c44fb4880c7491e722439d rdf:first sg:person.01274506210.27
112 rdf:rest Nabf41eff79144b1391de464c341fad1a
113 N8b4280295cd04dea8e4ce15e6fdf30fe schema:name doi
114 schema:value 10.1007/3-540-68530-8_23
115 rdf:type schema:PropertyValue
116 N9c841051e2c84f9fa68f86fe7f521ae1 schema:name dimensions_id
117 schema:value pub.1009493733
118 rdf:type schema:PropertyValue
119 Na7cad367e6864cfead7d3cb7bb03168b schema:familyName Bilardi
120 schema:givenName Gianfranco
121 rdf:type schema:Person
122 Nabf41eff79144b1391de464c341fad1a rdf:first sg:person.015655737162.07
123 rdf:rest rdf:nil
124 Ne06da5f4a1ae47339826a715c6354596 schema:familyName Pietracaprina
125 schema:givenName Andrea
126 rdf:type schema:Person
127 Nfb023932e27c4c1e8eb5ada7498180bb rdf:first Na7cad367e6864cfead7d3cb7bb03168b
128 rdf:rest N56683ea76309436ca832a291ed7637bf
129 Nfd275b5fb510400c977097040456d484 schema:isbn 978-3-540-64848-2
130 978-3-540-68530-2
131 schema:name Algorithms — ESA’ 98
132 rdf:type schema:Book
133 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
134 schema:name Information and Computing Sciences
135 rdf:type schema:DefinedTerm
136 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
137 schema:name Computation Theory and Mathematics
138 rdf:type schema:DefinedTerm
139 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
140 schema:familyName Berman
141 schema:givenName Piotr
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
143 rdf:type schema:Person
144 sg:person.015655737162.07 schema:affiliation grid-institutes:grid.469490.6
145 schema:familyName Garay
146 schema:givenName Juan A.
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015655737162.07
148 rdf:type schema:Person
149 grid-institutes:grid.29857.31 schema:alternateName Computer Science Department Pond Lab, The Pennsylvania State University, 16802, University Park, USA
150 schema:name Computer Science Department Pond Lab, The Pennsylvania State University, 16802, University Park, USA
151 rdf:type schema:Organization
152 grid-institutes:grid.469490.6 schema:alternateName Bell Laboratories, Information Sciences Research Center, 600 Mountain Ave, 07974, Murray Hill, NJ, USA
153 schema:name Bell Laboratories, Information Sciences Research Center, 600 Mountain Ave, 07974, Murray Hill, NJ, USA
154 rdf:type schema:Organization
 




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


...