Global Synchronization in Sensornets View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Jeremy Elson , Richard M. Karp , Christos H. Papadimitriou , Scott Shenker

ABSTRACT

Time synchronization is necessary in many distributed systems, but achieving synchronization in sensornets, which combine stringent precision requirements with severe resource constraints, is particularly challenging. This challenge has been met by the recent Reference-Broadcast Synchronization (RBS) proposal, which provides on-demand pairwise synchronization with low overhead and high precision. In this paper we introduce a model of the basic RBS synchronization paradigm. Within the context of this model we characterize the optimally precise clock synchronization algorithm and establish its global consistency. In the course of this analysis we point out unexpected connections between optimal clock synchronization, random walks, and resistive networks, and present a polynomial-time approximation scheme for the problem of calculating the effective resistance in a network based on min-cost flow. We also sketch a polynomial-time algorithm for finding a schedule of data acquisition giving the optimal trade-off between energy consumption and precision of clock synchronization. We also discuss synchronization in the presence of clock skews. In ongoing work we are adapting our synchronization algorithm for execution in a network of seismic sensors that requires global clock consistency. More... »

PAGES

609-624

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24698-5_63

DOI

http://dx.doi.org/10.1007/978-3-540-24698-5_63

DIMENSIONS

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


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/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "UCLA and Information Sciences Institute (Elson), UC Berkeley and International Computer Science Institute (Karp, Papadimitriou, Shenker)", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "UCLA and Information Sciences Institute (Elson), UC Berkeley and International Computer Science Institute (Karp, Papadimitriou, Shenker)"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Elson", 
        "givenName": "Jeremy", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UCLA and Information Sciences Institute (Elson), UC Berkeley and International Computer Science Institute (Karp, Papadimitriou, Shenker)", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "UCLA and Information Sciences Institute (Elson), UC Berkeley and International Computer Science Institute (Karp, Papadimitriou, Shenker)"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karp", 
        "givenName": "Richard M.", 
        "id": "sg:person.01037366160.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01037366160.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UCLA and Information Sciences Institute (Elson), UC Berkeley and International Computer Science Institute (Karp, Papadimitriou, Shenker)", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "UCLA and Information Sciences Institute (Elson), UC Berkeley and International Computer Science Institute (Karp, Papadimitriou, Shenker)"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos H.", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UCLA and Information Sciences Institute (Elson), UC Berkeley and International Computer Science Institute (Karp, Papadimitriou, Shenker)", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "UCLA and Information Sciences Institute (Elson), UC Berkeley and International Computer Science Institute (Karp, Papadimitriou, Shenker)"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shenker", 
        "givenName": "Scott", 
        "id": "sg:person.01057336750.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01057336750.07"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "Time synchronization is necessary in many distributed systems, but achieving synchronization in sensornets, which combine stringent precision requirements with severe resource constraints, is particularly challenging. This challenge has been met by the recent Reference-Broadcast Synchronization (RBS) proposal, which provides on-demand pairwise synchronization with low overhead and high precision. In this paper we introduce a model of the basic RBS synchronization paradigm. Within the context of this model we characterize the optimally precise clock synchronization algorithm and establish its global consistency. In the course of this analysis we point out unexpected connections between optimal clock synchronization, random walks, and resistive networks, and present a polynomial-time approximation scheme for the problem of calculating the effective resistance in a network based on min-cost flow. We also sketch a polynomial-time algorithm for finding a schedule of data acquisition giving the optimal trade-off between energy consumption and precision of clock synchronization. We also discuss synchronization in the presence of clock skews. In ongoing work we are adapting our synchronization algorithm for execution in a network of seismic sensors that requires global clock consistency.", 
    "editor": [
      {
        "familyName": "Farach-Colton", 
        "givenName": "Mart\u00edn", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24698-5_63", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-21258-4", 
        "978-3-540-24698-5"
      ], 
      "name": "LATIN 2004: Theoretical Informatics", 
      "type": "Book"
    }, 
    "keywords": [
      "synchronization algorithm", 
      "clock synchronization", 
      "polynomial-time algorithm", 
      "min-cost flow", 
      "severe resource constraints", 
      "clock synchronization algorithm", 
      "polynomial-time approximation scheme", 
      "stringent precision requirements", 
      "low overhead", 
      "time synchronization", 
      "pairwise synchronization", 
      "global consistency", 
      "synchronization paradigm", 
      "resource constraints", 
      "data acquisition", 
      "algorithm", 
      "sensornets", 
      "ongoing work", 
      "network", 
      "global synchronization", 
      "precision requirements", 
      "energy consumption", 
      "synchronization", 
      "approximation scheme", 
      "resistive network", 
      "high precision", 
      "clock skew", 
      "overhead", 
      "seismic sensors", 
      "random walk", 
      "execution", 
      "precision", 
      "scheme", 
      "constraints", 
      "paradigm", 
      "requirements", 
      "sensors", 
      "consistency", 
      "proposal", 
      "model", 
      "system", 
      "challenges", 
      "acquisition", 
      "skew", 
      "work", 
      "walk", 
      "context", 
      "unexpected connection", 
      "schedule", 
      "connection", 
      "consumption", 
      "analysis", 
      "effective resistance", 
      "flow", 
      "course", 
      "presence", 
      "resistance", 
      "paper", 
      "problem", 
      "recent Reference-Broadcast Synchronization (RBS) proposal", 
      "Reference-Broadcast Synchronization (RBS) proposal", 
      "Synchronization (RBS) proposal", 
      "demand pairwise synchronization", 
      "basic RBS synchronization paradigm", 
      "RBS synchronization paradigm", 
      "precise clock synchronization algorithm", 
      "optimal clock synchronization", 
      "global clock consistency", 
      "clock consistency"
    ], 
    "name": "Global Synchronization in Sensornets", 
    "pagination": "609-624", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024785695"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24698-5_63"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24698-5_63", 
      "https://app.dimensions.ai/details/publication/pub.1024785695"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T19:02", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_57.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-24698-5_63"
  }
]
 

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-540-24698-5_63'

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-540-24698-5_63'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24698-5_63'

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-540-24698-5_63'


 

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

