The design of novel distributed protocols from differential equations

Indranil Gupta, Mahvesh Nagda, Christo Frank Devaraj

Research output: Contribution to journalArticle

Abstract

This paper proposes a framework to translate certain subclasses of differential equation systems into practical protocols for distributed systems. The generated protocols are intended for large-scale distributed systems that contain several hundreds to thousands of processes. The synthesized protocols are state machines containing probabilistic transitions and actions, and they are proved to show equivalent stochastic behavior to the original equations. The protocols are probabilistically scalable and reliable, and have practical applications in large-scale distributed systems, e.g., peer to peer systems. In order to illustrate the usefulness of the framework, it is used to generate new solutions for the problems of (a) responsibility migration (giving rise to a novel model of dynamic replication), and (b) majority selection. We present mathematical analysis of these two protocols, and experimental results from our implementations. These two protocols are derived from natural analogies that are represented as differential equations-endemics and the Lotka-Volterra model of competition, respectively. 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)
Pages (from-to)95-114
Number of pages20
JournalDistributed Computing
Volume20
Issue number2
DOIs
StatePublished - Aug 1 2007

Keywords

  • Differential equations
  • Distributed protocols
  • Endemics
  • LV
  • Probabilistic protocols
  • Reliability
  • Replication
  • Scalability
  • Science of protocol design
  • Voting

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computational Theory and Mathematics

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

  • Cite this