Distributed Computing with Imperfect Randomness View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Shafi Goldwasser , Madhu Sudan , Vinod Vaikuntanathan

ABSTRACT

Randomness is a critical resource in many computational scenarios, enabling solutions where deterministic ones are elusive or even provably impossible. However, the randomized solutions to these tasks assume access to a source of unbiased, independent coins. Physical sources of randomness, on the other hand, are rarely unbiased and independent although they do seem to exhibit somewhat imperfect randomness. This gap in modeling questions the relevance of current randomized solutions to computational tasks. Indeed, there has been substantial investigation of this issue in complexity theory in the context of the applications to efficient algorithms and cryptography.In this paper, we seek to determine whether imperfect randomness, modeled appropriately, is “good enough” for distributed algorithms. Namely can we do with imperfect randomness all that we can do with perfect randomness, and with comparable efficiency ? We answer this question in the affirmative, for the problem of Byzantine agreement. We construct protocols for Byzantine agreement in a variety of scenarios (synchronous or asynchronous networks, with or without private channels), in which the players have imperfect randomness. Our solutions are essentially as efficient as the best known randomized agreement protocols, despite the defects in the randomness. More... »

PAGES

288-302

Book

TITLE

Distributed Computing

ISBN

978-3-540-29163-3
978-3-540-32075-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11561927_22

DOI

http://dx.doi.org/10.1007/11561927_22

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "MIT CSAIL, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT CSAIL, 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Goldwasser", 
        "givenName": "Shafi", 
        "id": "sg:person.010651111361.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010651111361.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT CSAIL, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT CSAIL, 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sudan", 
        "givenName": "Madhu", 
        "id": "sg:person.014663420265.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT CSAIL, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT CSAIL, 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vaikuntanathan", 
        "givenName": "Vinod", 
        "id": "sg:person.010511407257.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010511407257.61"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "Randomness is a critical resource in many computational scenarios, enabling solutions where deterministic ones are elusive or even provably impossible. However, the randomized solutions to these tasks assume access to a source of unbiased, independent coins. Physical sources of randomness, on the other hand, are rarely unbiased and independent although they do seem to exhibit somewhat imperfect randomness. This gap in modeling questions the relevance of current randomized solutions to computational tasks. Indeed, there has been substantial investigation of this issue in complexity theory in the context of the applications to efficient algorithms and cryptography.In this paper, we seek to determine whether imperfect randomness, modeled appropriately, is \u201cgood enough\u201d for distributed algorithms. Namely can we do with imperfect randomness all that we can do with perfect randomness, and with comparable efficiency ? We answer this question in the affirmative, for the problem of Byzantine agreement. We construct protocols for Byzantine agreement in a variety of scenarios (synchronous or asynchronous networks, with or without private channels), in which the players have imperfect randomness. Our solutions are essentially as efficient as the best known randomized agreement protocols, despite the defects in the randomness.", 
    "editor": [
      {
        "familyName": "Fraigniaud", 
        "givenName": "Pierre", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11561927_22", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-29163-3", 
        "978-3-540-32075-3"
      ], 
      "name": "Distributed Computing", 
      "type": "Book"
    }, 
    "keywords": [
      "Byzantine agreement", 
      "imperfect randomness", 
      "variety of scenarios", 
      "distributed algorithm", 
      "computational tasks", 
      "agreement protocol", 
      "randomized solutions", 
      "computational scenarios", 
      "complexity theory", 
      "algorithm", 
      "critical resources", 
      "perfect randomness", 
      "task", 
      "deterministic one", 
      "scenarios", 
      "cryptography", 
      "randomness", 
      "protocol", 
      "independent coin", 
      "solution", 
      "physical sources", 
      "resources", 
      "access", 
      "applications", 
      "comparable efficiency", 
      "issues", 
      "substantial investigation", 
      "efficiency", 
      "context", 
      "players", 
      "one", 
      "hand", 
      "variety", 
      "source", 
      "coins", 
      "questions", 
      "gap", 
      "theory", 
      "relevance", 
      "agreement", 
      "defects", 
      "investigation", 
      "problem", 
      "paper", 
      "current randomized solutions", 
      "randomized agreement protocols"
    ], 
    "name": "Distributed Computing with Imperfect Randomness", 
    "pagination": "288-302", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035148648"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11561927_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11561927_22", 
      "https://app.dimensions.ai/details/publication/pub.1035148648"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_212.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11561927_22"
  }
]
 

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/11561927_22'

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/11561927_22'

Turtle is a human-readable linked data format.

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

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

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


 

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

