(The Case for) Methodology ResearchBig PictureMore AilmentsHow do you Attack these Problems?Methodology: DefinitionAdvantages of MethodologiesAdvantages (2)Methodologies: Challenges and PotentialsInnovative Methodology: Probabilistic ProtocolsRelated Work+ModelA Working ExampleSlide 12Slide 13In Practice -- UntraceabilityIn Practice -- Effect of FailuresSlide 16In Practice -- Network TrafficA Brief Second ExampleSlide 19Slide 20A Level UpMethodology - IMethodology - IIOther Protocols from this MethodologySummarySummary (2)Slide 27Back to the Big PictureSlide 29Slides for Remaining “Methodology” PapersFuture/Ongoing WorkTranslating Natural Phenomena into Distributed Protocols2. Composable M.: Survivable Storage Architectures [Wylie et al]Wylie et alSlide 353. Innovative/Composable M.: Implementing Declarative Overlays [B.-T. Loo et al]MotivationWorking Example - OurDHTOurDHT (contd.)Slide 40That’s it!Pros and ConsSlide 43Other Methodology LanguagesBackup SlidesIs Methodology Research New?QuestionsTaxonomy of Methodologies(The Case for)Methodology ResearchIndranil GuptaMarch 27, 2007CS 525 Advanced Topics in Distributed SystemsSpring 07Big Picture•Distributed systems with large numbers of processes…–Grid, P2P systems, Web, …•…require scalable and reliable distributed protocols inside–Multicast, Replication, Voting, …Researchers design protocols to optimize message and time complexity, reliability, process overheads, etc.However, the only assistance for this design comes from research literature and experience. This is a laborious, almost “seat of the pants” approach. Leads to complex system internals, e.g., credit-card systems [Spec03], information systems [CRA], the Grid, the Internet,…Efforts to understand existing systems, and design simple, effective systems.More Ailments•A different kind of gap is the one between theory and systems. •Other fields of science have already developed methodologies–Synthesis in hardware design. [Ambrosio et al, Bluespec]–Design patterns–Methodologies are needed for maturity in a field of science.How do you Attack these Problems? Design Methodologies•Simple Thesis For any "project" or "problem", design a (i) solution, and (ii) a methodology underlying the design for the solution(s), and (iii) (optional) tie this methodology to at least one other methodology. –Calls for a new layer of Methodology Research–Does not solve the mentioned problems, but attacks them–Is more powerful than meets the eyeMethodology: DefinitionProtocol Design Methodology = An organized, documented set of building blocks, rules and/or guidelines for design of a class of protocols, possibly amenable to automated code generation. [adapted from FOLDOC]Advantages of Methodologies•“Archival” of ideas and results. •Systematic reuse of ideas and results.•Help designer systematically design new protocols with provable properties. •Theoreticians and Practitioners–Methodologies are understood by, and allow, both theoreticians and practitioners to apply their solutions more “generally” and to exchange ideas in a systematic manner.Composable MethodologiesInnovative MethodologiesAdvantages (2)•Systematic Generalization of an Approach–in a sense, a methodology captures the mode of thinking of the designer (without a psychological examination or MRI).•Systematic tie-in with existing systems•Shorten Life-span of research projects.•These advantages are especially evident after a methodology has been discovered–“If only I had realized there was an underlying design methodology, I might have designed these protocols much quicker”Methodologies: Challenges and Potentials Are there systematic protocol design methodologies? Can we automate part of protocol design? Marshall McLuhan: “Technology is an extension of our natural facilities”. Bill Gates: “Automation of any activity will magnify both its efficiencies and inefficiencies”.Innovative Methodology: Probabilistic Protocols•How does one assist the innovative process of design?Scientific disciplines use differential equations to represent ideas, results, and phenomenaBiology, Physics, Chemistry, Electrical Engg., Economics, Sociology..Many phenomena here are scalable and reliableMethodologies to translate differential equations into protocols.Potential to innovate protocols that inherit scale and reliability of original equations.We give rigorous design methodologies for this We show how to design practical protocols for real applicationsRelated Work+Model•Differential Equations used to study algorithms for independent vertex sets [Worm.95], 3-SAT [Achl.01], load balancing [Mitz.01]–Our focus is opposite direction: converting differential equations into distributed protocols•Distributed Computing with infinite number of processes, and relation to very large groups: [Kur.81, Mer.00, Mitz.01] – We analyze infinite groups•We assume an asynchronous system with no clock drift •[FLP85], Randomized protocols [Motwani text], Probabilistic I/O Automata [Lyn.97, Wu97]A Working Example•Endemic Diseases: e.g., Flu, Measles [in static populations]x= fraction of receptives, y=stashers, z=averse•translate into Migratory Replication–E.g., Persistent Distributed Storage of Files.•[R. Anderson] “Where a file once inserted, can never be deleted, even by a gun at your wife’s head”.–E.g., Migrating leader committee membership, e.g., for multicast bufferingzxydtdx yxydtdyzydtdzFlipping ActionDifferential Eqn. State MachineMap• Each Variable to a state • Each Term to an ActionOne-Time-Sampling Actionzxydtdxyxydtdyzydtdz“Endemic Protocol” for Migratory Replicationxy z MappingDifferential Equation (hence system)has a trivial and a non-trivial equilibrium point. • The trivial point is a saddle (partly stable) point.• The non-trivial point is a stable point.System analysis through Phase Portraits• Behavior starting from different initial pointsConvergence Complexity: typically exponentially fastAnalysisIn Practice -- UntraceabilitySet of stashers changes every 40.6 s (on average)No long horizontal lines No vertical stripesNo temporal or hostid-wise correlation of stasher setPerformanceIn Practice -- Effect of FailuresEndemic Protocol under Massive Failures: 50% of computers in this 100,000-computer system
View Full Document
Unlocking...