Round Robin Is Optimal for Fault-Tolerant Broadcasting on Wireless Networks View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001

AUTHORS

Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri

ABSTRACT

We study the completion time of broadcast operations on Static Ad-Hoc Wireless Networks in presence of unpredictable and dynamical faults. As for oblivious fault-tolerant distributed protocols, we provide an Ω(Dn) lower bound where n is the number of nodes of the network and D is the source eccentricity in the fault-free part of the network. Rather surprisingly, this lower bound implies that the simple Round-Robin protocol, working in O(Dn) time, is an optimal fault-tolerant oblivious protocol. Then, we demonstrate that networks of o(n/ log n) maximum in-degree admit faster oblivious protocols. Indeed, we derive an oblivious protocol having O(D minn, Δ log n) completion time on any network of maximum in-degree Δ. Finally, we address the question whether adaptive protocols can be faster than oblivious ones. We show that the answer is negative at least in the general setting: we indeed prove an Ω(Dn) lower bound when \( D = \Theta \left( {\sqrt n } \right) \). This clearly implies that no (adaptive) protocol can achieve, in general, o(Dn) completion time. More... »

PAGES

452-463

Book

TITLE

Algorithms — ESA 2001

ISBN

978-3-540-42493-2
978-3-540-44676-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44676-1_38

DOI

http://dx.doi.org/10.1007/3-540-44676-1_38

DIMENSIONS

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


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/1005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Communications Technologies", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Rome Tor Vergata", 
          "id": "https://www.grid.ac/institutes/grid.6530.0", 
          "name": [
            "Dipartimento di Matematica, Universit\u00e0 di Roma \u201cTor Vergata\u201d, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Clementi", 
        "givenName": "Andrea E. F.", 
        "id": "sg:person.011027660123.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Scienze dell\u2019Informazione, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Monti", 
        "givenName": "Angelo", 
        "id": "sg:person.013471123531.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013471123531.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Scienze dell\u2019Informazione, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Silvestri", 
        "givenName": "Riccardo", 
        "id": "sg:person.012430640403.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1109/tcom.1985.1096245", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061554033"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.1985.1057022", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061649139"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001", 
    "datePublishedReg": "2001-01-01", 
    "description": "We study the completion time of broadcast operations on Static Ad-Hoc Wireless Networks in presence of unpredictable and dynamical faults. As for oblivious fault-tolerant distributed protocols, we provide an \u03a9(Dn) lower bound where n is the number of nodes of the network and D is the source eccentricity in the fault-free part of the network. Rather surprisingly, this lower bound implies that the simple Round-Robin protocol, working in O(Dn) time, is an optimal fault-tolerant oblivious protocol. Then, we demonstrate that networks of o(n/ log n) maximum in-degree admit faster oblivious protocols. Indeed, we derive an oblivious protocol having O(D minn, \u0394 log n) completion time on any network of maximum in-degree \u0394. Finally, we address the question whether adaptive protocols can be faster than oblivious ones. We show that the answer is negative at least in the general setting: we indeed prove an \u03a9(Dn) lower bound when \\( D = \\Theta \\left( {\\sqrt n } \\right) \\). This clearly implies that no (adaptive) protocol can achieve, in general, o(Dn) completion time.", 
    "editor": [
      {
        "familyName": "auf der Heide", 
        "givenName": "Friedhelm Meyer", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44676-1_38", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42493-2", 
        "978-3-540-44676-7"
      ], 
      "name": "Algorithms \u2014 ESA 2001", 
      "type": "Book"
    }, 
    "name": "Round Robin Is Optimal for Fault-Tolerant Broadcasting on Wireless Networks", 
    "pagination": "452-463", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44676-1_38"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "aa1ad8d6273db0a0a7c5041ca0fb55e4923701b59a2706ae18d5adf7b95a841a"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035709034"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44676-1_38", 
      "https://app.dimensions.ai/details/publication/pub.1035709034"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T10:36", 
    "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_8659_00000265.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-44676-1_38"
  }
]
 

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-44676-1_38'

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-44676-1_38'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44676-1_38'

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-44676-1_38'


 

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

