On the Design of Distributed Protocols from Differential Equations

Gupta, Indranil

Permalink

https://hdl.handle.net/2142/10820 Copy

Description

Title

On the Design of Distributed Protocols from Differential Equations

Author(s)

Gupta, Indranil

Issue Date

2004-05

Keyword(s)

Distributed Systems

Abstract

We propose a framework to translate systems of differential equations into distributed protocols. The synthesized protocols are state machines containing probabilistic transitions and actions, and they show equivalent stochastic behavior to that in the original equations. We apply the framework to the Lotka-Volterra model of competition, in order to design a scalable and probabilistically reliable protocol for majority selection (and thus scalable and eventual consensus). We propose two subclasses of equations with polynomial terms, and prove the equivalence of protocols generated by the proposed mapping techniques to the original differential equations. The protocols are probabilistically scalable and reliable. Equation rewriting techniques are also described. Endemic protocols for migratory replication, and well-known epidemic protocols are also shown to be generated using this design methodology. 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, albeit in a systematic manner, well-known natural phenomena into protocols for distributed systems.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/10820

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections