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 N21832528472e4e338d8f7cf62b97eda5
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 N5769ddc466a04121b8455fbf03563059
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N9b2ab0b725144b19a9eab0c06a615f8f
15 schema:name Communication heuristics in distributed combinatorial search algorithms
16 schema:pagination 268-279
17 schema:productId N05a8e949225047cdaa3ab12a44a8a1d8
18 N14575a5651294860871fbe0d7b5f5598
19 N19cbe996531f40358131804948153347
20 schema:publisher N8fb3aa0a8068431790c1390d647b599c
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 N8e6901698755420fb4d1c339ffb3f029
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 N05a8e949225047cdaa3ab12a44a8a1d8 schema:name readcube_id
31 schema:value 672b06a17bb90064af18580c8e270b2a68fcc44f06e1d798565bb7ebc66d422f
32 rdf:type schema:PropertyValue
33 N14575a5651294860871fbe0d7b5f5598 schema:name doi
34 schema:value 10.1007/3-540-51687-5_49
35 rdf:type schema:PropertyValue
36 N19cbe996531f40358131804948153347 schema:name dimensions_id
37 schema:value pub.1021653553
38 rdf:type schema:PropertyValue
39 N21832528472e4e338d8f7cf62b97eda5 rdf:first sg:person.010346251263.14
40 rdf:rest rdf:nil
41 N227dc6e9a9614ea59f2723b9caba087a rdf:first N420edf6c138243cf8743aef629d794ae
42 rdf:rest rdf:nil
43 N24d5b7ba5da249309ed80ce9dc8a9a69 schema:familyName Bermond
44 schema:givenName Jean-Claude
45 rdf:type schema:Person
46 N420edf6c138243cf8743aef629d794ae schema:familyName Raynal
47 schema:givenName Michel
48 rdf:type schema:Person
49 N5769ddc466a04121b8455fbf03563059 rdf:first N24d5b7ba5da249309ed80ce9dc8a9a69
50 rdf:rest N227dc6e9a9614ea59f2723b9caba087a
51 N8e6901698755420fb4d1c339ffb3f029 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 N8fb3aa0a8068431790c1390d647b599c schema:location Berlin, Heidelberg
54 schema:name Springer Berlin Heidelberg
55 rdf:type schema:Organisation
56 N9b2ab0b725144b19a9eab0c06a615f8f schema:isbn 978-3-540-46750-2
57 978-3-540-51687-3
58 schema:name Distributed Algorithms
59 rdf:type schema:Book
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)


...