120 TRIPLES      23 PREDICATES      72 URIs      65 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11561927_22 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nc514f6f4ecf44e10bc000bd934657f16
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description Randomness is a critical resource in many computational scenarios, enabling solutions where deterministic ones are elusive or even provably impossible. However, the randomized solutions to these tasks assume access to a source of unbiased, independent coins. Physical sources of randomness, on the other hand, are rarely unbiased and independent although they do seem to exhibit somewhat imperfect randomness. This gap in modeling questions the relevance of current randomized solutions to computational tasks. Indeed, there has been substantial investigation of this issue in complexity theory in the context of the applications to efficient algorithms and cryptography.In this paper, we seek to determine whether imperfect randomness, modeled appropriately, is “good enough” for distributed algorithms. Namely can we do with imperfect randomness all that we can do with perfect randomness, and with comparable efficiency ? We answer this question in the affirmative, for the problem of Byzantine agreement. We construct protocols for Byzantine agreement in a variety of scenarios (synchronous or asynchronous networks, with or without private channels), in which the players have imperfect randomness. Our solutions are essentially as efficient as the best known randomized agreement protocols, despite the defects in the randomness.
7 schema:editor Nc01a6cee206f497fbd3f4b27c4c605fa
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N502113f7e7c34dc7a0e67bf9d3287071
12 schema:keywords Byzantine agreement
13 access
14 agreement
15 agreement protocol
16 algorithm
17 applications
18 coins
19 comparable efficiency
20 complexity theory
21 computational scenarios
22 computational tasks
23 context
24 critical resources
25 cryptography
26 current randomized solutions
27 defects
28 deterministic one
29 distributed algorithm
30 efficiency
31 gap
32 hand
33 imperfect randomness
34 independent coin
35 investigation
36 issues
37 one
38 paper
39 perfect randomness
40 physical sources
41 players
42 problem
43 protocol
44 questions
45 randomized agreement protocols
46 randomized solutions
47 randomness
48 relevance
49 resources
50 scenarios
51 solution
52 source
53 substantial investigation
54 task
55 theory
56 variety
57 variety of scenarios
58 schema:name Distributed Computing with Imperfect Randomness
59 schema:pagination 288-302
60 schema:productId N563c4d220d4c4482824332e4ae8e27d7
61 N5af19402090d46ba8f899bfdb4fdeb15
62 schema:publisher Nbfbc757f286948f1a3c65a330f83eac9
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035148648
64 https://doi.org/10.1007/11561927_22
65 schema:sdDatePublished 2022-01-01T19:12
66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
67 schema:sdPublisher N5a24fb99434e40bfb56a1f03635f4cda
68 schema:url https://doi.org/10.1007/11561927_22
69 sgo:license sg:explorer/license/
70 sgo:sdDataset chapters
71 rdf:type schema:Chapter
72 N45946af3ee2c4110838db1d1e0217557 schema:familyName Fraigniaud
73 schema:givenName Pierre
74 rdf:type schema:Person
75 N502113f7e7c34dc7a0e67bf9d3287071 schema:isbn 978-3-540-29163-3
76 978-3-540-32075-3
77 schema:name Distributed Computing
78 rdf:type schema:Book
79 N563c4d220d4c4482824332e4ae8e27d7 schema:name dimensions_id
80 schema:value pub.1035148648
81 rdf:type schema:PropertyValue
82 N5a24fb99434e40bfb56a1f03635f4cda schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N5af19402090d46ba8f899bfdb4fdeb15 schema:name doi
85 schema:value 10.1007/11561927_22
86 rdf:type schema:PropertyValue
87 N666a3390d55d488b9c1469fa34222514 rdf:first sg:person.014663420265.17
88 rdf:rest N69cd48ee1043459db582c8bf37df1481
89 N69cd48ee1043459db582c8bf37df1481 rdf:first sg:person.010511407257.61
90 rdf:rest rdf:nil
91 Nbfbc757f286948f1a3c65a330f83eac9 schema:name Springer Nature
92 rdf:type schema:Organisation
93 Nc01a6cee206f497fbd3f4b27c4c605fa rdf:first N45946af3ee2c4110838db1d1e0217557
94 rdf:rest rdf:nil
95 Nc514f6f4ecf44e10bc000bd934657f16 rdf:first sg:person.010651111361.51
96 rdf:rest N666a3390d55d488b9c1469fa34222514
97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
98 schema:name Information and Computing Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
101 schema:name Computation Theory and Mathematics
102 rdf:type schema:DefinedTerm
103 sg:person.010511407257.61 schema:affiliation grid-institutes:grid.116068.8
104 schema:familyName Vaikuntanathan
105 schema:givenName Vinod
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010511407257.61
107 rdf:type schema:Person
108 sg:person.010651111361.51 schema:affiliation grid-institutes:grid.116068.8
109 schema:familyName Goldwasser
110 schema:givenName Shafi
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010651111361.51
112 rdf:type schema:Person
113 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
114 schema:familyName Sudan
115 schema:givenName Madhu
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
117 rdf:type schema:Person
118 grid-institutes:grid.116068.8 schema:alternateName MIT CSAIL, 02139, Cambridge, MA, USA
119 schema:name MIT CSAIL, 02139, Cambridge, MA, USA
120 rdf:type schema:Organization
 




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


...