Communication heuristics in distributed combinatorial search algorithms View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1989

AUTHORS

Alfred Taudes

ABSTRACT

Algorithms for combinatorial search problems such as the travelling salesman problem, the polynomial problem or game-tree searching have been prime candidates for a distributed implementation as these problems offer substantial parallelism on the programm level. However, a number of experimental studies show that naive approaches to distributed combinatorial search tend to yield only a moderate speedup. The problem is to find a communication strategy that is able to limit stand-stills and superfluous searching of individual processors by distributing the work-load and intermediate results among the processors effectively and that causes only moderate communication overhead. To tackle the problem of the diffusion of commonly useful intermediate results between processors linked by “slow” communication lines without shared memory, we propose a formal method to derive optimal and adaptive communication strategies based on Dynamic Programming in Markov Chains. The key idea of our approach is to compare the running time to be expected under the current contents of the local copy of the shared state with the search and communication effort when acquiring the intermediate result of another processor via an exchange of messages. Using this method we study communication strategies for various distributed combinatorial search problems: for the distributed determination of the maximum of a vector, for a distibuted version of a simple variant of alpha-beta pruning, and for distributed branch and bound methods, where we examine the set partitioning problem. More... »

PAGES

268-279

Book

TITLE

Distributed Algorithms

ISBN

978-3-540-51687-3
978-3-540-46750-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-51687-5_49

DOI

http://dx.doi.org/10.1007/3-540-51687-5_49

DIMENSIONS

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


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/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Vienna University of Economics and Business", 
          "id": "https://www.grid.ac/institutes/grid.15788.33", 
          "name": [
            "Department of Applied Computer Science Institute of Information Processing and Information Economics, Vienna University of Economics and Business Administration, Augasse 2-6, A-1090\u00a0Vienna, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Taudes", 
        "givenName": "Alfred", 
        "id": "sg:person.010346251263.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010346251263.14"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0004-3702(75)90019-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014742214"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(75)90019-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014742214"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-16811-7_166", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022743669", 
          "https://doi.org/10.1007/3-540-16811-7_166"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01762110", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031777105", 
          "https://doi.org/10.1007/bf01762110"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01762110", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031777105", 
          "https://doi.org/10.1007/bf01762110"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1989", 
    "datePublishedReg": "1989-01-01", 
    "description": "Algorithms for combinatorial search problems such as the travelling salesman problem, the polynomial problem or game-tree searching have been prime candidates for a distributed implementation as these problems offer substantial parallelism on the programm level. However, a number of experimental studies show that naive approaches to distributed combinatorial search tend to yield only a moderate speedup. The problem is to find a communication strategy that is able to limit stand-stills and superfluous searching of individual processors by distributing the work-load and intermediate results among the processors effectively and that causes only moderate communication overhead. To tackle the problem of the diffusion of commonly useful intermediate results between processors linked by \u201cslow\u201d communication lines without shared memory, we propose a formal method to derive optimal and adaptive communication strategies based on Dynamic Programming in Markov Chains. The key idea of our approach is to compare the running time to be expected under the current contents of the local copy of the shared state with the search and communication effort when acquiring the intermediate result of another processor via an exchange of messages. Using this method we study communication strategies for various distributed combinatorial search problems: for the distributed determination of the maximum of a vector, for a distibuted version of a simple variant of alpha-beta pruning, and for distributed branch and bound methods, where we examine the set partitioning problem.", 
    "editor": [
      {
        "familyName": "Bermond", 
        "givenName": "Jean-Claude", 
        "type": "Person"
      }, 
      {
        "familyName": "Raynal", 
        "givenName": "Michel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-51687-5_49", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-51687-3", 
        "978-3-540-46750-2"
      ], 
      "name": "Distributed Algorithms", 
      "type": "Book"
    }, 
    "name": "Communication heuristics in distributed combinatorial search algorithms", 
    "pagination": "268-279", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-51687-5_49"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "672b06a17bb90064af18580c8e270b2a68fcc44f06e1d798565bb7ebc66d422f"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021653553"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-51687-5_49", 
      "https://app.dimensions.ai/details/publication/pub.1021653553"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T13:27", 
    "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_8664_00000256.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-51687-5_49"
  }
]
 

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-51687-5_49'

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-51687-5_49'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-51687-5_49'

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-51687-5_49'


 

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

