On the design of distributed protocols from differential equations

Research output: Contribution to conferencePaperpeer-review

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
DOIs
StatePublished - 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
Country/TerritoryCanada
CitySt. John's, Nfld.
Period7/25/047/28/04

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

Fingerprint

Dive into the research topics of 'On the design of distributed protocols from differential equations'. Together they form a unique fingerprint.

Cite this