On the design of distributed protocols from differential equations

Research output: Contribution to conferencePaper

Abstract

We propose a framework to translate certain subclasses of differential equation systems into distributed protocols that are practical. The synthesized protocols are state machines containing probabilistic transitions and actions, and they show equivalent stochastic behavior to that in the original equations. The protocols are probabilistically scalable and reliable, and are derived from two subclasses of equations with polynomial terms. We prove the equivalence of protocols to the source equations. Rewriting techniques to bring equations into the appropriate mappable form are also described. In order to illustrate the usefulness of the approach, we present the design and study of scalable and probabilistically reliable protocols for migratory replication and majority selection. These two protocols are derived from natural analogies represented as differential equations - endemics and the Lotka- Volterra model of competition respectively. Well-known epidemic protocols are also shown to be an output of the framework. We present mathematical analysis of the protocols, and experimental results from our implementations. We also discuss limitations of our approach. We believe the design framework could be effectively used in transforming, in a very systematic manner, well-known natural phenomena into protocols for distributed systems.

Original languageEnglish (US)
Pages216-225
Number of pages10
StatePublished - Dec 27 2004
EventProceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing - St. John's, Nfld., Canada
Duration: Jul 25 2004Jul 28 2004

Other

OtherProceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing
CountryCanada
CitySt. John's, Nfld.
Period7/25/047/28/04

Fingerprint

Differential equations
Polynomials

Keywords

  • Distributed Protocols
  • Endemic Protocols
  • Probabilistic protocols
  • Reliability
  • Scalability
  • Science of Protocol Design

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Gupta, I. (2004). On the design of distributed protocols from differential equations. 216-225. Paper presented at Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, St. John's, Nfld., Canada.

On the design of distributed protocols from differential equations. / Gupta, Indranil.

2004. 216-225 Paper presented at Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, St. John's, Nfld., Canada.

Research output: Contribution to conferencePaper

Gupta, I 2004, 'On the design of distributed protocols from differential equations' Paper presented at Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, St. John's, Nfld., Canada, 7/25/04 - 7/28/04, pp. 216-225.
Gupta I. On the design of distributed protocols from differential equations. 2004. Paper presented at Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, St. John's, Nfld., Canada.
Gupta, Indranil. / On the design of distributed protocols from differential equations. Paper presented at Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, St. John's, Nfld., Canada.10 p.
@conference{b98f30b66cc74e6b804b3f298d0fadae,
title = "On the design of distributed protocols from differential equations",
abstract = "We propose a framework to translate certain subclasses of differential equation systems into distributed protocols that are practical. The synthesized protocols are state machines containing probabilistic transitions and actions, and they show equivalent stochastic behavior to that in the original equations. The protocols are probabilistically scalable and reliable, and are derived from two subclasses of equations with polynomial terms. We prove the equivalence of protocols to the source equations. Rewriting techniques to bring equations into the appropriate mappable form are also described. In order to illustrate the usefulness of the approach, we present the design and study of scalable and probabilistically reliable protocols for migratory replication and majority selection. These two protocols are derived from natural analogies represented as differential equations - endemics and the Lotka- Volterra model of competition respectively. Well-known epidemic protocols are also shown to be an output of the framework. We present mathematical analysis of the protocols, and experimental results from our implementations. We also discuss limitations of our approach. We believe the design framework could be effectively used in transforming, in a very systematic manner, well-known natural phenomena into protocols for distributed systems.",
keywords = "Distributed Protocols, Endemic Protocols, Probabilistic protocols, Reliability, Scalability, Science of Protocol Design",
author = "Indranil Gupta",
year = "2004",
month = "12",
day = "27",
language = "English (US)",
pages = "216--225",
note = "Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing ; Conference date: 25-07-2004 Through 28-07-2004",

}

TY - CONF

T1 - On the design of distributed protocols from differential equations

AU - Gupta, Indranil

PY - 2004/12/27

Y1 - 2004/12/27

N2 - We propose a framework to translate certain subclasses of differential equation systems into distributed protocols that are practical. The synthesized protocols are state machines containing probabilistic transitions and actions, and they show equivalent stochastic behavior to that in the original equations. The protocols are probabilistically scalable and reliable, and are derived from two subclasses of equations with polynomial terms. We prove the equivalence of protocols to the source equations. Rewriting techniques to bring equations into the appropriate mappable form are also described. In order to illustrate the usefulness of the approach, we present the design and study of scalable and probabilistically reliable protocols for migratory replication and majority selection. These two protocols are derived from natural analogies represented as differential equations - endemics and the Lotka- Volterra model of competition respectively. Well-known epidemic protocols are also shown to be an output of the framework. We present mathematical analysis of the protocols, and experimental results from our implementations. We also discuss limitations of our approach. We believe the design framework could be effectively used in transforming, in a very systematic manner, well-known natural phenomena into protocols for distributed systems.

AB - We propose a framework to translate certain subclasses of differential equation systems into distributed protocols that are practical. The synthesized protocols are state machines containing probabilistic transitions and actions, and they show equivalent stochastic behavior to that in the original equations. The protocols are probabilistically scalable and reliable, and are derived from two subclasses of equations with polynomial terms. We prove the equivalence of protocols to the source equations. Rewriting techniques to bring equations into the appropriate mappable form are also described. In order to illustrate the usefulness of the approach, we present the design and study of scalable and probabilistically reliable protocols for migratory replication and majority selection. These two protocols are derived from natural analogies represented as differential equations - endemics and the Lotka- Volterra model of competition respectively. Well-known epidemic protocols are also shown to be an output of the framework. We present mathematical analysis of the protocols, and experimental results from our implementations. We also discuss limitations of our approach. We believe the design framework could be effectively used in transforming, in a very systematic manner, well-known natural phenomena into protocols for distributed systems.

KW - Distributed Protocols

KW - Endemic Protocols

KW - Probabilistic protocols

KW - Reliability

KW - Scalability

KW - Science of Protocol Design

UR - http://www.scopus.com/inward/record.url?scp=10444230311&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=10444230311&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:10444230311

SP - 216

EP - 225

ER -