Finding the extrema of a distributed multiset View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1994

AUTHORS

P. Alimonti , P. Flocchini , N. Santoro

ABSTRACT

We consider the problem of finding the extrema of a distributed multiset in a ring; that is, of determining the minimum and the maximum values, x min and x max, of a multiset X={x 0, x2, ..., x n}-1}, whose elements are drawn from a totally ordered universe U and stored at the n entities of a ring network. This problem is unsolvable if the ring size is not known to the entities, and has complexity θ(n 2) in the case of asynchronous rings of known size. We show that, in synchronous rings of known size, this problem can always be solved in O((c+ log n) · n) bits and O(n · c · x 1/c) time for any integer c> 0, where x=Max{¦xmin¦, ¦xmax¦}. The previous solutions required O(n 2) bits and the same amount of time. Based on these results, we also present a bit optimal solution to the problem of finding the multiplicity of the extrema. More... »

PAGES

164-178

Book

TITLE

Distributed Algorithms

ISBN

978-3-540-58449-0
978-3-540-48799-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0020432

DOI

http://dx.doi.org/10.1007/bfb0020432

DIMENSIONS

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


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": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dip. Informatica Sistemistica, Universit\u00e0 di Roma \u201cla Sapienza\u201d, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Alimonti", 
        "givenName": "P.", 
        "id": "sg:person.015632520461.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015632520461.69"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Milan", 
          "id": "https://www.grid.ac/institutes/grid.4708.b", 
          "name": [
            "Dip. di Scienze dell'informazione, Universit\u00e0 di Milano, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Flocchini", 
        "givenName": "P.", 
        "id": "sg:person.011601470625.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Carleton University", 
          "id": "https://www.grid.ac/institutes/grid.34428.39", 
          "name": [
            "School of Computer Science, Carleton University, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Santoro", 
        "givenName": "N.", 
        "id": "sg:person.010566557723.84", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/1634.1889", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002583230"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/7531.7919", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033074534"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/48014.48247", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037496106"
        ], 
        "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": "https://doi.org/10.1016/0304-3975(91)90193-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045063311"
        ], 
        "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.1016/0196-6774(82)90023-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047631493"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(87)90018-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052031732"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1994", 
    "datePublishedReg": "1994-01-01", 
    "description": "We consider the problem of finding the extrema of a distributed multiset in a ring; that is, of determining the minimum and the maximum values, x min and x max, of a multiset X={x 0, x2, ..., x n}-1}, whose elements are drawn from a totally ordered universe U and stored at the n entities of a ring network. This problem is unsolvable if the ring size is not known to the entities, and has complexity \u03b8(n 2) in the case of asynchronous rings of known size. We show that, in synchronous rings of known size, this problem can always be solved in O((c+ log n) \u00b7 n) bits and O(n \u00b7 c \u00b7 x 1/c) time for any integer c> 0, where x=Max{\u00a6xmin\u00a6, \u00a6xmax\u00a6}. The previous solutions required O(n 2) bits and the same amount of time. Based on these results, we also present a bit optimal solution to the problem of finding the multiplicity of the extrema.", 
    "editor": [
      {
        "familyName": "Tel", 
        "givenName": "Gerard", 
        "type": "Person"
      }, 
      {
        "familyName": "Vit\u00e1nyi", 
        "givenName": "Paul", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0020432", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-58449-0", 
        "978-3-540-48799-9"
      ], 
      "name": "Distributed Algorithms", 
      "type": "Book"
    }, 
    "name": "Finding the extrema of a distributed multiset", 
    "pagination": "164-178", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0020432"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "85027f918654846497e55636c86123a7979ad2d0715fedc6e0ac025b9d712ebe"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027921840"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0020432", 
      "https://app.dimensions.ai/details/publication/pub.1027921840"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T18:11", 
    "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_8681_00000260.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/BFb0020432"
  }
]
 

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/bfb0020432'

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/bfb0020432'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0020432'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0020432'


 

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