149 TRIPLES      23 PREDICATES      95 URIs      88 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24698-5_63 schema:about anzsrc-for:10
2 anzsrc-for:1005
3 schema:author N83aa1cc3d4de4bcfa12d09a9f20fda23
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description Time synchronization is necessary in many distributed systems, but achieving synchronization in sensornets, which combine stringent precision requirements with severe resource constraints, is particularly challenging. This challenge has been met by the recent Reference-Broadcast Synchronization (RBS) proposal, which provides on-demand pairwise synchronization with low overhead and high precision. In this paper we introduce a model of the basic RBS synchronization paradigm. Within the context of this model we characterize the optimally precise clock synchronization algorithm and establish its global consistency. In the course of this analysis we point out unexpected connections between optimal clock synchronization, random walks, and resistive networks, and present a polynomial-time approximation scheme for the problem of calculating the effective resistance in a network based on min-cost flow. We also sketch a polynomial-time algorithm for finding a schedule of data acquisition giving the optimal trade-off between energy consumption and precision of clock synchronization. We also discuss synchronization in the presence of clock skews. In ongoing work we are adapting our synchronization algorithm for execution in a network of seismic sensors that requires global clock consistency.
7 schema:editor N0584a518218c4b6e9b878535b3fa5762
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb772705e43dc42cb9e929ecd33dd87d8
12 schema:keywords RBS synchronization paradigm
13 Reference-Broadcast Synchronization (RBS) proposal
14 Synchronization (RBS) proposal
15 acquisition
16 algorithm
17 analysis
18 approximation scheme
19 basic RBS synchronization paradigm
20 challenges
21 clock consistency
22 clock skew
23 clock synchronization
24 clock synchronization algorithm
25 connection
26 consistency
27 constraints
28 consumption
29 context
30 course
31 data acquisition
32 demand pairwise synchronization
33 effective resistance
34 energy consumption
35 execution
36 flow
37 global clock consistency
38 global consistency
39 global synchronization
40 high precision
41 low overhead
42 min-cost flow
43 model
44 network
45 ongoing work
46 optimal clock synchronization
47 overhead
48 pairwise synchronization
49 paper
50 paradigm
51 polynomial-time algorithm
52 polynomial-time approximation scheme
53 precise clock synchronization algorithm
54 precision
55 precision requirements
56 presence
57 problem
58 proposal
59 random walk
60 recent Reference-Broadcast Synchronization (RBS) proposal
61 requirements
62 resistance
63 resistive network
64 resource constraints
65 schedule
66 scheme
67 seismic sensors
68 sensornets
69 sensors
70 severe resource constraints
71 skew
72 stringent precision requirements
73 synchronization
74 synchronization algorithm
75 synchronization paradigm
76 system
77 time synchronization
78 unexpected connection
79 walk
80 work
81 schema:name Global Synchronization in Sensornets
82 schema:pagination 609-624
83 schema:productId N057c783de53d4c5c913f413d552fb3f2
84 Nd3cad1e6a2af4e64b993b5cd23effaa5
85 schema:publisher N5e4fa1e83c5d4f32924bf3c1c90cb042
86 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024785695
87 https://doi.org/10.1007/978-3-540-24698-5_63
88 schema:sdDatePublished 2021-11-01T19:02
89 schema:sdLicense https://scigraph.springernature.com/explorer/license/
90 schema:sdPublisher N919ff48670e142789bc7c186799433ec
91 schema:url https://doi.org/10.1007/978-3-540-24698-5_63
92 sgo:license sg:explorer/license/
93 sgo:sdDataset chapters
94 rdf:type schema:Chapter
95 N057c783de53d4c5c913f413d552fb3f2 schema:name dimensions_id
96 schema:value pub.1024785695
97 rdf:type schema:PropertyValue
98 N0584a518218c4b6e9b878535b3fa5762 rdf:first Nbbbbebf8fe004bfb849f61ed03a95a69
99 rdf:rest rdf:nil
100 N45f8cd16fbf7451fa49fbad6cb16dafd rdf:first sg:person.01057336750.07
101 rdf:rest rdf:nil
102 N5e4fa1e83c5d4f32924bf3c1c90cb042 schema:name Springer Nature
103 rdf:type schema:Organisation
104 N76154e265df042f588d6c741167347fd rdf:first sg:person.01037366160.22
105 rdf:rest Nd7b0768b84e04a52b05759bd2eafb24f
106 N83aa1cc3d4de4bcfa12d09a9f20fda23 rdf:first Nff87dcf314b0413e8e3cb9b83ad756d3
107 rdf:rest N76154e265df042f588d6c741167347fd
108 N919ff48670e142789bc7c186799433ec schema:name Springer Nature - SN SciGraph project
109 rdf:type schema:Organization
110 Nb772705e43dc42cb9e929ecd33dd87d8 schema:isbn 978-3-540-21258-4
111 978-3-540-24698-5
112 schema:name LATIN 2004: Theoretical Informatics
113 rdf:type schema:Book
114 Nbbbbebf8fe004bfb849f61ed03a95a69 schema:familyName Farach-Colton
115 schema:givenName Martín
116 rdf:type schema:Person
117 Nd3cad1e6a2af4e64b993b5cd23effaa5 schema:name doi
118 schema:value 10.1007/978-3-540-24698-5_63
119 rdf:type schema:PropertyValue
120 Nd7b0768b84e04a52b05759bd2eafb24f rdf:first sg:person.013233165465.63
121 rdf:rest N45f8cd16fbf7451fa49fbad6cb16dafd
122 Nff87dcf314b0413e8e3cb9b83ad756d3 schema:affiliation grid-institutes:None
123 schema:familyName Elson
124 schema:givenName Jeremy
125 rdf:type schema:Person
126 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
127 schema:name Technology
128 rdf:type schema:DefinedTerm
129 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
130 schema:name Communications Technologies
131 rdf:type schema:DefinedTerm
132 sg:person.01037366160.22 schema:affiliation grid-institutes:None
133 schema:familyName Karp
134 schema:givenName Richard M.
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01037366160.22
136 rdf:type schema:Person
137 sg:person.01057336750.07 schema:affiliation grid-institutes:None
138 schema:familyName Shenker
139 schema:givenName Scott
140 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01057336750.07
141 rdf:type schema:Person
142 sg:person.013233165465.63 schema:affiliation grid-institutes:None
143 schema:familyName Papadimitriou
144 schema:givenName Christos H.
145 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
146 rdf:type schema:Person
147 grid-institutes:None schema:alternateName UCLA and Information Sciences Institute (Elson), UC Berkeley and International Computer Science Institute (Karp, Papadimitriou, Shenker)
148 schema:name UCLA and Information Sciences Institute (Elson), UC Berkeley and International Computer Science Institute (Karp, Papadimitriou, Shenker)
149 rdf:type schema:Organization
 




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


...