From asr32@cornell.edu Mon Apr 17 20:32:08 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.1 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.25) with ESMTP id k3I0W7225068 for ; Mon, 17 Apr 2006 20:32:08 -0400 (EDT) Received: from dreadnought.cornell.edu (r253240123.resnet.cornell.edu [128.253.240.123]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k3I0W729024627 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Mon, 17 Apr 2006 20:32:07 -0400 (EDT) Message-Id: <6.2.1.2.2.20060417000812.01de43a0@postoffice8.mail.cornell.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Mon, 17 Apr 2006 20:32:07 -0400 To: egs+summary@cs.cornell.edu From: Ari Rabkin Subject: PAPER 22 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Implementing Declarative Overlays: The authors define a declarative language, OverLog, for specifying distributed algorithms, and in particular, overlay networks. They demonstrate that even a substantial system such as Chord can be specified in a few dozen lines, with performance comparable to the reference C++ implementation. (Moreover, as our experience with databases has shown, sometimes coding at a higher level allows for automatic optimization resulting in better performance than hand-crafted code) The chief benefit of OverLog is compactness of code. However, most programmers seem resistant to using Prolog, which offers similar compactness in non-distributed contexts. Moreover, the compactness of OverLog is bought at the expense of reduced flexibility. Designers often want to specify message formats at the byte level, or the details of the underlying transport layer; OverLog makes this difficult to do. Macedon: Macedon is designed to output efficient C++ implementations of overlay algorithms from finite-state-machine descriptions. This allows quite compact descriptions of complex algorithms in a modular way. Macedon results in compact, efficient executable code from short descriptions at a higher level. The evaluation of Macedon left a lot to be desired. Counting lines of code gives only a very loose sense how complex a piece of code is, and counting semicolons is, if anything, worse. Moreover, it's not clear that writing hundreds of lines of FSM description, takes less time than writing a few thousand lines of java. Moreover, it may be easier to debug a conventinonal language than an FSM description. Lastly, like OverLog, there is the danger of constraining programmers who wish to use underlying components other than the one Macedon offers: for instance, suppose a Chord user truly wanted 128-bit rings, rather than the 32-bit identifier space that Macedon supplies. Ari Rabkin asr32@cornell.edu Risley Hall 454 3-2842 The resources of civilization are not yet exhausted. --William Gladstone From lackhand@gmail.com Tue Apr 18 01:43:33 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.2 required=5.0 tests=AWL,BAYES_00,HTML_00_10, HTML_MESSAGE autolearn=no version=3.1.0 X-Spam-Level: Received: from penguin.cs.cornell.edu (penguin.cs.cornell.edu [128.84.96.11]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.25) with ESMTP id k3I5hW229098 for ; Tue, 18 Apr 2006 01:43:32 -0400 (EDT) Received: from pproxy.gmail.com ([64.233.166.183]) by penguin.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 18 Apr 2006 01:43:10 -0400 Received: by pproxy.gmail.com with SMTP id c30so811458pyc for ; Mon, 17 Apr 2006 22:43:10 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type; b=W9PFKwUkFzsBHzFvHL4a4g1YHnXd4BhTl7IRgOsDbBjDsaefQ/cWPdMVw1CIDhiD5hSl02ELhvIpJugvCDbLCmxr/A+8KhdWxEzsdoskQ75YIXOrqo/VJC4Js1QlKVl6BZH47fe/3QXvBsyZIGOAobfholORqoKQBLQ6R0cAUow= Received: by 10.35.50.9 with SMTP id c9mr528494pyk; Mon, 17 Apr 2006 22:17:59 -0700 (PDT) Received: by 10.35.125.16 with HTTP; Mon, 17 Apr 2006 22:17:59 -0700 (PDT) Message-ID: <9aa7a97d0604172217k5d180b0dwb3b402cb1923046a@mail.gmail.com> Date: Tue, 18 Apr 2006 01:17:59 -0400 From: "Andrew Cunningham" To: egs+summary@cs.cornell.edu Subject: PAPER 22 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_Part_6079_29173591.1145337479690" X-OriginalArrivalTime: 18 Apr 2006 05:43:10.0510 (UTC) FILETIME=[FA02FCE0:01C662AA] ------=_Part_6079_29173591.1145337479690 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Andrew Cunningham arc39 Implementing Declaritive Overlays Boon Thau Loo, Tyson Condie, Joseph M. Hellerstein, Petros Maniatis, Timothy Roscoe, Ion Stoica P2 is a new technology designed to streamline and quicken the design of peer to peer, distributed systems. A side benefit is that as the code is structurally designed with no syntactic noise from procedural language constructs, code is very easily shared, reused, and repurposed. The authors use three components, relational tables to represent overlay state, high level declaritive language to specify the overlay's logical properties and behavior, and graphs of the dataflow elements to represent runtime information processing. They use structured relational tables because they are a natural representation as neighbor tables are already quite common, tables are easily represented in declarative language, and it provides a consistently-named view of all the local tables and messages at different nodes. It is claimed that OverLog, the language presented, is not designed as a Domain-Specific language for overlay specification but instead an adaption of a powerful query language to a distributed context of data and messages. However, those are nearly synonymous, in that once one reaches a distributed context, it is a quite short hop to an overlay system. P2 dataflows mix together network packet processing elements for tasks like queueing, (de)muxing, and congestion control along with relational database operators like joins and aggregations; the unification of variable= s in the body of a rule is implemented in a dataflow by an equijoin. This is = a complex operation, which can be considered somewhat inefficient; moreover, the future work lists sharing as an area of future work, and therefore earlier comments on sharing workload are somewhat immaterial. Also, the performance characteristics represent fairly decent behavior, which seems t= o be in a sense unnecessary; the paper is almost trying to accomplish too muc= h in that it posits that the system will aid in design time while simultaneously maintaining decent performance. While this is true, the proofs provided to precious little to back this claim up. MACEDON: Methodology for Automatically Creating, Evaluating, and Designing Overlay Networks Adolfo Rodriguez, Charles Killian, Sooraj Bhat, Dejan Kostic, Amin Vahdat MACEDON, written before the P2 paper, performs a similar role in that i= t abstracts the work of designing overlay networks into that of specifying their runtime and other performance characteristics. Rather than generating query plans, it generates C++ code which can be compiled to run as per any other program. The benefits here are obvious, allowing greater programmers input in that the code can be modified afterwards. This might imply that th= e system is unnecessary, or might provide a human readable version of the specified system. The language itself describes a finite state machine, wit= h drawbacks such as high complexity to cope with system events, via API calls= , making the learning curve somewhat less steep; however, this is generally used in the generated code. The language that a programmer would use to create these API calls resembles a C or Java type language much more than DataLog does, while maintaining its nature as a descriptive language. It is therefore more mature as a language, which does not necessarily speak to th= e performance of the system but does speak to its utility as a rapid prototyping tool. Its performance is clearly not going to suffer as compared to standard programming techniques -- so much of the actual performance gains are implemented in an automated fashion by the compiler and optimizer that another step hardly seems likely to hurt. Moreover, the P2 paper doesn't seem to present an improvement over this system, as the performance is better, and the ease of use is greater. While concepts such as code reuse and query sharing exist, they are not yet implemented in either system, and thus somewhat secondary. ------=_Part_6079_29173591.1145337479690 Content-Type: text/html; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Andrew Cunningham
arc39

    Implementing Declaritive Overlays
    Boon Thau Loo, Tyson Condie, Joseph M. Hellerstein, Petr= os Maniatis, Timothy Roscoe, Ion Stoica
    
    P2 is a new technology designed to streamline and quicken the design of peer to peer, distributed systems. A side benefit is that as the code is structurally designed with no syntactic noise from procedural language constructs, code is very easily shared, reused, and repurposed. The authors use three components, relational tables to represent overlay state, high level declaritive language to specify the overlay's logical properties and behavior, and graphs of the dataflow elements to represent runtime information processing. They use structured relational tables because they are a natural representation as neighbor tables are already quite common, tables are easily represented in declarative language, and it provides a consistently-named view of all the local tables and messages at different nodes. It is claimed that OverLog, the language presented, is not designed as a Domain-Specific language for overlay specification but instead an adaption of a powerful query language to a distributed context of data and messages. However, those are nearly synonymous, in that once one reaches a distributed context, it is a quite short hop to an overlay system.
    P2 dataflows mix together network packet processing elements for tasks like queueing, (de)muxing, and congestion control along with relational database operators like joins and aggregations; the unification of variables in the body of a rule is implemented in a dataflow by an equijoin. This is a complex operation, which can be considered somewhat inefficient; moreover, the future work lists sharing as an area of future work, and therefore earlier comments on sharing workload are somewhat immaterial. Also, the performance characteristics represent fairly decent behavior, which seems to be in a sense unnecessary; the paper is almost trying to accomplish too much in that it posits that the system will aid in design time while simultaneously maintaining decent performance. While this is true, the proofs provided to precious little to back this claim up.
    
    MACEDON: Methodology for Automatically Creating, Evaluat= ing, and Designing Overlay Networks
    Adolfo Rodriguez, Charles Killian, Sooraj Bhat, Dejan Ko= stic, Amin Vahdat
    
    MACEDON, written before the P2 paper, performs a similar role in that it abstracts the work of designing overlay networks into that of specifying their runtime and other performance characteristics. Rather than generating query plans, it generates C++ code which can be compiled to run as per any other program. The benefits here are obvious, allowing greater programmers input in that the code can be modified afterwards. This might imply that the system is unnecessary, or might provide a human readable version of the specified system. The language itself describes a finite state machine, with drawbacks such as high complexity to cope with system events, via API calls, making the learning curve somewhat less steep; however, this is generally used in the generated code. The language that a programmer would use to create these API calls resembles a C or Java type language much more than DataLog does, while maintaining its nature as a descriptive language. It is therefore more mature as a language, which does not necessarily speak to the performance of the system but does speak to its utility as a rapid prototyping tool.
    Its performance is clearly not going to suffer as compared to standard programming techniques -- so much of the actual performance gains are implemented in an automated fashion by the compiler and optimizer that another step hardly seems likely to hurt. Moreover, the P2 paper doesn't seem to present an improvement over this system, as the performance is better, and the ease of use is greater. While concepts such as code reuse and query sharing exist, they are not yet implemented in either system, and thus somewhat secondary. ------=_Part_6079_29173591.1145337479690-- From sh366@cornell.edu Tue Apr 18 02:58:15 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.25) with ESMTP id k3I6wE217202 for ; Tue, 18 Apr 2006 02:58:14 -0400 (EDT) Received: from orpheus3.dataserver.cornell.edu (orpheus3.dataserver.cornell.edu [128.253.161.167]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k3I6wDiP020486 for ; Tue, 18 Apr 2006 02:58:13 -0400 (EDT) Message-ID: <1047235984.1145343491824.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Tue, 18 Apr 2006 02:58:12 -0400 (EDT) From: Huang Shiang-Jia To: egs+summary@cs.cornell.edu Subject: PAPER 22 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: uPortal WEB email client 3.0 To ease the development and deployment of a diverse set of overlay systems, some research works have recently focused on the services that abstractly express the behaviors and provide sharable/reusable codes of overlay networks. Performance is an issue in such works. * P2 uses OverLog, a logic language, to specify overlays declaratively. They model an overlay as a distributed data structure represented by a set of relations. Two relations, tables and streams, are employed. * By its dataflow engine, P2 executes fundamental functionalities of an overlay system, given logic descriptions issued by applications. Multiple overlay specifications can be compiled into a single dataflow in its dataflow framework. * In this paper, several research directions are also listed, including the breadth of codes, transport protocols, on-line distributed debugging and security. * Macedon specifies an overlay network in terms of event-driven finite state machines. Each node maintains a local 'state'. 'Events' such as message reception or node failures move a node from one state to another. 'Transitions' indicate the actions to take in response to events. * From the specification above, Macedon generates API-consistent codes for a variety of infrastructures leveraging shared libraries. In this way, it enables protocols layering from one overlay to another. From niranjan.sivakumar@gmail.com Tue Apr 18 07:29:56 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.7 required=5.0 tests=AWL,BAYES_00,HTML_00_10, HTML_MESSAGE autolearn=no version=3.1.0 X-Spam-Level: Received: from penguin.cs.cornell.edu (penguin.cs.cornell.edu [128.84.96.11]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.25) with ESMTP id k3IBTu217292 for ; Tue, 18 Apr 2006 07:29:56 -0400 (EDT) Received: from xproxy.gmail.com ([66.249.82.206]) by penguin.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 18 Apr 2006 07:29:07 -0400 Received: by xproxy.gmail.com with SMTP id s19so492004wxc for ; Tue, 18 Apr 2006 04:29:07 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type; b=Q/Yi4IUVVYK6Cl2zgSnk6S+uxkt1gEXnHTe+skX+oexoLN2m6ioaA1xOJORhLDl+RLDeLQFRQdYaxbWHbvlUePG6RhLDTw7mw+1fsE8NXJ3vT//x0e22kOirpvxhSDcUUwRK1jX4ciDFXwNczcVJsa2qYQsad3orOe9xTQT/Bf4= Received: by 10.70.124.7 with SMTP id w7mr4523998wxc; Mon, 17 Apr 2006 20:48:44 -0700 (PDT) Received: by 10.70.125.19 with HTTP; Mon, 17 Apr 2006 20:48:44 -0700 (PDT) Message-ID: Date: Mon, 17 Apr 2006 23:48:44 -0400 From: "Niranjan Sivakumar" To: egs+summary@cs.cornell.edu Subject: PAPER 22 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_Part_22554_7826521.1145332124795" X-OriginalArrivalTime: 18 Apr 2006 11:29:07.0842 (UTC) FILETIME=[4E587E20:01C662DB] ------=_Part_22554_7826521.1145332124795 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Niranjan Sivakumar Implementing Declarative Overlays Macedon: Methodology for Automatically Creating, Evaluating, and Designing Overlay Networks P2 is a system that is designed to simplify the process of writing overlay networks using a logic language and dataflow framework. Coding for P2 is done with Overlog, a Prolog-like language that is suited for specifying and implementing rules associated with overlay network behavior. Two examples of real world overlay networks, Narada and Chord, are illustrated using the P2 framework. Both systems were shown to be written using significantly less code than a direct implementation, or in some cases, even other declarative overlay systems. There a number of similarities between the P2 approach and the evolution of database systems and querying languages. Analysis of performance is provided, and shown to be "acceptible", but it i= s clearly stated that performance is not one of the goals of P2 at this stage. It is also noted that although Overlog facilitates writing overlay rules, it has many drawbacks as a language, particularly when compared to popular, familiar, object oriented languages. MACEDON is an earlier, but in many ways similar system, to P2. MACEDON als= o seeks to provide a framework to reduce the amount of code that must be written to create an overlay network. MACEDON is shown to be particularly geared to distributed hash tables and certain kinds of high-level multicast networks. MACEDON models overlay networks based on a finite state machine. A implementation of Overcast is used throughout the paper to describe a variety of MACEDON's features, but the evaluation compares a number of different systems that were implemented with MACEDON, including NICE, Chord= , and Pastry. MACEDON's programming syntax appears to be similar to that of languages like C++ and Java. As with P2, the focus of evaluation appears t= o be the number of lines of code required to implement a given overlay, with less of a focus on actual performance. Many of the notable drawbacks of P2 and Overlog are recognized in the paper itself. It is difficult to evaluate the ongoing work on P2, such as making the language more readable, from the information provided in the paper. However, given their reasons for using a Prolog-style language, and comparisons made between Datalog and SQL in the paper, it seems unlikely that Overlog will be changed in a drastic way. MACEDON appears to currentl= y be tailored around existing overlay models, and this may provide some problems when trying to implement something novel using MACEDON. One interesting point in the paper was that the authors noticed that there was an issue with their implementation of NICE, and stated a proposed solution that is said to be "straightforward" but did not implement it and attempt t= o get more accurate data. This seems to raise some questions about how "straightforward" or easy it is to make the change that was proposed. ------=_Part_22554_7826521.1145332124795 Content-Type: text/html; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Niranjan Sivakumar

Implementing Declarative Overlays
Macedon:&nbs= p; Methodology for Automatically Creating, Evaluating, and Designing Overla= y Networks

P2 is a system that is designed to simplify the process o= f writing overlay networks using a logic language and dataflow framework.&n= bsp; Coding for P2 is done with Overlog, a Prolog-like language that is sui= ted for specifying and implementing rules associated with overlay network b= ehavior.  Two examples of real world overlay networks, Narada and Chor= d, are illustrated using the P2 framework.  Both systems were shown to= be written using significantly less code than a direct implementation, or = in some cases, even other declarative overlay systems.  There a number= of similarities between the P2 approach and the evolution of database syst= ems and querying languages.  Analysis of performance is provided, and = shown to be "acceptible", but it is clearly stated that performan= ce is not one of the goals of P2 at this stage.  It is also noted that= although Overlog facilitates writing overlay rules, it has many drawbacks = as a language, particularly when compared to popular, familiar, object orie= nted languages.

MACEDON is an earlier, but in many ways similar system, to P2. = ; MACEDON also seeks to provide a framework to reduce the amount of code th= at must be written to create an overlay network.  MACEDON is shown to = be particularly geared to distributed hash tables and certain kinds of high= -level multicast networks.  MACEDON models overlay networks based on a= finite state machine.  A implementation of Overcast is used throughou= t the paper to describe a variety of MACEDON's features, but the evaluation= compares a number of different systems that were implemented with MACEDON,= including NICE, Chord, and Pastry.  MACEDON's programming syntax appe= ars to be similar to that of languages like C++ and Java.  As with P2,= the focus of evaluation appears to be the number of lines of code required= to implement a given overlay, with less of a focus on actual performance.

Many of the notable drawbacks of P2 and Overlog are recognized in t= he paper itself.  It is difficult to evaluate the ongoing work on P2, = such as making the language more readable, from the information provided in= the paper.  However, given their reasons for using a Prolog-style lan= guage, and comparisons made between Datalog and SQL in the paper, it seems = unlikely that Overlog will be changed in a drastic way.  MACEDON appea= rs to currently be tailored around existing overlay models, and this may pr= ovide some problems when trying to implement something novel using MACEDON.=   One interesting point in the paper was that the authors noticed that= there was an issue with their implementation of NICE, and stated a propose= d solution that is said to be "straightforward" but did not imple= ment it and attempt to get more accurate data.  This seems to raise so= me questions about how "straightforward" or easy it is to make th= e change that was proposed. =20
------=_Part_22554_7826521.1145332124795-- From tc99@cornell.edu Tue Apr 18 11:20:19 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.25) with ESMTP id k3IFKI212768 for ; Tue, 18 Apr 2006 11:20:18 -0400 (EDT) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k3IFKG0b026321 for ; Tue, 18 Apr 2006 11:20:17 -0400 (EDT) Received: from 128.84.153.96 by webmail.cornell.edu with HTTP; Tue, 18 Apr 2006 11:20:17 -0400 (EDT) Message-ID: <1151.128.84.153.96.1145373617.squirrel@webmail.cornell.edu> Date: Tue, 18 Apr 2006 11:20:17 -0400 (EDT) Subject: paper 22 From: "Theodore Ming Shiuan Chao" To: egs@cs.cornell.edu User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal The two papers discuss methods for abstracting the implementation of network overlays to simply implementing them and provide for a more structured method of testing and evaluating their performance. Macedon is a protocol-centric approach that abstracts each node into a finite state machine (FSM) and focuses on the events that cause transitions between states. Within Macedon itself, there is a multi-layered stack to allow systems to be built on others (for example, SplitStream is built on Scribe which is built on Pastry or alternative, a different DHT overlay such as Chord). P2 approaches things slightly differently. Instead of forcing the user to specify their own handling of events in code, P2 represents everything as a labeled relational tuple. The tuples are generated based on a series of rules, which are the various conditions on which a specified tuple will be generated. There are some primitive event types that P2 implements though, such as periodic generation of tuples and pings to measure latency. The general structure of an overlay can then be represented in surprisingly few rules (47 rules for Chord). The two approaches differ in the complexity of the code (both for the underlying backbone and the per-overlay code) and their perfomance goals. In Macedon, the user must write the majority of the message handling code and thus, the backbone of Macedon is relatively simple. In P2, the relational database abstraction simplifies the overlay code (or rules, as the case may be), but the underlying code of P2 is much longer and complicated than Macedon to support that abstraction. Similarly, pushing specific overlay descriptions to a higher level will have an impact on the performance. P2's performance goal is a "good enough" measure - or a performance that is not significantly worse than an optimized version. Macedon, on the other hand, can achieve better performance since the lower-level coding allows for more optimizations. From km266@cornell.edu Tue Apr 18 11:39:38 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-0.5 required=5.0 tests=AWL,BAYES_00, FORGED_OUTLOOK_TAGS,HTML_MESSAGE autolearn=no version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.25) with ESMTP id k3IFdc217711 for ; Tue, 18 Apr 2006 11:39:38 -0400 (EDT) Received: from KEVSTOY (cpe-69-207-37-246.twcny.res.rr.com [69.207.37.246]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k3IFdbLt011761 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for ; Tue, 18 Apr 2006 11:39:37 -0400 (EDT) Message-ID: <000601c662fe$50c08f90$f625cf45@KEVSTOY> Reply-To: "Kevin" From: "Kevin" To: Subject: PAPER 22 Date: Tue, 18 Apr 2006 11:39:43 -0400 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_0003_01C662DC.C937C3C0" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.2869 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2869 This is a multi-part message in MIME format. ------=_NextPart_000_0003_01C662DC.C937C3C0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Implementing Declarative Overlays introduces P2, a system that allows = the user to concisely specify an overlay network. A language, OverLog, = is introduced which uses rules and relations to construct an overlay. = This system allows tables (which they argue are necessary because many = current overlays use tables to store neighbor state and other such = information), streams, and uses a high level language to specify a = system. Overlog is a query language which the authors claim to derived = from Datalog, which in turn is derived from Prolog. The authors argue = that their system is a distributed version of previous systems. The = authors constantly claim that they wrote Chord in 47 lines of code. = While I have no doubt that they did, those 47 lines are, in my opinion, = confusing and intertwined. They depend on each other so much that = debugging in this language seems like a nightmarish task. Macedon uses finite state machines which compile down into a lower level = language (C/C++), allowing an advanced programmer access to any code = they felt they could not specify clearly enough at a high level. The = high level language they use is far less confusing than Overlog and = reminds me more of typical C-style languages. The language allows you = to specify finite state machines quickly and logically. The main = drawback to these two systems is the amount of pre-planning and thought = that goes into every line. While CHORD can be expressed in 47 lines or = several hundred lines, these lines each took significantly more time to = write than a single line in the Java implementation of Chord. If the = Java implementation is 10x as long as the Macedon implementation but it = took 10x less time to write each line, the gain is minimal. Worse yet, = the implementation Macedon gives is not even a full Chord = implementation. --Kevin ------=_NextPart_000_0003_01C662DC.C937C3C0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
Implementing Declarative Overlays = introduces=20 P2, a system that allows the user to concisely specify an overlay=20 network.  A language, OverLog, is introduced which uses rules and = relations=20 to construct an overlay.  This system allows tables (which = they argue=20 are necessary because many current overlays use tables to store neighbor = state=20 and other such information), streams, and uses a high level = language to=20 specify a system.  Overlog is a query language which the authors = claim to=20 derived from Datalog, which in turn is derived from Prolog.  The = authors=20 argue that their system is a distributed version of previous = systems.  The=20 authors constantly claim that they wrote Chord in 47 lines of = code.  While=20 I have no doubt that they did, those 47 lines are, in my opinion, = confusing and=20 intertwined.  They depend on each other so much that debugging in = this=20 language seems like a nightmarish task.
 