88 TRIPLES      23 PREDICATES      29 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44676-1_38 schema:about anzsrc-for:10
2 anzsrc-for:1005
3 schema:author N2078c04c194f42a4addac1096020f770
4 schema:citation https://doi.org/10.1109/tcom.1985.1096245
5 https://doi.org/10.1109/tit.1985.1057022
6 schema:datePublished 2001
7 schema:datePublishedReg 2001-01-01
8 schema:description We study the completion time of broadcast operations on Static Ad-Hoc Wireless Networks in presence of unpredictable and dynamical faults. As for oblivious fault-tolerant distributed protocols, we provide an Ω(Dn) lower bound where n is the number of nodes of the network and D is the source eccentricity in the fault-free part of the network. Rather surprisingly, this lower bound implies that the simple Round-Robin protocol, working in O(Dn) time, is an optimal fault-tolerant oblivious protocol. Then, we demonstrate that networks of o(n/ log n) maximum in-degree admit faster oblivious protocols. Indeed, we derive an oblivious protocol having O(D minn, Δ log n) completion time on any network of maximum in-degree Δ. Finally, we address the question whether adaptive protocols can be faster than oblivious ones. We show that the answer is negative at least in the general setting: we indeed prove an Ω(Dn) lower bound when \( D = \Theta \left( {\sqrt n } \right) \). This clearly implies that no (adaptive) protocol can achieve, in general, o(Dn) completion time.
9 schema:editor N84d44b438c944addb215d5a33d521fa3
10 schema:genre chapter
11 schema:inLanguage en
12 schema:isAccessibleForFree false
13 schema:isPartOf N55c418fc273b492a88ebb8fee05f941e
14 schema:name Round Robin Is Optimal for Fault-Tolerant Broadcasting on Wireless Networks
15 schema:pagination 452-463
16 schema:productId N60bf490538664e9b974fa3b56e798460
17 Nad6314aa37714f93a2a84c6b71d28cfe
18 Nf8dc5bcd68254303a3e1935e4b74393d
19 schema:publisher N7a0626a49d8244e899e6d75186990a70
20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035709034
21 https://doi.org/10.1007/3-540-44676-1_38
22 schema:sdDatePublished 2019-04-15T10:36
23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
24 schema:sdPublisher Nf903e6b4d9e54910ac1faab9e2aecaa1
25 schema:url http://link.springer.com/10.1007/3-540-44676-1_38
26 sgo:license sg:explorer/license/
27 sgo:sdDataset chapters
28 rdf:type schema:Chapter
29 N1d0d304d918a40499a895d196001f1e5 schema:familyName auf der Heide
30 schema:givenName Friedhelm Meyer
31 rdf:type schema:Person
32 N2078c04c194f42a4addac1096020f770 rdf:first sg:person.011027660123.21
33 rdf:rest N6ea2d71f0d624f318c77d08b1bcd3ba5
34 N33d229253d214ca18e071eeba8c00dac rdf:first sg:person.012430640403.64
35 rdf:rest rdf:nil
36 N55c418fc273b492a88ebb8fee05f941e schema:isbn 978-3-540-42493-2
37 978-3-540-44676-7
38 schema:name Algorithms — ESA 2001
39 rdf:type schema:Book
40 N60bf490538664e9b974fa3b56e798460 schema:name readcube_id
41 schema:value aa1ad8d6273db0a0a7c5041ca0fb55e4923701b59a2706ae18d5adf7b95a841a
42 rdf:type schema:PropertyValue
43 N6ea2d71f0d624f318c77d08b1bcd3ba5 rdf:first sg:person.013471123531.02
44 rdf:rest N33d229253d214ca18e071eeba8c00dac
45 N7a0626a49d8244e899e6d75186990a70 schema:location Berlin, Heidelberg
46 schema:name Springer Berlin Heidelberg
47 rdf:type schema:Organisation
48 N84d44b438c944addb215d5a33d521fa3 rdf:first N1d0d304d918a40499a895d196001f1e5
49 rdf:rest rdf:nil
50 Nad6314aa37714f93a2a84c6b71d28cfe schema:name doi
51 schema:value 10.1007/3-540-44676-1_38
52 rdf:type schema:PropertyValue
53 Nf8dc5bcd68254303a3e1935e4b74393d schema:name dimensions_id
54 schema:value pub.1035709034
55 rdf:type schema:PropertyValue
56 Nf903e6b4d9e54910ac1faab9e2aecaa1 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
59 schema:name Technology
60 rdf:type schema:DefinedTerm
61 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
62 schema:name Communications Technologies
63 rdf:type schema:DefinedTerm
64 sg:person.011027660123.21 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
65 schema:familyName Clementi
66 schema:givenName Andrea E. F.
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21
68 rdf:type schema:Person
69 sg:person.012430640403.64 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
70 schema:familyName Silvestri
71 schema:givenName Riccardo
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64
73 rdf:type schema:Person
74 sg:person.013471123531.02 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
75 schema:familyName Monti
76 schema:givenName Angelo
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013471123531.02
78 rdf:type schema:Person
79 https://doi.org/10.1109/tcom.1985.1096245 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061554033
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1109/tit.1985.1057022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061649139
82 rdf:type schema:CreativeWork
83 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
84 schema:name Dipartimento di Matematica, Università di Roma “Tor Vergata”, Italy
85 rdf:type schema:Organization
86 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
87 schema:name Dipartimento di Scienze dell’Informazione, Università di Roma “La Sapienza”, Italy
88 rdf:type schema:Organization
 




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


...