Distributed Computing manuscript No.(will be inserted by the editor)The Design of Novel Distributed Protocols from Differential EquationsIndranil Gupta, Mahvesh Nagda, Christo Frank Devaraj{indy ,nagda,devaraj}@cs.uiuc.eduDept. of Computer Science201 N. Goodwin Ave.University of Illinois at Urbana-ChampaignUrbana, IL, USA 61801.Ph: 1 217 265 5517Fax: 1 217 265 6494Summary. This paper proposes a framework to trans-late certain s ubclasses of differential equation systemsinto practical protocols for distributed systems. The gen-erated protocols are inten ded for large-scale distributedsystems that contain several hundreds to thousands ofprocesses. The synthesized protocols are state machinescontaining probabilistic transitions and actions, and theyare proved to show equivalent stochastic behavior t o theoriginal equations. The protocols are probabilistically scal-able and reliable, and have practical applications in large-scale distributed systems, e.g., peer to peer systems. Inorder to illustrate the usefulness of the framework, itis used to generate new solutions for the problems of(i) responsibility migration (giving rise to a n ovel modelof dynamic replication), and (ii) majority select ion. Wepresent mathematical analysis of these two protocols, andexperimental results from our implementations. Thesetwo protocols are derived from natural analogies that arerepresented as differential equations - endemics and theLotka-Volterra model of competition respectively. We be-lieve the design framework could be effectively used intransforming, in a very systematic manner, well-knownnatural phenomena into protocols for distributed systems.Key words: Science of Proto c ol Design, DifferentialEquations, Distributed Protoc ols, Scalability, Reliability,Replication, Endemics, Voting, LV, Probabilistic Proto-cols.1 IntroductionMuch attention has been paid to studying the scalabil-ity and reliability of distributed protocols that run in-side large-scale distributed systems containing hundredsto thous ands of processes, such as peer to peer systems,the Grid, the Internet, and the Web. However, the sci-ence of design of scalable, efficient, and reliable protocolsfor such large-scale distributed systems remains a diffi-cult problem. In this paper, we describe a frameworkto translate sets of differential equations (called a “sys-tem of differential e quations”, or abbreviated as “equa-tion system”) into a protocol for a large-scale distrib-uted system. The techniques generate a state machinewhere states are derived from variables in the originalequations, and actions and transitions are derived fromthe terms in the original equations. The source equationsystems are required to be in a certain form - we de-scribe this through a ta xonomy, and also present equa-tion rewriting techniques to enable conversion of otherequation systems to the appropriate mappable form.In order to illustrate practical utility of the presentedmethodology, we present two case studies where naturalprocesses represented as differential equations are usedto design practicable protocols for a dynamic and migra-tory res ponsibility migration scheme a nd for probabilis-tic majority selection. The two protoco ls are respectivelycalled endemic replicatio n and the Lotka-Volterra (LV)protocol.Previously, differential equations have been used tostudy and analyze algorithmic solutions to problems suchas indep e ndent vertex sets and degree distributions [27],3-SAT [1], randomized load balancing [19], etc. The an-alyzed solutions are usually rando mized algorithms.However, little of the above wo rk has addressed theconver se direction, i.e., a design methodology to trans-late differe ntial equations into distributed protocols. Sucha methodology can be invaluable because scientists andresearchers in various scientific disciplines express theirideas and results by using the language of differentialequations. These ideas can then be systematica lly con-verted into distributed protocols that consequently havewell-known behavior (by virtue of the original equations).Our protoc ols can be seen as a varia nt of probabilis-tic I/O auto mata [28], however the cited work gives abroad spe c ification of protocols, rather than a frameworkfor building and analyzing protocols. Several randomizedprotocols have been proposed to circumvent the FLP im-possibility of consensus result [12], starting from Rabin’swork in [21]. Distributed computing with infinitely manyprocesses, and the relation to finite groups, was studiedin [16,18,19]. Strogatz’s textbook [25] gives a thorough2 I. Gupta et al: Designing Novel Distributed Protocols from Differential Equationscoverage for the analysis of non-linear dynamic equationsystems.The protocols generated by our framework have thecommon characteristics that they offer probabilistic reli-ability, utilize low and scalable bandwidth at each process,and have low co nvergence times. Most importantly, thedistributed protocol inherits the stochastic behavior ofthe original differential equation sy stem, e.g., the exis-tence of stable equilibrium points in the original equa-tions implicitly map into self-stabilizing behavior in theprotocol. The mathematica l analysis of these protocolsborrows techniques from the study of non-linear dy nam-ics. One particular style using phase portraits and simpleperturbation a nalysis is appropriate for our goals, andhas not been used befor e to study distributed protocols.The protocols are intended for asynchronous networksettings, however our analysis makes certa in simplifyingassumptions.In summary, the contributions of this paper are:(i) A novel framework to translate differe ntial equations,from two subclasses, into equivalent distributed proto-cols;(ii) A natural taxonomy of differential equations, andequation rew riting techniques tha t facilitate translation;(iii) Use of this framework to design new scalable proto-cols for majority selection and responsibility migration;(iv) Use of analytical techniques from the study o f non-linear dynamics in analyzing distributed protocols; and(v) A toolkit called DiffGen that when given differentialequations in Mathematica-like format, spews out compi-lable and executable C code.System Model: We assume a closed g roup G of Nprocesses, communicating over an asynchronous network.The closed group assumption means that there are nojoins by new processes; simulations show that our proto-cols work in open gro ups. For s implicity, our
View Full Document
Unlocking...