Deterministic Leader Election in $$O(D+\log n)$$ Time with Messages of Size O(1) View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016

AUTHORS

Arnaud Casteigts , Yves Métivier , John Michael Robson , Akka Zemmari

ABSTRACT

This paper presents a distributed algorithm, called \(\mathcal{STT}\), for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size \(O(\log n)\), where n is the number of processors. It elects a leader in \(O(D +\log n)\) rounds, where D is the diameter of the network, with messages of size O(1). Thus it has a bit round complexity of \(O(D +\log n)\). This substantially improves upon the best known algorithm whose bit round complexity is \(O(D\log n)\). In fact, using the lower bound by Kutten et al. [13] and a result of Dinitz and Solomon [8], we show that the bit round complexity of \(\mathcal{STT}\) is optimal (up to a constant factor), which is a step forward in understanding the interplay between time and message optimality for the election problem. Our algorithm requires no knowledge on the graph such as n or D. More... »

PAGES

16-28

References to SciGraph publications

  • 2015-08. Knowledge, level of symmetry, and time of leader election in DISTRIBUTED COMPUTING
  • 1990-03. One-bit algorithms in DISTRIBUTED COMPUTING
  • 1984-06. On the message complexity of distributed problems in INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
  • 2011. Trading Bit, Message, and Time Complexity of Distributed Algorithms in DISTRIBUTED COMPUTING
  • Book

    TITLE

    Distributed Computing

    ISBN

    978-3-662-53425-0
    978-3-662-53426-7

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-662-53426-7_2

    DOI

    http://dx.doi.org/10.1007/978-3-662-53426-7_2

    DIMENSIONS

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


    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": "University of Bordeaux", 
              "id": "https://www.grid.ac/institutes/grid.412041.2", 
              "name": [
                "Universit\u00e9 de Bordeaux - Bordeaux INP LaBRI, UMR CNRS 5800"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Casteigts", 
            "givenName": "Arnaud", 
            "id": "sg:person.014046062661.61", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014046062661.61"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Bordeaux", 
              "id": "https://www.grid.ac/institutes/grid.412041.2", 
              "name": [
                "Universit\u00e9 de Bordeaux - Bordeaux INP LaBRI, UMR CNRS 5800"
              ], 
              "type": "Organization"
            }, 
            "familyName": "M\u00e9tivier", 
            "givenName": "Yves", 
            "id": "sg:person.011253260611.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011253260611.27"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Bordeaux", 
              "id": "https://www.grid.ac/institutes/grid.412041.2", 
              "name": [
                "Universit\u00e9 de Bordeaux - Bordeaux INP LaBRI, UMR CNRS 5800"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Robson", 
            "givenName": "John Michael", 
            "id": "sg:person.015275030542.01", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015275030542.01"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Bordeaux", 
              "id": "https://www.grid.ac/institutes/grid.412041.2", 
              "name": [
                "Universit\u00e9 de Bordeaux - Bordeaux INP LaBRI, UMR CNRS 5800"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zemmari", 
            "givenName": "Akka", 
            "id": "sg:person.016353075212.37", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016353075212.37"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf00979869", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001142188", 
              "https://doi.org/10.1007/bf00979869"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2007.04.027", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003927287"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/28395.28421", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005789709"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/inco.1994.1002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010619041"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0743-7315(90)90074-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011438153"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-24100-0_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023437505", 
              "https://doi.org/10.1007/978-3-642-24100-0_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1326554.1326557", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027300092"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-014-0237-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038642630", 
              "https://doi.org/10.1007/s00446-014-0237-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(90)90187-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044391970"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01783661", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046270517", 
              "https://doi.org/10.1007/bf01783661"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01783661", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046270517", 
              "https://doi.org/10.1007/bf01783661"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.1983.1056620", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061648804"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2006.1639281", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093657531"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/0471478210", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098661292"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/0471478210", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098661292"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/0470072644", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098661409"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/0470072644", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098661409"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9781139168724", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098678976"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2016", 
        "datePublishedReg": "2016-01-01", 
        "description": "This paper presents a distributed algorithm, called \\(\\mathcal{STT}\\), for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size \\(O(\\log n)\\), where n is the number of processors. It elects a leader in \\(O(D +\\log n)\\) rounds, where D is the diameter of the network, with messages of size O(1). Thus it has a bit round complexity of \\(O(D +\\log n)\\). This substantially improves upon the best known algorithm whose bit round complexity is \\(O(D\\log n)\\). In fact, using the lower bound by Kutten et al.\u00a0[13] and a result of Dinitz and Solomon\u00a0[8], we show that the bit round complexity of \\(\\mathcal{STT}\\) is optimal (up\u00a0to a constant factor), which is a step forward in understanding the interplay between time and message optimality for the election problem. Our algorithm requires no knowledge on the graph such as n or D.", 
        "editor": [
          {
            "familyName": "Gavoille", 
            "givenName": "Cyril", 
            "type": "Person"
          }, 
          {
            "familyName": "Ilcinkas", 
            "givenName": "David", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-662-53426-7_2", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-662-53425-0", 
            "978-3-662-53426-7"
          ], 
          "name": "Distributed Computing", 
          "type": "Book"
        }, 
        "name": "Deterministic Leader Election in $$O(D+\\log n)$$ Time with Messages of Size O(1)", 
        "pagination": "16-28", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-662-53426-7_2"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "848f8460eefa78d4090c14343206b5a55fcf07275906577c8ac34659e5e34d90"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1027827245"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-662-53426-7_2", 
          "https://app.dimensions.ai/details/publication/pub.1027827245"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T12:32", 
        "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_8663_00000260.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-662-53426-7_2"
      }
    ]
     

    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/978-3-662-53426-7_2'

    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/978-3-662-53426-7_2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53426-7_2'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53426-7_2'


     

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

    140 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-662-53426-7_2 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Neceb0bff8551413081d36b5fbb849812
    4 schema:citation sg:pub.10.1007/978-3-642-24100-0_4
    5 sg:pub.10.1007/bf00979869
    6 sg:pub.10.1007/bf01783661
    7 sg:pub.10.1007/s00446-014-0237-0
    8 https://doi.org/10.1002/0470072644
    9 https://doi.org/10.1002/0471478210
    10 https://doi.org/10.1006/inco.1994.1002
    11 https://doi.org/10.1016/0020-0190(90)90187-3
    12 https://doi.org/10.1016/0743-7315(90)90074-y
    13 https://doi.org/10.1016/j.tcs.2007.04.027
    14 https://doi.org/10.1017/cbo9781139168724
    15 https://doi.org/10.1109/ipdps.2006.1639281
    16 https://doi.org/10.1109/tit.1983.1056620
    17 https://doi.org/10.1145/1326554.1326557
    18 https://doi.org/10.1145/28395.28421
    19 schema:datePublished 2016
    20 schema:datePublishedReg 2016-01-01
    21 schema:description This paper presents a distributed algorithm, called \(\mathcal{STT}\), for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size \(O(\log n)\), where n is the number of processors. It elects a leader in \(O(D +\log n)\) rounds, where D is the diameter of the network, with messages of size O(1). Thus it has a bit round complexity of \(O(D +\log n)\). This substantially improves upon the best known algorithm whose bit round complexity is \(O(D\log n)\). In fact, using the lower bound by Kutten et al. [13] and a result of Dinitz and Solomon [8], we show that the bit round complexity of \(\mathcal{STT}\) is optimal (up to a constant factor), which is a step forward in understanding the interplay between time and message optimality for the election problem. Our algorithm requires no knowledge on the graph such as n or D.
    22 schema:editor N2c1cf97af42a46c18b2d8e98fe09066c
    23 schema:genre chapter
    24 schema:inLanguage en
    25 schema:isAccessibleForFree false
    26 schema:isPartOf N2fcce38c22da4859808221f675b2f162
    27 schema:name Deterministic Leader Election in $$O(D+\log n)$$ Time with Messages of Size O(1)
    28 schema:pagination 16-28
    29 schema:productId N3415403cefe54a51a002ed6135ba1f8c
    30 N88f4204430c040a1aaaec94704f8dbbf
    31 N90f1a51eeb664774bf474dcbbe8933ae
    32 schema:publisher N242750647b2849459d65c7a6922fdc1f
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027827245
    34 https://doi.org/10.1007/978-3-662-53426-7_2
    35 schema:sdDatePublished 2019-04-15T12:32
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher Na3589f3d395f4ad3b0fe888b81e4a53b
    38 schema:url http://link.springer.com/10.1007/978-3-662-53426-7_2
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset chapters
    41 rdf:type schema:Chapter
    42 N08fbf2b128b94ec585367ffd4e4e1f94 schema:familyName Gavoille
    43 schema:givenName Cyril
    44 rdf:type schema:Person
    45 N242750647b2849459d65c7a6922fdc1f schema:location Berlin, Heidelberg
    46 schema:name Springer Berlin Heidelberg
    47 rdf:type schema:Organisation
    48 N253f147d254a4b4c885771abbb91fdfd rdf:first sg:person.015275030542.01
    49 rdf:rest N2f5fcb0bdd864466b22ba2e6a45e616f
    50 N2c1cf97af42a46c18b2d8e98fe09066c rdf:first N08fbf2b128b94ec585367ffd4e4e1f94
    51 rdf:rest N9fb782a7273c4280868e7aa6e5b201b3
    52 N2f5fcb0bdd864466b22ba2e6a45e616f rdf:first sg:person.016353075212.37
    53 rdf:rest rdf:nil
    54 N2fcce38c22da4859808221f675b2f162 schema:isbn 978-3-662-53425-0
    55 978-3-662-53426-7
    56 schema:name Distributed Computing
    57 rdf:type schema:Book
    58 N3415403cefe54a51a002ed6135ba1f8c schema:name doi
    59 schema:value 10.1007/978-3-662-53426-7_2
    60 rdf:type schema:PropertyValue
    61 N88f4204430c040a1aaaec94704f8dbbf schema:name readcube_id
    62 schema:value 848f8460eefa78d4090c14343206b5a55fcf07275906577c8ac34659e5e34d90
    63 rdf:type schema:PropertyValue
    64 N90f1a51eeb664774bf474dcbbe8933ae schema:name dimensions_id
    65 schema:value pub.1027827245
    66 rdf:type schema:PropertyValue
    67 N9fb782a7273c4280868e7aa6e5b201b3 rdf:first Nf195e6b198e64d88b10da29558433840
    68 rdf:rest rdf:nil
    69 Na3589f3d395f4ad3b0fe888b81e4a53b schema:name Springer Nature - SN SciGraph project
    70 rdf:type schema:Organization
    71 Neceb0bff8551413081d36b5fbb849812 rdf:first sg:person.014046062661.61
    72 rdf:rest Nfc1c9e32b2ca4fd784e6939fa3e1a1d9
    73 Nf195e6b198e64d88b10da29558433840 schema:familyName Ilcinkas
    74 schema:givenName David
    75 rdf:type schema:Person
    76 Nfc1c9e32b2ca4fd784e6939fa3e1a1d9 rdf:first sg:person.011253260611.27
    77 rdf:rest N253f147d254a4b4c885771abbb91fdfd
    78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Information and Computing Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Computation Theory and Mathematics
    83 rdf:type schema:DefinedTerm
    84 sg:person.011253260611.27 schema:affiliation https://www.grid.ac/institutes/grid.412041.2
    85 schema:familyName Métivier
    86 schema:givenName Yves
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011253260611.27
    88 rdf:type schema:Person
    89 sg:person.014046062661.61 schema:affiliation https://www.grid.ac/institutes/grid.412041.2
    90 schema:familyName Casteigts
    91 schema:givenName Arnaud
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014046062661.61
    93 rdf:type schema:Person
    94 sg:person.015275030542.01 schema:affiliation https://www.grid.ac/institutes/grid.412041.2
    95 schema:familyName Robson
    96 schema:givenName John Michael
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015275030542.01
    98 rdf:type schema:Person
    99 sg:person.016353075212.37 schema:affiliation https://www.grid.ac/institutes/grid.412041.2
    100 schema:familyName Zemmari
    101 schema:givenName Akka
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016353075212.37
    103 rdf:type schema:Person
    104 sg:pub.10.1007/978-3-642-24100-0_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023437505
    105 https://doi.org/10.1007/978-3-642-24100-0_4
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/bf00979869 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001142188
    108 https://doi.org/10.1007/bf00979869
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/bf01783661 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046270517
    111 https://doi.org/10.1007/bf01783661
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/s00446-014-0237-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038642630
    114 https://doi.org/10.1007/s00446-014-0237-0
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1002/0470072644 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098661409
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1002/0471478210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098661292
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1006/inco.1994.1002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010619041
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1016/0020-0190(90)90187-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044391970
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1016/0743-7315(90)90074-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1011438153
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1016/j.tcs.2007.04.027 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003927287
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1017/cbo9781139168724 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098678976
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1109/ipdps.2006.1639281 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093657531
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1109/tit.1983.1056620 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061648804
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.1145/1326554.1326557 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027300092
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.1145/28395.28421 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005789709
    137 rdf:type schema:CreativeWork
    138 https://www.grid.ac/institutes/grid.412041.2 schema:alternateName University of Bordeaux
    139 schema:name Université de Bordeaux - Bordeaux INP LaBRI, UMR CNRS 5800
    140 rdf:type schema:Organization
     




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


    ...