The computational power of population protocols View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2007-11

AUTHORS

Dana Angluin, James Aspnes, David Eisenstat, Eric Ruppert

ABSTRACT

We consider the model of population protocols introduced by Angluin et al. (Computation in networks of passively mobile finite-state sensors, pp. 290–299. ACM, New York, 2004), in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via two-way interactions in the family of all-pairs communication networks. We prove that all predicates stably computable in this model (and certain generalizations of it) are semilinear, answering a central open question about the power of the model. Removing the assumption of two-way interaction, we also consider several variants of the model in which agents communicate by anonymous message-passing where the recipient of each message is chosen by an adversary and the sender is not identified to the recipient. These one-way models are distinguished by whether messages are delivered immediately or after a delay, whether a sender can record that it has sent a message, and whether a recipient can queue incoming messages, refusing to accept new messages until it has had a chance to send out messages of its own. We characterize the classes of predicates stably computable in each of these one-way models using natural subclasses of the semilinear predicates. More... »

PAGES

279-304

References to SciGraph publications

  • 2001-03. A simple game for the study of trust in distributed systems in WUHAN UNIVERSITY JOURNAL OF NATURAL SCIENCES
  • 2003-09. Hundreds of impossibility results for distributed computing in DISTRIBUTED COMPUTING
  • 2006. Stabilizing Consensus in Mobile Networks in DISTRIBUTED COMPUTING IN SENSOR SYSTEMS
  • 1994-08. Naming symmetric processes using shared variables in DISTRIBUTED COMPUTING
  • 2001-09-11. An Effective Characterization of Computability in Anonymous Networks in DISTRIBUTED COMPUTING
  • 1998-08. Randomized naming using wait-free shared variables in DISTRIBUTED COMPUTING
  • 2006. When Birds Die: Making Population Protocols Fault-Tolerant in DISTRIBUTED COMPUTING IN SENSOR SYSTEMS
  • 2006. Fast Computation by Population Protocols with a Leader in DISTRIBUTED COMPUTING
  • 2006-03. Computation in networks of passively mobile finite-state sensors in DISTRIBUTED COMPUTING
  • 2006. Self-stabilizing Population Protocols in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 1991. Wakeup under read/write atomicity in DISTRIBUTED ALGORITHMS
  • 2006. Self-stabilizing Leader Election in Networks of Finite-State Anonymous Agents in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 2006. On the Power of Anonymous One-Way Communication in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 2007-10. Anonymous and fault-tolerant shared-memory computing in DISTRIBUTED COMPUTING
  • 2006-02. On the importance of having an identity or, is consensus really universal? in DISTRIBUTED COMPUTING
  • 2005. Stably Computable Properties of Network Graphs in DISTRIBUTED COMPUTING IN SENSOR SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00446-007-0040-2

    DOI

    http://dx.doi.org/10.1007/s00446-007-0040-2

    DIMENSIONS

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


    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": "Yale University", 
              "id": "https://www.grid.ac/institutes/grid.47100.32", 
              "name": [
                "Yale University, New Haven, CT, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Angluin", 
            "givenName": "Dana", 
            "id": "sg:person.012777470527.24", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012777470527.24"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Yale University", 
              "id": "https://www.grid.ac/institutes/grid.47100.32", 
              "name": [
                "Yale University, New Haven, CT, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Aspnes", 
            "givenName": "James", 
            "id": "sg:person.07603052541.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07603052541.00"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Princeton University", 
              "id": "https://www.grid.ac/institutes/grid.16750.35", 
              "name": [
                "Princeton University, Princeton, NJ, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Eisenstat", 
            "givenName": "David", 
            "id": "sg:person.012723473111.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012723473111.27"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "York University", 
              "id": "https://www.grid.ac/institutes/grid.21100.32", 
              "name": [
                "York University, Toronto, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ruppert", 
            "givenName": "Eric", 
            "id": "sg:person.015321512455.60", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015321512455.60"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11776178_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000140499", 
              "https://doi.org/10.1007/11776178_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11776178_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000140499", 
              "https://doi.org/10.1007/11776178_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1021/jp993732q", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000647454"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1021/jp993732q", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000647454"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/301308.301352", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003092108"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(90)90103-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004348357"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11502593_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006294768", 
              "https://doi.org/10.1007/11502593_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11502593_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006294768", 
              "https://doi.org/10.1007/11502593_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11864219_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011929643", 
              "https://doi.org/10.1007/11864219_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11864219_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011929643", 
              "https://doi.org/10.1007/11864219_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.2000.1110", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014787372"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(79)90041-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015335104"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1112/plms/s3-2.1.326", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016071453"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2003.10.028", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016565524"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45414-4_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018563200", 
              "https://doi.org/10.1007/3-540-45414-4_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45414-4_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018563200", 
              "https://doi.org/10.1007/3-540-45414-4_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-003-0091-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018732233", 
              "https://doi.org/10.1007/s00446-003-0091-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/inco.2001.3119", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019205331"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1146381.1146425", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021804191"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11795490_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023123527", 
              "https://doi.org/10.1007/11795490_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11795490_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023123527", 
              "https://doi.org/10.1007/11795490_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s004460050045", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025196545", 
              "https://doi.org/10.1007/s004460050045"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11795490_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026846852", 
              "https://doi.org/10.1007/11795490_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11795490_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026846852", 
              "https://doi.org/10.1007/11795490_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0378-4371(92)90283-v", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030775693"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0378-4371(92)90283-v", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030775693"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-005-0121-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032446123", 
              "https://doi.org/10.1007/s00446-005-0121-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-005-0121-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032446123", 
              "https://doi.org/10.1007/s00446-005-0121-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(90)90094-e", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032641364"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11776178_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032841614", 
              "https://doi.org/10.1007/11776178_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321356.321364", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036285496"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/301308.301355", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037385852"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-54099-7_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039259117", 
              "https://doi.org/10.1007/3-540-54099-7_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-007-0042-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040077881", 
              "https://doi.org/10.1007/s00446-007-0042-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-007-0042-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040077881", 
              "https://doi.org/10.1007/s00446-007-0042-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/509907.509983", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043983740"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11945529_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045117559", 
              "https://doi.org/10.1007/11945529_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11945529_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045117559", 
              "https://doi.org/10.1007/11945529_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-005-0138-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047674948", 
              "https://doi.org/10.1007/s00446-005-0138-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-005-0138-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047674948", 
              "https://doi.org/10.1007/s00446-005-0138-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1011767.1011810", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048794699"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02283568", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051191130", 
              "https://doi.org/10.1007/bf02283568"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02283568", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051191130", 
              "https://doi.org/10.1007/bf02283568"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf03160228", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051344053", 
              "https://doi.org/10.1007/bf03160228"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf03160228", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051344053", 
              "https://doi.org/10.1007/bf03160228"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf03160228", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051344053", 
              "https://doi.org/10.1007/bf03160228"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/imamat/1.1.42", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059684230"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2370405", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069897226"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007-11", 
        "datePublishedReg": "2007-11-01", 
        "description": "We consider the model of population protocols introduced by Angluin et al. (Computation in networks of passively mobile finite-state sensors, pp. 290\u2013299. ACM, New York, 2004), in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via two-way interactions in the family of all-pairs communication networks. We prove that all predicates stably computable in this model (and certain generalizations of it) are semilinear, answering a central open question about the power of the model. Removing the assumption of two-way interaction, we also consider several variants of the model in which agents communicate by anonymous message-passing where the recipient of each message is chosen by an adversary and the sender is not identified to the recipient. These one-way models are distinguished by whether messages are delivered immediately or after a delay, whether a sender can record that it has sent a message, and whether a recipient can queue incoming messages, refusing to accept new messages until it has had a chance to send out messages of its own. We characterize the classes of predicates stably computable in each of these one-way models using natural subclasses of the semilinear predicates.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00446-007-0040-2", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052621", 
            "issn": [
              "0178-2770", 
              "1432-0452"
            ], 
            "name": "Distributed Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "20"
          }
        ], 
        "name": "The computational power of population protocols", 
        "pagination": "279-304", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "276948058254f9e7d60080168d3da49dcd26d9ac25ea64b6e8e0798eda20d6d9"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00446-007-0040-2"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1008272694"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00446-007-0040-2", 
          "https://app.dimensions.ai/details/publication/pub.1008272694"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T14:27", 
        "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/0000000373_0000000373/records_13078_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00446-007-0040-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/s00446-007-0040-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/s00446-007-0040-2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00446-007-0040-2'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00446-007-0040-2'


     

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

    203 TRIPLES      21 PREDICATES      60 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00446-007-0040-2 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N5a9b840a7e0746338e440d3b565cf029
    4 schema:citation sg:pub.10.1007/11502593_8
    5 sg:pub.10.1007/11776178_3
    6 sg:pub.10.1007/11776178_4
    7 sg:pub.10.1007/11795490_10
    8 sg:pub.10.1007/11795490_30
    9 sg:pub.10.1007/11864219_5
    10 sg:pub.10.1007/11945529_28
    11 sg:pub.10.1007/3-540-45414-4_3
    12 sg:pub.10.1007/3-540-54099-7_19
    13 sg:pub.10.1007/bf02283568
    14 sg:pub.10.1007/bf03160228
    15 sg:pub.10.1007/s00446-003-0091-y
    16 sg:pub.10.1007/s00446-005-0121-z
    17 sg:pub.10.1007/s00446-005-0138-3
    18 sg:pub.10.1007/s00446-007-0042-0
    19 sg:pub.10.1007/s004460050045
    20 https://doi.org/10.1006/inco.2001.3119
    21 https://doi.org/10.1006/jagm.2000.1110
    22 https://doi.org/10.1016/0020-0190(90)90094-e
    23 https://doi.org/10.1016/0020-0190(90)90103-5
    24 https://doi.org/10.1016/0304-3975(79)90041-0
    25 https://doi.org/10.1016/0378-4371(92)90283-v
    26 https://doi.org/10.1016/j.tcs.2003.10.028
    27 https://doi.org/10.1021/jp993732q
    28 https://doi.org/10.1093/imamat/1.1.42
    29 https://doi.org/10.1112/plms/s3-2.1.326
    30 https://doi.org/10.1145/1011767.1011810
    31 https://doi.org/10.1145/1146381.1146425
    32 https://doi.org/10.1145/301308.301352
    33 https://doi.org/10.1145/301308.301355
    34 https://doi.org/10.1145/321356.321364
    35 https://doi.org/10.1145/509907.509983
    36 https://doi.org/10.2307/2370405
    37 schema:datePublished 2007-11
    38 schema:datePublishedReg 2007-11-01
    39 schema:description We consider the model of population protocols introduced by Angluin et al. (Computation in networks of passively mobile finite-state sensors, pp. 290–299. ACM, New York, 2004), in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via two-way interactions in the family of all-pairs communication networks. We prove that all predicates stably computable in this model (and certain generalizations of it) are semilinear, answering a central open question about the power of the model. Removing the assumption of two-way interaction, we also consider several variants of the model in which agents communicate by anonymous message-passing where the recipient of each message is chosen by an adversary and the sender is not identified to the recipient. These one-way models are distinguished by whether messages are delivered immediately or after a delay, whether a sender can record that it has sent a message, and whether a recipient can queue incoming messages, refusing to accept new messages until it has had a chance to send out messages of its own. We characterize the classes of predicates stably computable in each of these one-way models using natural subclasses of the semilinear predicates.
    40 schema:genre research_article
    41 schema:inLanguage en
    42 schema:isAccessibleForFree true
    43 schema:isPartOf N598e2f5b056f44b1961c924a3477674b
    44 Nc973582837f04ad1b587969461c5490b
    45 sg:journal.1052621
    46 schema:name The computational power of population protocols
    47 schema:pagination 279-304
    48 schema:productId Na646002f935f424d8d64897ad5a3cecb
    49 Nbc37996c053842cfb6ccee7189e35f45
    50 Nc2c99fbf1dc546e28ce5def772b74bbc
    51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008272694
    52 https://doi.org/10.1007/s00446-007-0040-2
    53 schema:sdDatePublished 2019-04-11T14:27
    54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    55 schema:sdPublisher N754d78ff0f20421aacb1b4f823c4972a
    56 schema:url http://link.springer.com/10.1007/s00446-007-0040-2
    57 sgo:license sg:explorer/license/
    58 sgo:sdDataset articles
    59 rdf:type schema:ScholarlyArticle
    60 N0ddd5f76c388434682726ac0d13125fa rdf:first sg:person.012723473111.27
    61 rdf:rest Na322966649594c5ab784d29e18271a51
    62 N598e2f5b056f44b1961c924a3477674b schema:volumeNumber 20
    63 rdf:type schema:PublicationVolume
    64 N5a9b840a7e0746338e440d3b565cf029 rdf:first sg:person.012777470527.24
    65 rdf:rest Nffac8dbf09e149b79aae40304a527113
    66 N754d78ff0f20421aacb1b4f823c4972a schema:name Springer Nature - SN SciGraph project
    67 rdf:type schema:Organization
    68 Na322966649594c5ab784d29e18271a51 rdf:first sg:person.015321512455.60
    69 rdf:rest rdf:nil
    70 Na646002f935f424d8d64897ad5a3cecb schema:name dimensions_id
    71 schema:value pub.1008272694
    72 rdf:type schema:PropertyValue
    73 Nbc37996c053842cfb6ccee7189e35f45 schema:name doi
    74 schema:value 10.1007/s00446-007-0040-2
    75 rdf:type schema:PropertyValue
    76 Nc2c99fbf1dc546e28ce5def772b74bbc schema:name readcube_id
    77 schema:value 276948058254f9e7d60080168d3da49dcd26d9ac25ea64b6e8e0798eda20d6d9
    78 rdf:type schema:PropertyValue
    79 Nc973582837f04ad1b587969461c5490b schema:issueNumber 4
    80 rdf:type schema:PublicationIssue
    81 Nffac8dbf09e149b79aae40304a527113 rdf:first sg:person.07603052541.00
    82 rdf:rest N0ddd5f76c388434682726ac0d13125fa
    83 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Information and Computing Sciences
    85 rdf:type schema:DefinedTerm
    86 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    87 schema:name Computation Theory and Mathematics
    88 rdf:type schema:DefinedTerm
    89 sg:journal.1052621 schema:issn 0178-2770
    90 1432-0452
    91 schema:name Distributed Computing
    92 rdf:type schema:Periodical
    93 sg:person.012723473111.27 schema:affiliation https://www.grid.ac/institutes/grid.16750.35
    94 schema:familyName Eisenstat
    95 schema:givenName David
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012723473111.27
    97 rdf:type schema:Person
    98 sg:person.012777470527.24 schema:affiliation https://www.grid.ac/institutes/grid.47100.32
    99 schema:familyName Angluin
    100 schema:givenName Dana
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012777470527.24
    102 rdf:type schema:Person
    103 sg:person.015321512455.60 schema:affiliation https://www.grid.ac/institutes/grid.21100.32
    104 schema:familyName Ruppert
    105 schema:givenName Eric
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015321512455.60
    107 rdf:type schema:Person
    108 sg:person.07603052541.00 schema:affiliation https://www.grid.ac/institutes/grid.47100.32
    109 schema:familyName Aspnes
    110 schema:givenName James
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07603052541.00
    112 rdf:type schema:Person
    113 sg:pub.10.1007/11502593_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006294768
    114 https://doi.org/10.1007/11502593_8
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/11776178_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000140499
    117 https://doi.org/10.1007/11776178_3
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/11776178_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032841614
    120 https://doi.org/10.1007/11776178_4
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/11795490_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026846852
    123 https://doi.org/10.1007/11795490_10
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/11795490_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023123527
    126 https://doi.org/10.1007/11795490_30
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/11864219_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011929643
    129 https://doi.org/10.1007/11864219_5
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/11945529_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045117559
    132 https://doi.org/10.1007/11945529_28
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/3-540-45414-4_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018563200
    135 https://doi.org/10.1007/3-540-45414-4_3
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/3-540-54099-7_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039259117
    138 https://doi.org/10.1007/3-540-54099-7_19
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/bf02283568 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051191130
    141 https://doi.org/10.1007/bf02283568
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/bf03160228 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051344053
    144 https://doi.org/10.1007/bf03160228
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/s00446-003-0091-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1018732233
    147 https://doi.org/10.1007/s00446-003-0091-y
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/s00446-005-0121-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1032446123
    150 https://doi.org/10.1007/s00446-005-0121-z
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/s00446-005-0138-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047674948
    153 https://doi.org/10.1007/s00446-005-0138-3
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/s00446-007-0042-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040077881
    156 https://doi.org/10.1007/s00446-007-0042-0
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/s004460050045 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025196545
    159 https://doi.org/10.1007/s004460050045
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.1006/inco.2001.3119 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019205331
    162 rdf:type schema:CreativeWork
    163 https://doi.org/10.1006/jagm.2000.1110 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014787372
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1016/0020-0190(90)90094-e schema:sameAs https://app.dimensions.ai/details/publication/pub.1032641364
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1016/0020-0190(90)90103-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004348357
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1016/0304-3975(79)90041-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015335104
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1016/0378-4371(92)90283-v schema:sameAs https://app.dimensions.ai/details/publication/pub.1030775693
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1016/j.tcs.2003.10.028 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016565524
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1021/jp993732q schema:sameAs https://app.dimensions.ai/details/publication/pub.1000647454
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1093/imamat/1.1.42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059684230
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1112/plms/s3-2.1.326 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016071453
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1145/1011767.1011810 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048794699
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1145/1146381.1146425 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021804191
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1145/301308.301352 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003092108
    186 rdf:type schema:CreativeWork
    187 https://doi.org/10.1145/301308.301355 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037385852
    188 rdf:type schema:CreativeWork
    189 https://doi.org/10.1145/321356.321364 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036285496
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1145/509907.509983 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043983740
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.2307/2370405 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069897226
    194 rdf:type schema:CreativeWork
    195 https://www.grid.ac/institutes/grid.16750.35 schema:alternateName Princeton University
    196 schema:name Princeton University, Princeton, NJ, USA
    197 rdf:type schema:Organization
    198 https://www.grid.ac/institutes/grid.21100.32 schema:alternateName York University
    199 schema:name York University, Toronto, ON, Canada
    200 rdf:type schema:Organization
    201 https://www.grid.ac/institutes/grid.47100.32 schema:alternateName Yale University
    202 schema:name Yale University, New Haven, CT, USA
    203 rdf:type schema:Organization
     




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


    ...