115 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0020432 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N8ad7561afb0d43dba15793d402ebaee9
4 schema:citation sg:pub.10.1007/bf01783661
5 https://doi.org/10.1016/0020-0190(90)90187-3
6 https://doi.org/10.1016/0196-6774(82)90023-2
7 https://doi.org/10.1016/0304-3975(87)90018-1
8 https://doi.org/10.1016/0304-3975(91)90193-6
9 https://doi.org/10.1145/1634.1889
10 https://doi.org/10.1145/48014.48247
11 https://doi.org/10.1145/7531.7919
12 schema:datePublished 1994
13 schema:datePublishedReg 1994-01-01
14 schema:description We consider the problem of finding the extrema of a distributed multiset in a ring; that is, of determining the minimum and the maximum values, x min and x max, of a multiset X={x 0, x2, ..., x n}-1}, whose elements are drawn from a totally ordered universe U and stored at the n entities of a ring network. This problem is unsolvable if the ring size is not known to the entities, and has complexity θ(n 2) in the case of asynchronous rings of known size. We show that, in synchronous rings of known size, this problem can always be solved in O((c+ log n) · n) bits and O(n · c · x 1/c) time for any integer c> 0, where x=Max{¦xmin¦, ¦xmax¦}. The previous solutions required O(n 2) bits and the same amount of time. Based on these results, we also present a bit optimal solution to the problem of finding the multiplicity of the extrema.
15 schema:editor Nff35f43420a5425eba47113585b1419e
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf N0d0c07155c384b058db1820a6fcce416
20 schema:name Finding the extrema of a distributed multiset
21 schema:pagination 164-178
22 schema:productId N215e0172d2a1476bb4c3f2389b36d7bf
23 N677c3f9917564777a746efbc63a050cb
24 Ndb0b4a5ea3724d6aae3535a9a891d661
25 schema:publisher N4e0339f36a7748b5bdccf76fe96afd63
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027921840
27 https://doi.org/10.1007/bfb0020432
28 schema:sdDatePublished 2019-04-15T18:11
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N34913ef38b744c26ae69588a51dd7aa2
31 schema:url http://link.springer.com/10.1007/BFb0020432
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N0d0c07155c384b058db1820a6fcce416 schema:isbn 978-3-540-48799-9
36 978-3-540-58449-0
37 schema:name Distributed Algorithms
38 rdf:type schema:Book
39 N215e0172d2a1476bb4c3f2389b36d7bf schema:name readcube_id
40 schema:value 85027f918654846497e55636c86123a7979ad2d0715fedc6e0ac025b9d712ebe
41 rdf:type schema:PropertyValue
42 N34913ef38b744c26ae69588a51dd7aa2 schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 N4ddbfa0c9f664143924ad3c862498a2c schema:familyName Vitányi
45 schema:givenName Paul
46 rdf:type schema:Person
47 N4e0339f36a7748b5bdccf76fe96afd63 schema:location Berlin, Heidelberg
48 schema:name Springer Berlin Heidelberg
49 rdf:type schema:Organisation
50 N677c3f9917564777a746efbc63a050cb schema:name doi
51 schema:value 10.1007/bfb0020432
52 rdf:type schema:PropertyValue
53 N689b4a3598de4ee184c83582a7b8a46f rdf:first sg:person.010566557723.84
54 rdf:rest rdf:nil
55 N8ad7561afb0d43dba15793d402ebaee9 rdf:first sg:person.015632520461.69
56 rdf:rest N9adb795464f84ae5ae407444c026dae5
57 N9adb795464f84ae5ae407444c026dae5 rdf:first sg:person.011601470625.25
58 rdf:rest N689b4a3598de4ee184c83582a7b8a46f
59 Nb973f8836d2d435ba6fb9384680c977a schema:familyName Tel
60 schema:givenName Gerard
61 rdf:type schema:Person
62 Ndb0b4a5ea3724d6aae3535a9a891d661 schema:name dimensions_id
63 schema:value pub.1027921840
64 rdf:type schema:PropertyValue
65 Nff35f43420a5425eba47113585b1419e rdf:first Nb973f8836d2d435ba6fb9384680c977a
66 rdf:rest Nff85c2a0956448ebbdd450f5fa9751fe
67 Nff85c2a0956448ebbdd450f5fa9751fe rdf:first N4ddbfa0c9f664143924ad3c862498a2c
68 rdf:rest rdf:nil
69 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
70 schema:name Information and Computing Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
73 schema:name Computation Theory and Mathematics
74 rdf:type schema:DefinedTerm
75 sg:person.010566557723.84 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
76 schema:familyName Santoro
77 schema:givenName N.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84
79 rdf:type schema:Person
80 sg:person.011601470625.25 schema:affiliation https://www.grid.ac/institutes/grid.4708.b
81 schema:familyName Flocchini
82 schema:givenName P.
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25
84 rdf:type schema:Person
85 sg:person.015632520461.69 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
86 schema:familyName Alimonti
87 schema:givenName P.
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015632520461.69
89 rdf:type schema:Person
90 sg:pub.10.1007/bf01783661 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046270517
91 https://doi.org/10.1007/bf01783661
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1016/0020-0190(90)90187-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044391970
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1016/0196-6774(82)90023-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047631493
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1016/0304-3975(87)90018-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052031732
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/0304-3975(91)90193-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045063311
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1145/1634.1889 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002583230
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1145/48014.48247 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037496106
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1145/7531.7919 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033074534
106 rdf:type schema:CreativeWork
107 https://www.grid.ac/institutes/grid.34428.39 schema:alternateName Carleton University
108 schema:name School of Computer Science, Carleton University, Canada
109 rdf:type schema:Organization
110 https://www.grid.ac/institutes/grid.4708.b schema:alternateName University of Milan
111 schema:name Dip. di Scienze dell'informazione, Università di Milano, Italy
112 rdf:type schema:Organization
113 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
114 schema:name Dip. Informatica Sistemistica, Università di Roma “la Sapienza”, Italy
115 rdf:type schema:Organization
 




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


...