Macedon uses finite state machines = which compile=20 down into a lower level language (C/C++), allowing an advanced = programmer access=20 to any code they felt they could not specify clearly enough at a high=20 level.  The high level language they use is far less confusing than = Overlog=20 and reminds me more of typical C-style languages.  The language = allows you=20 to specify finite state machines quickly and logically.  The main = drawback=20 to these two systems is the amount of pre-planning and thought that goes = into=20 every line.  While CHORD can be expressed in 47 lines or several = hundred=20 lines, these lines each took significantly more time to write than a = single line=20 in the Java implementation of Chord.  If the Java implementation is = 10x as=20 long as the Macedon implementation but it took 10x less time to write = each line,=20 the gain is minimal.  Worse yet, the implementation Macedon gives = is not=20 even a full Chord implementation.
 
--Kevin
------=_NextPart_000_0003_01C662DC.C937C3C0-- From victoria@cs.hmc.edu Tue Apr 18 12:32:55 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from penguin.cs.cornell.edu (penguin.cs.cornell.edu [128.84.96.11]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.25) with ESMTP id k3IGWs202220 for ; Tue, 18 Apr 2006 12:32:54 -0400 (EDT) Received: from turing.cs.hmc.edu ([134.173.42.99]) by penguin.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Tue, 18 Apr 2006 12:31:52 -0400 Received: from knuth.cs.hmc.edu (knuth.cs.hmc.edu [134.173.42.100]) by turing.cs.hmc.edu (Postfix) with ESMTP id A4F5253201; Tue, 18 Apr 2006 09:08:33 -0700 (PDT) Received: by knuth.cs.hmc.edu (Postfix, from userid 34382) id 93A7DBF46; Tue, 18 Apr 2006 09:08:33 -0700 (PDT) Date: Tue, 18 Apr 2006 09:08:33 -0700 From: Victoria Krafft To: egs+summary@cs.cornell.edu Subject: PAPER 22 Message-ID: <20060418160833.GB7659@cs.hmc.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.9i X-OriginalArrivalTime: 18 Apr 2006 16:31:52.0592 (UTC) FILETIME=[99616100:01C66305] MACEDON and P2 are both systems which allow peer-to-peer networks to be quickly coded and tested; rather than writing thousands of lines of code, these systems allow overlay networks to be specified in a concise, domain-specific manner. MACEDON is designed to simplify the design, implementation, and evaluation of large-scale overlays. A researcher gives MACEDON a high-level specification in terms of a finite state machine, and MACEDON generates C++ code. The authors have re-written several well-known peer-to-peer applications in MACEDON, and their experiments show that MACEDON produces efficient code for those applications. In many ways, the MACEDON code reminds me of higher-level languages such as python and perl; it takes care of the gory details, so a researcher can focus on the algorithm. P2 uses a declarative logic language to specify the overlays, and a dataflow framework to maintain the overlays, rather than a finite state machine. To specify the overlay networks, they developed a language called OverLog, which is similar to ProLog and DataLog. In this language, the amount of code a researcher has to write drops further; for example, Chord can be specified with 47 logic rules, while MACEDON used 320 lines. However, I think that OverLog looks much more complicated than the specifications MACEDON requires, so this may not actually save the researcher any time. Both of these systems are designed to cut down on the amount of work a researcher needs to do. However, the number of lines of code does not necessarily reflect the amount of time the researcher has to spend to get the system working; tracking down bugs could easily take more time once another layer of abstraction is introduced. In addition, the researcher may want to modify code at a lower level than these systems allow for; modifications to wire protocols, or specific rules for choosing neighbors, are not allowed under these systems. With the increasing use of high-level languages such as Python, systems such as MACEDON and P2 may become less useful. -- Victoria Krafft From gp72@cornell.edu Sat May 13 19:16:05 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from exchfe1.cs.cornell.edu (exchfe1.cs.cornell.edu [128.84.97.27]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.25) with ESMTP id k4DNG4200824 for ; Sat, 13 May 2006 19:16:05 -0400 (EDT) Received: from iago.cs.cornell.edu ([128.84.96.10]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Sat, 13 May 2006 19:15:01 -0400 Received: from postoffice10.mail.cornell.edu ([132.236.56.14]) by iago.cs.cornell.edu with Microsoft SMTPSVC(6.0.3790.1830); Sat, 13 May 2006 19:14:57 -0400 Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k4DNEqat012158; Sat, 13 May 2006 19:14:53 -0400 (EDT) Received: from 128.84.98.245 by webmail.cornell.edu with HTTP; Sat, 13 May 2006 19:14:52 -0400 (EDT) Message-ID: <2001.128.84.98.245.1147562092.squirrel@webmail.cornell.edu> In-Reply-To: <1923.128.84.98.245.1147557414.squirrel@webmail.cornell.edu> References: <2537.128.84.98.245.1147406914.squirrel@webmail.cornell.edu> <3469.128.84.98.245.1147411785.squirrel@webmail.cornell.edu> <4952.128.84.98.245.1147484280.squirrel@webmail.cornell.edu> <1157.128.84.98.245.1147492519.squirrel@webmail.cornell.edu> <1255.128.84.98.245.1147497043.squirrel@webmail.cornell.edu> <1923.128.84.98.245.1147557414.squirrel@webmail.cornell.edu> Date: Sat, 13 May 2006 19:14:52 -0400 (EDT) Subject: PAPER 22 From: "Gopal Parameswaran" To: egs+summary@cs.cornell.edu Cc: gp72@cornell.edu User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal X-OriginalArrivalTime: 13 May 2006 23:14:58.0069 (UTC) FILETIME=[0D600C50:01C676E3] Implementing Declarative Overlays In this paper the authors presents a declarative logical language P2 that can be used to express the overlay networks and can be used to implement them. Applications would submit to P2 a logical description of an overlay network and P2 would generate the code needed to maintain all the data structures associated with the network including routing tables and perform resource discovery and forwarding features to the overall. The authors claim that since the system is based on logical units it can be broken down into smaller units and can be reused for coding in the future. The advantage of this system it is felt would only be in the ease of writing a simple system and its contribution to an actual futuristic peer-to-peer system would be minimal in terms of performance. This system like Macedon discussed below are good for prototyping simple systems. Also it seems rather naïve to implement the system as a platform instead of it as a library that would have helped in integrating it with other systems and would have also helped others in developing extensions to the system. This system models a lot on database query languages and though it is a promising area the amount of support work done for the P2 system only involves the implementation of Chord and it is assumed that other systems can be similarly developed. The comparison chart with Chord also happens to be for only 400 nodes and that is too minimal a node population to provide for any significant results. Macedon Macedon provides a domain specific language for abstracting the high level behavior of overlays and DHT’s for peer to peer systems and is implemented on a wider range of systems and provides also a C++ language generated code and though the code generated would be harder to walk through make changes and would involve a substantial learning curve, it could be used to generate the basic peer to peer functionalities and then the generated code could be modified to tune the code for specific needs. This system serves as an API over the network substrate and could be modified to provide a library of API. However any specific changes to the network protocols would involve as said earlier a substantial effort though it could be added on as extensions to the existing code and would be great for running simulations. Developing languages for peer-to-peer system development is a great idea though the focus should be more on development of libraries rather than languages. The Macedon API can be made on to run on existing overlays and can be used for enhancements as shown in the Macedon protocol stack and this serves a major development for peer-to-peer application development. Another feature of Macedon is the inclusion of locking mechanisms that could be used to provide a higher level of multithreading use and it could be extended to provide for callback functions that could allow for more specific implementation of locking mechanisms if required by certain application developers. However both these systems though being a major step in the development of Peer-to-Peer system languages it still represents a process in its infancy.