Simple and optimal randomized fault-tolerant rumor spreading View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2016-04

AUTHORS

Benjamin Doerr, Carola Doerr, Shay Moran, Shlomo Moran

ABSTRACT

We revisit the classic problem of spreading a piece of information in a group of n fully connected processors. By suitably adding a small dose of randomness to the protocol of Gasieniec and Pelc (Parallel Comput 22:903–912, 1996), we derive for the first time protocols that (i) use a linear number of messages, (ii) are correct even when an arbitrary number of adversarially chosen processors does not participate in the process, and (iii) with high probability have the asymptotically optimal runtime of O(logn) when at least an arbitrarily small constant fraction of the processors are working. In addition, our protocols do not require that the system is synchronized nor that all processors are simultaneously woken up at time zero, they are fully based on push-operations, and they do not need an a priori estimate on the number of failed nodes. Our protocols thus overcome the typical disadvantages of the two known approaches, algorithms based on random gossip (typically needing a large number of messages due to their unorganized nature) and algorithms based on fair workload splitting (which are either not time-efficient or require intricate preprocessing steps plus synchronization). More... »

PAGES

89-104

References to SciGraph publications

  • 2000-09. Optimal Adaptive Broadcasting with a Bounded Fraction of Faulty Nodes in ALGORITHMICA
  • 1988-09. Ramanujan graphs in COMBINATORICA
  • 2009-09. Derandomized Constructions of k-Wise (Almost) Independent Permutations in ALGORITHMICA
  • 1999-01. On the Construction of Pseudorandom Permutations: Luby—Rackoff Revisited in JOURNAL OF CRYPTOLOGY
  • 1989-08. Initial failures in distributed computations in INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
  • 1998. “Balls into Bins” — A Simple and Tight Analysis in RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00446-014-0238-z

    DOI

    http://dx.doi.org/10.1007/s00446-014-0238-z

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "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": "\u00c9cole Polytechnique", 
              "id": "https://www.grid.ac/institutes/grid.10877.39", 
              "name": [
                "LIX, \u00c9cole Polytechnique, Palaiseau, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Doerr", 
            "givenName": "Benjamin", 
            "id": "sg:person.01327223002.89", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01327223002.89"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "French National Centre for Scientific Research", 
              "id": "https://www.grid.ac/institutes/grid.4444.0", 
              "name": [
                "Sorbonne Universit\u00e9s, UPMC Univ Paris 06, UMR 7606, LIP6, 75005, Paris, France", 
                "CNRS, UMR 7606, LIP6, 75005, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Doerr", 
            "givenName": "Carola", 
            "id": "sg:person.010360414373.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Max Planck Institute for Informatics", 
              "id": "https://www.grid.ac/institutes/grid.419528.3", 
              "name": [
                "Computer Science Department, Technion - Israel Institute of Technology, 32000, Haifa, Israel", 
                "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Moran", 
            "givenName": "Shay", 
            "id": "sg:person.015764722771.49", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015764722771.49"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Technion \u2013 Israel Institute of Technology", 
              "id": "https://www.grid.ac/institutes/grid.6451.6", 
              "name": [
                "Computer Science Department, Technion - Israel Institute of Technology, 32000, Haifa, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Moran", 
            "givenName": "Shlomo", 
            "id": "sg:person.016526215237.63", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016526215237.63"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s004530010030", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002180396", 
              "https://doi.org/10.1007/s004530010030"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01407859", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005321758", 
              "https://doi.org/10.1007/bf01407859"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01407859", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005321758", 
              "https://doi.org/10.1007/bf01407859"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(85)90059-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006274177"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00003817", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017452659", 
              "https://doi.org/10.1007/pl00003817"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-008-9267-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019520288", 
              "https://doi.org/10.1007/s00453-008-9267-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-008-9267-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019520288", 
              "https://doi.org/10.1007/s00453-008-9267-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/43921.43922", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028661815"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2213977.2214064", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035015752"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02126799", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036601821", 
              "https://doi.org/10.1007/bf02126799"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02126799", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036601821", 
              "https://doi.org/10.1007/bf02126799"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49543-6_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038366427", 
              "https://doi.org/10.1007/3-540-49543-6_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ipl.2010.11.006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039563235"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/inco.1994.1099", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042716041"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-8191(96)00023-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045425959"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.2008.924648", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061651989"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0147013", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062840489"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/9789814282673_0001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088792900"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.2000.892324", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093211058"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511813603", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098666463"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511581274", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098672101"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2016-04", 
        "datePublishedReg": "2016-04-01", 
        "description": "We revisit the classic problem of spreading a piece of information in a group of n fully connected processors. By suitably adding a small dose of randomness to the protocol of Gasieniec and Pelc (Parallel Comput 22:903\u2013912, 1996), we derive for the first time protocols that (i) use a linear number of messages, (ii) are correct even when an arbitrary number of adversarially chosen processors does not participate in the process, and (iii) with high probability have the asymptotically optimal runtime of O(logn) when at least an arbitrarily small constant fraction of the processors are working. In addition, our protocols do not require that the system is synchronized nor that all processors are simultaneously woken up at time zero, they are fully based on push-operations, and they do not need an a priori estimate on the number of failed nodes. Our protocols thus overcome the typical disadvantages of the two known approaches, algorithms based on random gossip (typically needing a large number of messages due to their unorganized nature) and algorithms based on fair workload splitting (which are either not time-efficient or require intricate preprocessing steps plus synchronization).", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00446-014-0238-z", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052621", 
            "issn": [
              "0178-2770", 
              "1432-0452"
            ], 
            "name": "Distributed Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "29"
          }
        ], 
        "name": "Simple and optimal randomized fault-tolerant rumor spreading", 
        "pagination": "89-104", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "f180b566183bb34c0ce3e9445a762f6c7bee488215ad1881ee7c8bba021c34fe"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00446-014-0238-z"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1050697039"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00446-014-0238-z", 
          "https://app.dimensions.ai/details/publication/pub.1050697039"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T15:47", 
        "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_00000491.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00446-014-0238-z"
      }
    ]
     

    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/s00446-014-0238-z'

    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/s00446-014-0238-z'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00446-014-0238-z'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00446-014-0238-z'


     

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

    153 TRIPLES      21 PREDICATES      45 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00446-014-0238-z schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N8a1b876452644c2fbaccdd741c286da9
    4 schema:citation sg:pub.10.1007/3-540-49543-6_13
    5 sg:pub.10.1007/bf01407859
    6 sg:pub.10.1007/bf02126799
    7 sg:pub.10.1007/pl00003817
    8 sg:pub.10.1007/s00453-008-9267-y
    9 sg:pub.10.1007/s004530010030
    10 https://doi.org/10.1006/inco.1994.1099
    11 https://doi.org/10.1016/0166-218x(85)90059-9
    12 https://doi.org/10.1016/0167-8191(96)00023-3
    13 https://doi.org/10.1016/j.ipl.2010.11.006
    14 https://doi.org/10.1017/cbo9780511581274
    15 https://doi.org/10.1017/cbo9780511813603
    16 https://doi.org/10.1109/sfcs.2000.892324
    17 https://doi.org/10.1109/tit.2008.924648
    18 https://doi.org/10.1137/0147013
    19 https://doi.org/10.1142/9789814282673_0001
    20 https://doi.org/10.1145/2213977.2214064
    21 https://doi.org/10.1145/43921.43922
    22 schema:datePublished 2016-04
    23 schema:datePublishedReg 2016-04-01
    24 schema:description We revisit the classic problem of spreading a piece of information in a group of n fully connected processors. By suitably adding a small dose of randomness to the protocol of Gasieniec and Pelc (Parallel Comput 22:903–912, 1996), we derive for the first time protocols that (i) use a linear number of messages, (ii) are correct even when an arbitrary number of adversarially chosen processors does not participate in the process, and (iii) with high probability have the asymptotically optimal runtime of O(logn) when at least an arbitrarily small constant fraction of the processors are working. In addition, our protocols do not require that the system is synchronized nor that all processors are simultaneously woken up at time zero, they are fully based on push-operations, and they do not need an a priori estimate on the number of failed nodes. Our protocols thus overcome the typical disadvantages of the two known approaches, algorithms based on random gossip (typically needing a large number of messages due to their unorganized nature) and algorithms based on fair workload splitting (which are either not time-efficient or require intricate preprocessing steps plus synchronization).
    25 schema:genre research_article
    26 schema:inLanguage en
    27 schema:isAccessibleForFree true
    28 schema:isPartOf N204cb90f6f7e467dacc5429f4ce55c3b
    29 N821d18822dd548f48d5b36e9cd3479a0
    30 sg:journal.1052621
    31 schema:name Simple and optimal randomized fault-tolerant rumor spreading
    32 schema:pagination 89-104
    33 schema:productId N33f830c791fc4deba07a4f1deab27ca4
    34 N71431bf6edf244e6965126eb33a13626
    35 N90a36d1afe384ad5bad93d478484c204
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050697039
    37 https://doi.org/10.1007/s00446-014-0238-z
    38 schema:sdDatePublished 2019-04-10T15:47
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher Ncdfaf29037ad404490eba0aa52ea6f04
    41 schema:url http://link.springer.com/10.1007/s00446-014-0238-z
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N204cb90f6f7e467dacc5429f4ce55c3b schema:issueNumber 2
    46 rdf:type schema:PublicationIssue
    47 N33f830c791fc4deba07a4f1deab27ca4 schema:name readcube_id
    48 schema:value f180b566183bb34c0ce3e9445a762f6c7bee488215ad1881ee7c8bba021c34fe
    49 rdf:type schema:PropertyValue
    50 N4f75235b62b547da938200605fda877e rdf:first sg:person.015764722771.49
    51 rdf:rest Nccbf14d7b9db4daf85c361c23887759a
    52 N71431bf6edf244e6965126eb33a13626 schema:name doi
    53 schema:value 10.1007/s00446-014-0238-z
    54 rdf:type schema:PropertyValue
    55 N74c14e51015d46839a7e7b465a54be6e rdf:first sg:person.010360414373.45
    56 rdf:rest N4f75235b62b547da938200605fda877e
    57 N821d18822dd548f48d5b36e9cd3479a0 schema:volumeNumber 29
    58 rdf:type schema:PublicationVolume
    59 N8a1b876452644c2fbaccdd741c286da9 rdf:first sg:person.01327223002.89
    60 rdf:rest N74c14e51015d46839a7e7b465a54be6e
    61 N90a36d1afe384ad5bad93d478484c204 schema:name dimensions_id
    62 schema:value pub.1050697039
    63 rdf:type schema:PropertyValue
    64 Nccbf14d7b9db4daf85c361c23887759a rdf:first sg:person.016526215237.63
    65 rdf:rest rdf:nil
    66 Ncdfaf29037ad404490eba0aa52ea6f04 schema:name Springer Nature - SN SciGraph project
    67 rdf:type schema:Organization
    68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Information and Computing Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Computation Theory and Mathematics
    73 rdf:type schema:DefinedTerm
    74 sg:journal.1052621 schema:issn 0178-2770
    75 1432-0452
    76 schema:name Distributed Computing
    77 rdf:type schema:Periodical
    78 sg:person.010360414373.45 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
    79 schema:familyName Doerr
    80 schema:givenName Carola
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45
    82 rdf:type schema:Person
    83 sg:person.01327223002.89 schema:affiliation https://www.grid.ac/institutes/grid.10877.39
    84 schema:familyName Doerr
    85 schema:givenName Benjamin
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01327223002.89
    87 rdf:type schema:Person
    88 sg:person.015764722771.49 schema:affiliation https://www.grid.ac/institutes/grid.419528.3
    89 schema:familyName Moran
    90 schema:givenName Shay
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015764722771.49
    92 rdf:type schema:Person
    93 sg:person.016526215237.63 schema:affiliation https://www.grid.ac/institutes/grid.6451.6
    94 schema:familyName Moran
    95 schema:givenName Shlomo
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016526215237.63
    97 rdf:type schema:Person
    98 sg:pub.10.1007/3-540-49543-6_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038366427
    99 https://doi.org/10.1007/3-540-49543-6_13
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/bf01407859 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005321758
    102 https://doi.org/10.1007/bf01407859
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/bf02126799 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036601821
    105 https://doi.org/10.1007/bf02126799
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/pl00003817 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017452659
    108 https://doi.org/10.1007/pl00003817
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/s00453-008-9267-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1019520288
    111 https://doi.org/10.1007/s00453-008-9267-y
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/s004530010030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002180396
    114 https://doi.org/10.1007/s004530010030
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1006/inco.1994.1099 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042716041
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1016/0166-218x(85)90059-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006274177
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1016/0167-8191(96)00023-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045425959
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1016/j.ipl.2010.11.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039563235
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1017/cbo9780511581274 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098672101
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1017/cbo9780511813603 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098666463
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1109/sfcs.2000.892324 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093211058
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1109/tit.2008.924648 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061651989
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1137/0147013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062840489
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.1142/9789814282673_0001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088792900
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.1145/2213977.2214064 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035015752
    137 rdf:type schema:CreativeWork
    138 https://doi.org/10.1145/43921.43922 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028661815
    139 rdf:type schema:CreativeWork
    140 https://www.grid.ac/institutes/grid.10877.39 schema:alternateName École Polytechnique
    141 schema:name LIX, École Polytechnique, Palaiseau, France
    142 rdf:type schema:Organization
    143 https://www.grid.ac/institutes/grid.419528.3 schema:alternateName Max Planck Institute for Informatics
    144 schema:name Computer Science Department, Technion - Israel Institute of Technology, 32000, Haifa, Israel
    145 Max Planck Institute for Informatics, Saarbrücken, Germany
    146 rdf:type schema:Organization
    147 https://www.grid.ac/institutes/grid.4444.0 schema:alternateName French National Centre for Scientific Research
    148 schema:name CNRS, UMR 7606, LIP6, 75005, Paris, France
    149 Sorbonne Universités, UPMC Univ Paris 06, UMR 7606, LIP6, 75005, Paris, France
    150 rdf:type schema:Organization
    151 https://www.grid.ac/institutes/grid.6451.6 schema:alternateName Technion – Israel Institute of Technology
    152 schema:name Computer Science Department, Technion - Israel Institute of Technology, 32000, Haifa, Israel
    153 rdf:type schema:Organization
     




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


    ...