On the design of distributed protocols from differential equations
Indranil Sen Gupta · 2004
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.