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 language | English (US) |
---|---|
Pages | 216-225 |
Number of pages | 10 |
DOIs | |
State | Published - 2004 |
Event | Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing - St. John's, Nfld., Canada Duration: Jul 25 2004 → Jul 28 2004 |
Other
Other | Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing |
---|---|
Country/Territory | Canada |
City | St. John's, Nfld. |
Period | 7/25/04 → 7/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