81 TRIPLES      23 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-51687-5_49 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N58aeaaa8dd794850a6aa7f57ff5cca8e
4 schema:citation sg:pub.10.1007/3-540-16811-7_166
5 sg:pub.10.1007/bf01762110
6 https://doi.org/10.1016/0004-3702(75)90019-3
7 schema:datePublished 1989
8 schema:datePublishedReg 1989-01-01
9 schema:description Algorithms for combinatorial search problems such as the travelling salesman problem, the polynomial problem or game-tree searching have been prime candidates for a distributed implementation as these problems offer substantial parallelism on the programm level. However, a number of experimental studies show that naive approaches to distributed combinatorial search tend to yield only a moderate speedup. The problem is to find a communication strategy that is able to limit stand-stills and superfluous searching of individual processors by distributing the work-load and intermediate results among the processors effectively and that causes only moderate communication overhead. To tackle the problem of the diffusion of commonly useful intermediate results between processors linked by “slow” communication lines without shared memory, we propose a formal method to derive optimal and adaptive communication strategies based on Dynamic Programming in Markov Chains. The key idea of our approach is to compare the running time to be expected under the current contents of the local copy of the shared state with the search and communication effort when acquiring the intermediate result of another processor via an exchange of messages. Using this method we study communication strategies for various distributed combinatorial search problems: for the distributed determination of the maximum of a vector, for a distibuted version of a simple variant of alpha-beta pruning, and for distributed branch and bound methods, where we examine the set partitioning problem.
10 schema:editor Nd9822f8ca76a4845bf79340d079f9a88
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N4f29b579b2e44d0dbba9ba0d5737063c
15 schema:name Communication heuristics in distributed combinatorial search algorithms
16 schema:pagination 268-279
17 schema:productId N46ebf5ce0f8c4eb296361d9cac3862c9
18 N4be7b986520d43248c71af6516bb1194
19 Ndfcc2cd5204f4afa959765bf95b6b9bb
20 schema:publisher N005c00424ba44807823744eb297563f8
21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021653553
22 https://doi.org/10.1007/3-540-51687-5_49
23 schema:sdDatePublished 2019-04-15T13:27
24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
25 schema:sdPublisher Nd43d74bb18bd486f8ce8d3a388f2c926
26 schema:url http://link.springer.com/10.1007/3-540-51687-5_49
27 sgo:license sg:explorer/license/
28 sgo:sdDataset chapters
29 rdf:type schema:Chapter
30 N005c00424ba44807823744eb297563f8 schema:location Berlin, Heidelberg
31 schema:name Springer Berlin Heidelberg
32 rdf:type schema:Organisation
33 N330d3e0ef4e14bbfb00fe93a1e78b46c rdf:first N36a08f9956d3415ebf4b4c70909a4f62
34 rdf:rest rdf:nil
35 N36a08f9956d3415ebf4b4c70909a4f62 schema:familyName Raynal
36 schema:givenName Michel
37 rdf:type schema:Person
38 N46ebf5ce0f8c4eb296361d9cac3862c9 schema:name doi
39 schema:value 10.1007/3-540-51687-5_49
40 rdf:type schema:PropertyValue
41 N4be7b986520d43248c71af6516bb1194 schema:name readcube_id
42 schema:value 672b06a17bb90064af18580c8e270b2a68fcc44f06e1d798565bb7ebc66d422f
43 rdf:type schema:PropertyValue
44 N4f29b579b2e44d0dbba9ba0d5737063c schema:isbn 978-3-540-46750-2
45 978-3-540-51687-3
46 schema:name Distributed Algorithms
47 rdf:type schema:Book
48 N58aeaaa8dd794850a6aa7f57ff5cca8e rdf:first sg:person.010346251263.14
49 rdf:rest rdf:nil
50 Nb25fb807dc1d4bddb239cba0dd1b5c32 schema:familyName Bermond
51 schema:givenName Jean-Claude
52 rdf:type schema:Person
53 Nd43d74bb18bd486f8ce8d3a388f2c926 schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 Nd9822f8ca76a4845bf79340d079f9a88 rdf:first Nb25fb807dc1d4bddb239cba0dd1b5c32
56 rdf:rest N330d3e0ef4e14bbfb00fe93a1e78b46c
57 Ndfcc2cd5204f4afa959765bf95b6b9bb schema:name dimensions_id
58 schema:value pub.1021653553
59 rdf:type schema:PropertyValue
60 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
61 schema:name Information and Computing Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
64 schema:name Computer Software
65 rdf:type schema:DefinedTerm
66 sg:person.010346251263.14 schema:affiliation https://www.grid.ac/institutes/grid.15788.33
67 schema:familyName Taudes
68 schema:givenName Alfred
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010346251263.14
70 rdf:type schema:Person
71 sg:pub.10.1007/3-540-16811-7_166 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022743669
72 https://doi.org/10.1007/3-540-16811-7_166
73 rdf:type schema:CreativeWork
74 sg:pub.10.1007/bf01762110 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031777105
75 https://doi.org/10.1007/bf01762110
76 rdf:type schema:CreativeWork
77 https://doi.org/10.1016/0004-3702(75)90019-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014742214
78 rdf:type schema:CreativeWork
79 https://www.grid.ac/institutes/grid.15788.33 schema:alternateName Vienna University of Economics and Business
80 schema:name Department of Applied Computer Science Institute of Information Processing and Information Economics, Vienna University of Economics and Business Administration, Augasse 2-6, A-1090 Vienna, Austria
81 rdf:type schema:Organization
 




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


...