Files in this item



application/pdfOn the Design o ... Differential Equations.pdf (574kB)
(no description provided)PDF


Title:On the Design of Distributed Protocols from Differential Equations
Author(s):Gupta, Indranil
Subject(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.
Issue Date:2004-05
Genre:Technical Report
Rights 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).
Date Available in IDEALS:2009-04-14

This item appears in the following Collection(s)

Item Statistics