From: Bach Duy Bui Sent: Tuesday, March 07, 2006 9:30 AM To: Indranil Gupta Subject: 598ig review 03/07 The Design of Novel Distributed Protocols from Differential Equations Bach Duy Bui - 598IG I. SUMMARY This paper proposes a framework to translate differential equations, from two subclasses i.e. CompletelyPartitionable equation systems and Restricted Polynomial equation systems, intoequivalent distributed protocols. The paper gives a taxonomy of differential equations and definition of the abovementioned equations. The proposed techniquesgenerate a state machine where states are derived from variables in theoriginal equations, and actions and transitions are derived from the terms in original equations. As to completely partitionable equation systems, the technique translates each positive-negative term pair into an action where the action is executed only by a process in the state whose differential funtion has negative term. Each process uses a parameter called protocol period duration in order to decide what time the next action will be executed at that process. The nature of an action depends on the term T i.e. if term ?T = ?c.x the action is a flipping action, if term T is of the type ?T = ?c.xix,fx,T .y2X?xyix,fx,T the action is one-time sampling. The authors also used analytical techniques from the study of non-linear dynamics to analyze distributed protocol parameters such as errors, message complexity, effect of failures. The authors demonstrated the effectivenessof the method through two applications: majority selection and responsibility migration. A responsibility migration protocol is designed based on the endemic equation. This equation is restricted polynomial and completely partitionable, thus the abovementioned framework is applied to design the protocol. Analitical analyses of the protocol are given to demonstrate how the framework-generated protocols are to be studied. A majority selection is designed based on Lotka-Volterra model. The original equations are rewritten to be completely partionable which are applicable to the framework. The analyses and simulations show the correctness and effectiveness of the protocols. The authors also discuss other related issues (i) how to map equations system that are completely partitionable but not restricted polynomial (ii) how to map equations that are not completely partitionable II. COMMENTS The paper demonstrate an interesting topic where through a mathematically systematic framework largescale natural phenomenons with desirable characteristics are converted to large-scale distributed systems with the same characteristics. There are many other lessons that we can learn from nature, I wonder how much we can conver that learning into machinaries of large-scale distributed systems. The question is which classes of the natural phenomenons can be employed in large-scale distributed system. And if we can find a framework for more general differential equations. A protocol family approach to survivable storage infrastructures Bach Duy Bui - 598IG I. SUMMARY The authors of this paper argue that hardcoded approach in designing a faul-tolerant system limits the utility of the system incurring unnecessary cost as well as limits user into a specific fault model. They advocate an alternative approach, in which the decision of which faults to tolerate is shifted from design time to data-item creation time which achieves through a family of protocols. Four main parameters are used to differentiate members of the protocol family: (i) the timing model: synchronous or asynchronous timing (ii) the storage-node failure model: a hybrid failure model of storage-nodes mixing crash failures, omission failures, or crash-recovery failures with Byzantine failure (iii) the client failure model: member of the protocol family tolerates crash client failures and may tolerate Byzantine client failure (iv) node repair allowance: member of the protocol family either allows, or does not allow, clients to perform repair II. COMMENTS The selection of right protocol family member is very important. In the proposal, this process is shifted from the system designer to system operator. The question of how to choose a correct family member need to be investigated carefully. From: Michael Earnhart [mearnhart@gmail.com] Sent: Tuesday, March 07, 2006 9:19 AM To: Indranil Gupta Subject: 598ig review 03/07 Michael Earnhart CS598 IG 03/7/2006 Summary A Protocol Family Approach to Survivable Storage Infrastructures and Implementing Declarative Overlays In A Protocol Family Approach to Survivable Storage Infrastructures they are creating a system whereby the fault tolerance is more fine grained. Allowing a system to create a fault tolerant storage system for specific files while remaining non fault tolerant for temporary files or unimportant data. This system is designed from its inception to be used on brick type systems where each node is constructed of commodity hardware and there are a significant number of them. This model has been very prolific of late due to the decreasing cost of still rather impressive computer systems. The reason it was designed for this type of hardware implementation is that it fits the bill nicely because as the brick model is designed to be rather generic and easily scalable this protocol provides likewise with the file system software. They achieve scalability with protocol processing on the client and achieve redundancy by using erasure codes. The failure model provides a hybrid approach allowing for crash failures, omission failures, and crash-recovery. This system provides an interesting overview of a very flexible system for redundant storage. The ability to have fine grained control of the redundancy of different files is a powerful idea and could be applicable in many systems. Also the general idea of moving from very specific implementations to this very generic approach is very attractive for simplifying administration and deployment. In Implementing Declarative Overlays the authors are attempting to build a generic system for describing and building overlay networks. The motivation is that currently all overlay networks are unique programs that are non trivial tasks to implement nor debug. Therefore if there were a better more directed way of enumerating these network structures then perhaps the develop and debug cycle would be lessened and the research would be deepened. This paper suggest the use of Overlog as the declarative language because the description fo these networks are remarkably concise. After they define the language to some extent the paper shows two implementations using the Overlog language as the implementation tool. First is the Narada Mesh and then the more complex Chord example. They claim both are fully functional and show all the rules they created to implements them. Also there is some discussion of aspects of the language itself such as typing, and scoping. The final example of the Chord DHT is then evaluated for performance. Overlog does provide a reasonable implementation of chord but in highly dynamic situations the Overlog version of chord suffers dramatically. In conclusion they wrote that future topics would be to prove the breadth of Overlog by implementing other overlay networks and emphasizing the sharing property of this language. The strength of this paper is in its generic analysis of overlay networks. This provides a very powerful tool to implement overlay networks especially for simulation purposes and for non performing networks. Also their analysis is very compelling and honest such that they actually show where their system essentially breaks down. I appreciated their sufficient analysis and also the discussion on the topic. The problems with this approach is that indeed the number of rules or lines of code is fairly small even in a complex dht like chord but each line is rather complex itself. I was not able to easily understand the syntax of the language because it is clear to me that it is very difficult to such a system. Therefore I would argue to some extent this system provides a more simple creation cycle but perhaps even a worse readability and hence maintenance becomes more difficult. From: mbakht@gmail.com on behalf of Mehedi Bakht Sent: Tuesday, March 07, 2006 9:12 AM To: Indranil Gupta Subject: CS 598 IG Review : 6th March 2006 Title: A protocol family approach to survivable storage infrastructures Summary: This paper proposes a design approach that enables multiple failure models to be supported in a single server implementation by using family of protocols. Fault tolerant storage systems have to make many design choices on whether the system will be synchronous or asynchronous, whether the system has to tolerate fail-stop faults or Byzantine faults, etc. Traditional approaches required separate implementations for each combination of requirements. This paper demonstrates that the different requirements can be supported by a family of protocols, which differ in the algorithm used, all using a common server and client implementation. This approach has the additional benefit of allowing fault tolerance properties to be separately specified for each data element. Comments: Solution to a specific problem usually fares better than a generic solution in terms of performance, optimum resource utilization, etc. So it would have been great if the authors could show how the proposed protocol family approach performs against solutions tailored for specific fault models in practice. Title: The Design of Novel Distributed Protocols from Differential Equations Summary: This paper proposes a framework for converting differential equations into protocols for distributed systems. This design methodology enables many problems of interest to be first formulated using differential equations, analyzed and then converted into practical protocols. The paper contains two case studies that demonstrate the application of the design framework: 1. Responsibility Migration - It uses an endemic protocol designed from differential equations modeling an endemic infectious disease in a closed human population. The state machine has 3 states (receptive, stash, and averse), with state transitions occurring from Stash->Averse->Receptive->Stash. 2. Majority Selection Problem - It uses the Lotka-Volterra (LV) protocol derived from a state machine with 3 states. The actions are dictated by the flipping and one-time-sampling methods. Comments: I never had any idea that differential equations could be used to design protocols. I could not understand some of the mathematically involved sections of the paper. From: Juan Jose Jaramillo Jimenez Sent: Tuesday, March 07, 2006 9:10 AM To: 'Indranil Gupta' Subject: 598ig review 03/07 1 A protocol family approach to survivable storage infrastructures 1.1 Summary The paper proposes a new approach for survivable storage of data. The main idea is that instead of hard-coding the chosen fault model during the design stage of the access protocol, the decision of which faults to tolerate is taken during the data-item creation time. To achieve this, the authors propose a family of access protocols that share a common server implementation and a client-server interface; thus, the different failure models are supported by changing the number of storage-nodes used and the read-write thresholds. One goal achieved with this protocol family is that not all data must incur in the costs that must be paid in order to store sensitive data, allowing different applications to specialize their use of the common infrastructure. Since most processing is done at the clients, rather than in the servers, the system is scalable; further, there is no need to implement server-to-server communication that can become a bottleneck problem. It also achieves a general server that is independent of the assumed failure model. The authors identify four main parameters that differentiate the members of the protocol family: (1) the timing model (asynchronous vs. synchronous members), (2) storage-node failure model (crash, omission, crash-recovery, Byzantine or hybrid failures), (3) client failure model (same failures as in 2) , and (4) repair by clients (whether or not clients can rewrite a data fragment that is incomplete). Finally, the authors argue that this approach can be used in any niche situation by simply adapting those parameters to the desired fault model. 1.2 Comments I find interesting the approach of the authors that advocate not making the whole system incur the same costs to different kinds of backed data. However, it remains the question whether this approach makes unnecessarily complex the members, since they would have to choose which fault model to use according to the data that is about to be stored. Maybe a possibility could be making different client members tailored to different fault models, all using the common infrastructure. 2 Implementing Declarative Overlays 2.1 Summary Designing, building and adapting overlay networks is a time consuming process. In order to solve this, in this paper is proposed P2, a declarative logic language that expresses overlay networks in a compact and reusable form. The objective of the paper is not to capture all possible optimizations in the first generation of the system, but demonstrating that the declarative approach is feasible and practical. The idea is that P2 intends to simplify the process of selecting, implementing, deploying and evolving an overlay network design. The main advantages are ease of implementation and sharing code, decomposing code into logically reusable units. The approach is based in three components: (1) the use of relational tables to represent overlay state, (2) a high-level declarative language that specifies logical properties and behavior of the network (based on the Datalog query language), and (3) graphs of dataflow elements to represent runtime information processing. The authors present two examples of overlay networks declared with P2: Narada and Chord. Their experimental results show that although P2's performance is below C or C++ implementations of the overlay networks, its performance is quite acceptable, showing the feasibility of the approach. 2.2 Comments I found quite interesting the paper, since I am not familiar with declarative languages. It was interesting to understand a new concept design based on those languages. From: ercanucan@gmail.com on behalf of Ercan Ucan Sent: Tuesday, March 07, 2006 9:10 AM To: indy@uiuc.edu Subject: "598ig review 03/07" The Design of Novel Distributed Protocols from Differential Equations --------------------------------------------------------------------------------------------------- Problem Addressed: The aim of this paper is to present a design of new distributed protocols. Authors mainly propose a framework to translate certain subclasses of differential equation systems into practical protocols for distributed systems. Main intention is to use these protocols in large-scale distributed systems which contain several hundreds to thousands of processes. Using this design framework, they aim to transform well-known natural phenomena into distributed protocols. Approach Taken & Comments: Authors propose a systematic framework that translates systems of differential equations into practical distributed protocols. The basic equation systems considered have the form dx/dt = _f(_X ). Here, _X is a vector of the finite-sized variable set X, _f is an |X|-sized vector of functions each in |X| variables, and t is the time variable. The idea is that, if the terms on the right hand sides of these equations are polynomial and can be matched into positive-negative pairs, the protocol generated by the framework has equivalent behavior to the equation in an infinite sized distributed group and this is proved in the paper. Here is the approach: The framework creates a state machine with one state per variable in the original equations, and probabilistic actions derived from terms in the equations. Equivalence means the time-based variation of variable values in the equations is the same as the variation of fractions of nodes in corresponding states in the protocol. Stable equilibrium points in the equation map to fault-tolerance and self-stabilizing behavior in the protocol, simplicity of terms maps to scalable communication, and stochastic properties map to untraceability and resistance to churn. The framework also includes translation techniques for more general classes of differential equations than the above. In the paper, there is a section that gives a taxonomy of differential equations. However, there are limitations for these general classes meaning that equivalence to equations with arbitrary terms may be unscalable. Techniques to rewrite differential equations into a format that allows translation by the framework were also presented. Conclusion: Both analysis and experiments with periodic versions of these protocols point out that these protocols are probabilistically scalable and reliable. This framework and the DiffGen toolkit can be used as a useful resource to a designer of protocols since they enable systematic conversion of ideas and results from other scientific disciplines into practical distributed system designs. A protocol family approach to survivable storage infrastructures ------------------------------------------------------------------------------------------ Problem Addressed: Normally, the fault model decision is hard-coded during the design of an access protocol. This traditional approach has two significant drawbacks. First, the utility of the resulting system is limited meaning that in some environments, the system incurs unnecessary costs, and, in others, it cannot be deployed. The natural consequence is distinct system implementations for each distinct fault model. Second drawback is all users of any given system implementation must use the same fault model, either paying unnecessary costs or accepting more risk than desired. In this paper, the authors present an alternative approach, in which the decision of which faults to tolerate is shifted from design time to data-item creation time. Approach Taken & Comments: The shift mentioned above is achieved through the use of a family of access protocols. Those access protocols share a common server implementation and client-server interface. A protocol family supports different fault models in the same way that most access protocols support varied numbers of failures. The main method behind is simply changing the number of storage-nodes utilized, and some read and write thresholds. A protocol family enables a given storage infrastructure to be used for a mix of fault models and allows the number of faults tolerated to be chosen independently for each data-item. The authors of the paper have developed a protocol family for survivable storage infrastructures in their previous works. Each member of this protocol family exports a block-based interface. The survivable storage infrastructure consists of versioning storagenodes that offer a single interface for all data, regardless of the fault model. Clients of the infrastructure realize a particular model for a data item by interacting with the right number of storage-nodes. Four main parameters that differentiate members of the protocol family are presented in the paper. These are the timing model, the storage node failure model, the client failure model, and whether clients are allowed to perform repair. In order to show feasibility of their approach, the authors implemented a read/write access protocol family for survivable storage. These are initial results only. However, they show that the protocol family approach to constructing survivable infrastructures is worthy of further research. -- Ercan Ucan - eucan2@uiuc.edu Graduate Student Computer Science Department University of Illinois at Urbana-Champaign ------------------------------------------------------------ From: Long Hai Vu Sent: Tuesday, March 07, 2006 8:56 AM To: Indranil Gupta Cc: Long Vu Subject: cs598ig review 03/07/06 Name: Long Vu CS598IG-Spring 2006 REVIEWS A protocol family approach to survivable storage infrastructures In this paper, authors propose a protocol family for survivable storage infrastructure. According to them, the type of faults to tolerate is decided in data-item create phase rather than design time phase in traditional approach. Moreover, a single implementation could be deployed in different environments and a single development could satisfy the specific requirements in term of survivability. In this approach, regardless of fault model, the storage infrastructure contains versioning storage nodes with a single interface for processing and accessing data. A peer in this environment could learn the model of a particular data item by exchanging messages and interacting with a set of storage nodes. The protocol family in this paper allows a certain storage infrastructure to be used for a mix of fault model and the number of faults to be chosen independently for each data item. In this protocol family, each peer could populate a block-based interface with the rest of the overlay. Using these shared storages, peers could work consistently and synchronously. The Design of Novel Distributed Protocols from Differential Equations In this paper, authors present a framework which translates some particular subclasses of differential equation systems into practical protocol which is probabilistically scalable and reliable for distributed systems such as peer to peer systems. In essence, the protocol is a state machine whose transitions and actions are probabilistically decided based on terms in the original equations. Moreover, the practical protocols generated by this approach are proved to be equivalent to the original equations. They describe two protocols responsibility migration, majority selection, their mathematical analysis, and experimental results. Contributions: - Propose a promising and systematic framework to generate practical protocols from two subclasses, given the differential equations. - Equation rewriting techniques - Use the proposed framework to design newly scalable and reliable protocols for responsibility migration and majority selection - Use of a analytical techniques of non-linear dynamics in analyzing distributed protocols - Implement DiffGen toolkit to convert the differential equations into executable C code In the future, we could improve this work to have the general translation of differential equation classes into practical protocols. From: Maifi Khan [maifi.khan@gmail.com] Sent: Tuesday, March 07, 2006 5:36 AM To: Indranil Gupta Subject: 598ig review 03/07 Title: Implementing declarative overlays. Summary: This papers deals with the challenge of building overlay networks in an efficient way and proposes a declarative logic language P2 that can be used for this purpose. P2 can be used as a service or a library. Instead of using traditional finite state machine which is pretty cumbersome for large systems, P2 uses data flow framework for maintaining overlays. In Overlog one can specify physical distribution properties like where tuples will be physically stored etc. They model overlay as a distributed data structure which is represented by a set of structured relations. Application submits to P2 the required logical description of the overlay network and P2 executes this to maintain routing structure, resource discovery. In P2, one can specify the system in a compact and reusable form. Discussion: According to their implementation P2 can express Narada style mesh network in only 16 rules and Chord only in 47 rules. So P2 is pretty concise and easier to maintain. Moreover it is easier to reuse code or subset of rules. By combining logical specification and dataflow graphs, they provide a better solution from software engineering perspective also, namely- better scooping, typing, encapsulation and reuse. Modularity is also useful for bootstrapping the system. One of the tradeoff is between code size and efficiency. It may not be always clear which is better and vary with application requirements. P2 also does not provide optimized execution as C or Java but still comparable performance is achieved. For future extension, incorporating security features in the framework will be a challenging one. Another important aspect is how to support different types of transport services based on different types of application. Title: A protocol family approach to survivable storage infrastructure. Summary: The main idea of this paper is to shift the decision of fault tolerance from design time to data creation time. As various types of data require various types of fault tolerance and also vary in importance, the same hard coded fault model is not justified and sometimes are inefficient and causes either extra cost or extra risks. They proposed a solution that makes the fault tolerance decision during data creation time. Four parameters determines the membership of the protocol family – timing model, storage node failure model, client failure model and repair by clients. They developed a protocol family for survivable storage infrastructure which consists of versioning storage nodes that provides a single interface independent of failure model. Clients of the infrastructure achieves the required model by using right number of storage nodes. Thus this type of system can be reused for different types of fault model without modification. Discussion: Using a protocol approach enables reusing server implementation and single deployment can support different requirement without incurring extra cost for less sensitive data. The hard part of using such a model is how to decide the protocol family members. As most of the times there are conflicting factors involved. Also a deep understanding of the application domain will be required to make a "wise" decision which is not trivial and demand expert and experienced personnel. It will be also problematic if there is a problem with the underlying implementation which is an inherent problem with code reusing. From: Hussam Hasan Abu-Libdeh Sent: Tuesday, March 07, 2006 2:44 AM To: Indranil Gupta Subject: 598ig review 03/07 The two papers that i want to review are: 1. Implementing Declarative Overlays. 2. A protocol family approach to survivable storage infrastructures. --------------------------------------- Implementing Declarative Overlays : --------------------------------------- Overlay networks are used today in a variety of distributed systems ranging from ?le-sharing and storage systems to communication infrastructures. However, designing, building and adapting these overlays to the intended application and the target environment is a difficult and time consuming process. To ease the development and the deployment of such overlay networks the paper implemented P2, a system that uses a declarative logic language to express overlay networks in a highly compact and reusable form. P2 can express a Narada-style mesh network in 16 rules, and the Chord structured overlay in only 47 rules. P2 directly parses and executes such specifications using a data ?ow architecture to construct and maintain overlay networks. This paper has investigated the feasibility of expressing overlay networks in a declarative language, and then directly executing the resulting speci?cation to construct and maintain the overlay network. The approach looks promising: overlays can be speci?ed extremely concisely, yet with enough detail to be executed with performance and robustness acceptable for many applications. Furthermore, OverLog makes it easy to alter overlay routing algorithms without reimplementing complex state machines. The current system successfully compiles and runs specifications for all overlays discussed in this paper. The planner does not currently handle directly some of the more involved constructs of the OverLog language, such as multi-node rule bodies and the logic of negation; slightly wordier rule rewrites allow us to circumvent these limitations, as the next design iteration of the planner takes shape. Comment: ------------ This paper claims that the performance of this approach is acceptable, however i was wondering how does that approach measure up to C or C++ in real-life situations ?? --------------------------------------------------------------------- A protocol family approach to survivable storage infrastructures : --------------------------------------------------------------------- A protocol family supports a variety of fault models with a single client-server protocol and a single server implementation. Protocol families shift the decision of which types of faults to tolerate from system design time to data creation time. With a protocol family based on a common survivable storage infrastructure, each data-item can be protected from different types and numbers of faults. Thus, a single implementation can be deployed in different environments. Moreover, a single deployment can satisfy the speci?c survivability requirements of different data for costs commensurate with its requirements. Replacing protocols suitable for a single purpose with protocol families allows a single implementation to be used in many environments and a single deployment to serve distinct requirements efficiently. The implementation of the read/write access protocol family for survivable storage demonstrates the concept’s feasibility. The paper has had early successes developing a read-modify-write protocol family. The promising initial results indicate that the protocol family approach to constructing survivable infrastructures is worthy of further exploration. Comments: ------------- The paper presents the ideas but doesn't mention anything about actual implementation and experimental results. It would have been nice to seen some of those facts to back up their ideas. From: Mehedi Bakht Sent: Tuesday, March 07, 2006 1:13 AM To: Indranil Gupta Subject: RE: cs598ig survey Hi Professor Gupta, Thanks for your prompt and detailed reply. I do understand that all the other students taking the course also have their own midterms, presentation in other courses, projects, etc. So relaxing the requirement for me will be grossly unfair. I am really grateful that you still made an exception and extended the submission deadline for me. I know I should not be unreasonable and request for anything more. But I just wanted to let you know that my midterm for Distributed Systems (CS 425) will take place from 3:30 PM to 4:45 PM. So if you could extend that deadline by few hours - so that I can write the reviews after the midterm - then it would be really helpful. I apologize for requesting too much favor. Mehedi ________________________________ From: Indranil Gupta Sent: Mon 3/6/2006 10:15 PM To: Mehedi Bakht Subject: RE: cs598ig survey Hi Mehedi, I can give you an extension until Thursday office hours (5 pm), but not beyond that. I can relax the review submission rules for medical reasons and for interviews, but unfortunately if I start to relax review rules for midterms in other exams, I will begin to have a difficult time since everyone has exams at some point of time or the other. I hope you understand why I cannot grant you a longer extension. Indy Indranil Gupta Asst. Prof. Dept. of CS UIUC http://kepler.cs.uiuc.edu From: Muyuan Wang [mwang2@uiuc.edu] Sent: Tuesday, March 07, 2006 12:03 AM To: Indranil Gupta Subject: 598ig review 03/07 The Design of Novel Protocols from Differential Equations Summary: The paper proposes a framework to translate two subclasses of differential equations into distributed protocols. The synthesized protocols are state machines containing probabilistic transitions and actions, and have the same stochastic behavior with the original equations. In order to do that, first, a natural taxonomy of differential equations and the related reformatting method is provided. The (order 1) differential equation systems are categorized into two types: Polynomial Equation System and Non-polynomial System. Furthermore, among the polynomial equation system, one particular subclass, the Restribted Polynomial Equation System, is defined, which can be translated into distributed protocols. Then, another classification scheme is provided, and two categories Complete Equation System, and Completely Partitionable Equation Systems are introduced. Second, the translation framework is introduced, to map a differential equation system to protocols. After that, translation case studies for responsibility migration and majority selection problem are provided. Finally a toolkit named DiffGen that can translate differential equations in Mathematica-like format into executable C code is introduced. Comments: It is really a cool and very exciting idea to translate the differential equations directly into the distributed equations. Honestly, I cannot understand the heavy math in this paper. My questions are: it seems that the translatable differential equations are only a small fraction of all the differential equations; that is okay, I think, the problem is, are the translatable ones also 'useful' ones? What kind of differential equation system will generate 'high quality' distributed systems? Maybe this paper has already answered these questions, or maybe these questions should not be answered here. Anyway, I don't know and I am very curious about that. A protocol family approach to survivable storage infrastructures Summary: This paper provides an approach that can determine which types of faults to tolerate at the time of data creation, instead of system design time. Thus, each data-item can be protected from different types and numbers of faults, which gives the data more safety as well as reducing the overhead of the fault tolerance system. The method they used is called family protocol approach, namely, a bunch of protocols are used adaptively, to achieve the best results. Four parameters are used to distinguish the members of the family of protocols, which are: timing model, storage-node failure model, client failure model, and repair by clients. Based on the criterion, protocols in the protocol family are chosen. Comments: the novelty of this paper is to adopt the protocol family that is not configurable and logically related, thus provides the user more ease. The protocols in a family share a common server implementation and client-server interface. However, I am not sure how this sharing is achieved. From: Ravishankar Sathyam Sent: Monday, March 06, 2006 9:37 PM To: Indranil Gupta Subject: 598ig review 3/7 Ravi Sathyam The Design of Novel Distributed Protocols from Differential Equations Summary: This paper proposes a framework that converts various sets of differential equations into a protocol for a distributed system. The generated protocols are said to have probabilistic reliability, low and scalable bandwidth utilization, and low convergence times. The paper first describes a taxonomy of differential equations in order to properly classify them. Here, if f is a function consisting of various terms, then one can classify equation systems into two types: Polynomial Equation Systems (for each equation in the system, f can be written as a sum of polynomial terms) and Non-polynomial Equation Systems. Also, based on the structure of f, equation systems can also be classified into two types: Complete Equation Systems and Completely Partitionable Equation Systems. Translation of completely partitionable equation systems into a protocol involves creation of a state machine that contains one state for every basic variable in the system, and have actions corresponding to these states. These systems consist of even positive-negative pairs, each of which can be translated into an action. Here, if the negative term occurs in the one component of the function (say fx) and the positive term occurs in the other component (fy), then an action is executed by a process in state x into state y. Each process contains a parameter known as protocol period duration. This is used by the process to determine when the next action is going to be performed (after Tnext units). After Tnext units of time, the process will again randomly pick an action from the number of actions corresponding to the number of negative terms in fx. The paper then provides an analysis of the derived protocols. Here, it is initially it is shown that for these protocols, finite analysis is equivalent to infinite analysis. Using this, it is shown that that flipping and one-time sampling actions are sufficient in mapping completely partitionable and restricted polynomial equation systems into distributed protocols that have equivalent behavior. The paper then describes protocols designed for two purposes – Responsibility Migration and Majority Selection. For responsibility migration (with a probabilistic safety), an endemic protocol designed from differential equations for endemic infectious diseases is described. For this, three states are derived (receptive, stash, immune), and processes are responsible iff they’re in stash state. Basically, processes in various states either change their states or remain in the same state based on the flipping action. The paper notes that equilibrium in the endemic equations occur in two points, and the second equilibrium point is more desirable since it guarantees safety. It is shown that this equilibrium point is self-correcting, stable and converges exponentially quickly. For majority selection, differential equations are designed using the LV model, which is also used to model the number of sheep and rabbits in a given ecosystem. Again, based on the differential equations, a state machine is generated. Four equilibrium points are generated from this model, out of which two are said to be stable. Also, this LV protocol is shown to be self-stabilizing, and has exponential convergence complexity near each of the stable equilibrium points. In the experiments for responsibility migration, it is seen that the number of stashers stabilizes very quickly, which keeping the communication overhead and network traffic low, and decaying oscillations in the number of stashers and receptives. Also, increasing the protocol period merely makes the convergence slower. Also, in the experiments for LV protocol, convergence time is directly proportional to the number of processes crashing at random (the effect of massive failures). Convergence times are also inversely proportional to the p value. Furthermore, the paper talks about a new technique known as tokenizing, which are used to approximately map equations systems that are completely partitionable, but are not restricted polynomial. A generic sampling technique is also described to approximately map equations that aren’t polynomial. Finally, the paper describes a software toolkit, DiffGen, that consists of a parser, rewriter, and code generator and basically takes in a set of differential equations as input and spews out ready-to-deploy C code as output. Comments: I have not understood how the second equilibrium point guarantees safety. Moreover, I feel that coming up with a concept for designing protocols based on the application (aka endemic diseases for a protocol for responsibility migration and LV model for majority selection) is just as hard and hopefully this will be addressed someday!!! A protocol family approach to survivable storage infrastructures Summary: This paper proposes using a family of protocols, such that the decision of which faults to tolerate can be shifted from design time to data-item creation time. This is because using a single access protocol can result in more risk than desired, and also in unnecessary costs from the user’s perspective. Such a protocol family would be helpful for storage brick based systems, for example. This is because here, a single server software implementation can be reused for different environments with varying needs. The paper then highlights the protocol family that the authors have designed. Each member of the protocol family works as follows: In order to perform writes, clients need to send time-stamped frame segments to the set of storage-nodes involved in storing the data being updated. To perform a read, clients fetch the latest fragments from the storage-nodes and keep fetching additional fragments until a complete write is observed. This provides member scalability (most protocol processing is performed by clients) and server-to-server communication is not required in the case of reads and writes (thus removing a potential bottleneck with regard to the number of faults tolerated). There are four main things that differentiate members of the protocol family. These are Timing Model (synchronous or asynchronous), Storage-Node Failure Model (tolerance to a hybrid failure model), Client Failure Model, and Repair by Clients (either this is allowed or not allowed). Such flexibility can be useful for several environments. For example, synchronous timing model can be useful for LAN’s and physically isolated systems, while asynchronous models are useful since they provide resilience against DoS attacks. Other such examples are also highlighted in the paper. Comments: I suppose the greatest strength is the diversity of members in the protocol family, thus providing for deployment in various environments. However, I would have liked to have seen an implementation and an analysis versus a singular access protocol where the failure model is hard-coded. From: Raghu Kiran Ganti Sent: Monday, March 06, 2006 7:15 PM To: Indranil Gupta Subject: 598ig review 03/07 Reviews for Design Methodologies, March 7 ----------------------------------------- Paper title: Implementing Declarative Overlays Summary/Main Ideas: ------------------- This paper addresses the issue of designing, building, and adapting overlay networks based on the application by introducing a new declarative logic language to express overlay networks in compact and reusable form. It also provides a dataflow runtime after the declarative logic language (Overlog) is compiled and the overlay is being used (the system is called P2). The main contributions of this paper are: 1. Diverse set of overlays can be expressed concisely in a declarative specification language. 2. Declarative specifications can be executed as overlay maintenance protocols, which share communication, state, and computation. 3. Constructed overlays (using the specification language) have acceptable performance compared to hand-coded implementation. Applications submit a logical description of an overlay network, which is used to maintain routing data structures, perform resource discovery and optionally provide forwarding for the overlay. The overlay is modeled as a distributed data structure, represented using a set of structured relations. Thus, a typical specification of an overlay consists of *materialization* statements and a set of rules. The materialization statements declare tables along with parameters such as lifetime of tuple storage. There are various types of rules- examples include streams that generate periodic tuples, location specifiers that annotate the components of a rule to specify the node at which the tuples in question should exist. A description of an overlay in the above specification language is compiled into an executable presentation, which is similar to a dataflow graph. The authors argue that a dataflow runtime is better than a automata style runtime due to the software engineering advantages the former method provides (such as encapsulation and reuse). P2 is implemented in C++ and consists of a Datalog style parser (for Overlog), a planner, a set of dataflow element implementations, and a runtime plan executor. For a given query, it is parsed into an internal representation, the planner constructs a corresponding dataflow graph of elements, and the graph is executed by the runtime until it is canceled. The authors provide an implementation of Narada and Chord (overlay networks) by using Overlog, as a proof of concept. Comments: --------- 1. The paper provides a new declarative style language and a runtime framework to express overlays. An application can provide a description of overlay networks in Overlog, and can establish the overlay without the hassle of trying to tweak with the actual code. 2. It provides a clean interface for the user to specify any parameters which he/she requires of the overlay network. 3. The declarative language presented in the paper seems to be too complex for users to use it! It has been also observed by the authors and it would be nice to see a less complicated version of their specification language. 4. It is not quite convincing to me as to how their specification language+runtime can provide efficient optimizations, which could possibly be implemented only at the lower layer. ************************************************************** Paper title: A protocol family approach to survivable storage infrastructure Summary/Main Ideas: ------------------- This paper discusses a different approach for providing survivable storage infrastructures, where a family of protocols support a variety of fault models with a single client-server protocol and a single server implementation. The idea is very simple. The drawbacks of the traditional fault tolerant models where the fault model is hard-coded during the design of an access protocol are: 1. The utility of the resulting system is limited to certain environments only. 2. All users of any given system implementation must use the same fault model, forcing the users to pay unnecessary costs or accepting more risk than desired. This is due to the fact that the fault model is hard-coded at design process, if this decision is shifted to data-item creation time, the above problems can be circumvented. This shift is achieved by using a family of access protocols that share a common server implementation and client-server interface. Each member of this protocol family exports a block-based interface. The survivable storage infrastructure consists of versioning storage nodes that offer a single interface for all data, regardless of the fault model. The authors argue that a protocol family assists ``storage brick'' based systems by providing one server software implementation for different environments and providing differing survivability requirements for the data stored (thus different data incur different costs). They also identify four main parameters in which protocols of a given family differ: 1. Timing model - synchronous vs. asynchronous 2. Storage-node failure model 3. Client failure model - crash client failures vs. Byzantine failures 4. Repair by clients - Allow vs. dis-allow clients to perform repairs in event of failures Based on the requirements of the application and the physical environment, protocol family members can be selected appropriately. Comments: --------- 1. The idea of using a family of protocols is similar to N-version programming. 2. The paper is only a short summary of the idea and does not provide any implementation details, thus making it not very convincing. 3. As such, the overhead of implementing a family of protocols can be high. From: Praveen Jayachandran Sent: Monday, March 06, 2006 12:14 PM To: Indranil Gupta Subject: cs598ig review 03/07 CS598IG Review 03/06 Praveen Jayachandran Implementing Declarative Overlays --------------------------------- This paper addresses the issue of ease of development and deployment of overlay networks. The authors present a declarative logic language to express overlay networks in a compact and reusable form. Their chord implementation consists of only 47 rules, compared to the more than thousand line C code. The rules used to define the overlay are parsed and executed using a data flow architecture to construct and maintain the overlay, instead of the traditional finite state machine approach. The selling point of this approach is its low specification complexity and reusability of code, which is achieved at a slight expense of performance. The authors have implemented two overlay structures, namely Narada and Chord, to illustrate their point. The overlay is modeled as a distributed data structure, represented by a set of relations in a relational database. The motivating factors of this approach are clearly elucidated. The structured tables are a simple and natural representation of the network state. The tables and relationships between them are concise and easy to represent. The queries and rules can specify distributed state information in a high-level and concise manner. Also, according to the authors the relational abstraction is a natural way to reuse functionality and share routing state among different overlays. The advantages of the data flow approach as against the traditional automata based approach is also well motivated. The automata must handle any possible event in every state. However, the data flow approach provides the flexibility of scoping the events. The data flow approach does not have to deal with all types of data, contrary to the automata approach. The modularity of the data flow approach also enables encapsulation and reuse of program code. Comments: 1. The programming language defined seems quite esoteric and the learning curve seems quite large. Unless the same programmers are to implement multiple overlay structures, the steep learning curve may not be worth the time and effort. 2. Although the authors claim that the performance of their approach is acceptable, it is unclear as to how it compares with a traditional optimized C or C++ implementation. 3. Testing tools are readily available for traditional programming languages. Using this declarative approach, how easy is it to debug and correct errors in the implementation? A Protocol Family Approach to Survivable Storage Infrastructures ---------------------------------------------------------------- A protocol family approach to build storage infrastructures that can survive different types and number of faults is introduced in this paper. A protocol family supports a variety of fault models with a single client-server protocol and a single server implementation. This enables the decision of which fault and timing model to assume, from system design time to data creation time, enabling a single implementation to be deployed in different environments. The number and type of faults to tolerate can now be chosen independently for each data item. The authors point out some significant shortcomings of the traditional approach of hard-coding the fault model decision during the design of the access protocol. All users of the system have to use the same fault model. The utility of the system is limited as in some environment, the fault model assumed may be too general and wasteful, while in others it may be too specific and unusable. All data items, regardless of their criticality, would pay the same overhead costs of surviving failures. These shortcomings serve as the main motivation to develop the protocol family approach, where the fault model decision can be shifted to the data creation time. Comments: 1. As the authors pointed out, all traditional programming assumes the fault model at the design stage. How difficult is it to write code independent of the fault model assumption? 2. Can this approach be adopted to systems other than storage systems as well? 3. In application specific systems, the protocol family approach may be wasteful in terms of effort spent in developing the system.