Systematic Verification of Safety Properties of Arbitrary Network Protocol Compositions Using CHAIN

Formal correctness of complex multi-party network protocols can be difficult to verify. While models of specific fixed compositions of agents can be checked against design constraints, protocols which lend themselves to arbitrarily many compositions of agents-such as the chaining of proxies or the peering of routers-are more difficult to verify because they represent potentially infinite state spaces and may exhibit emergent behaviors which may not materialize under particular fixed compositions. We address this challenge by developing an algebraic approach that enables us to reduce arbitrary compositions of network agents into a behaviorally-equivalent (with respect to some correctness property) compact, canonical representation, which is amenable to mechanical verification. Our approach consists of an algebra and a set of property-preserving rewrite rules for the Canonical Homomorphic Abstraction of Infinite Network protocol compositions (CHAIN). Using CHAIN, an expression over our algebra (i.e., a set of configurations of network protocol agents) can be reduced to another behaviorally-equivalent expression (i.e., a smaller set of configurations). Repeated applications of such rewrite rules produces a canonical expression which can be checked mechanically. We demonstrate our approach by characterizing deadlock-prone configurations of HTTP agents, as well as establishing useful properties of an overlay protocol for scheduling MPEG frames, and of a protocol for Web intra-cache consistency.

Validating Arbitrarily Large Network Protocol Compositions with Finite Computation

Formal tools like finite-state model checkers have proven useful in verifying the correctness of systems of bounded size and for hardening single system components against arbitrary inputs. However, conventional applications of these techniques are not well suited to characterizing emergent behaviors of large compositions of processes. In this paper, we present a methodology by which arbitrarily large compositions of components can, if sufficient conditions are proven concerning properties of small compositions, be modeled and completely verified by performing formal verifications upon only a finite set of compositions. The sufficient conditions take the form of reductions, which are claims that particular sequences of components will be causally indistinguishable from other shorter sequences of components. We show how this methodology can be applied to a variety of network protocol applications, including two features of the HTTP protocol, a simple active networking applet, and a proposed web cache consistency algorithm. We also doing discuss its applicability to framing protocol design goals and to representing systems which employ non-model-checking verification methodologies. Finally, we briefly discuss how we hope to broaden this methodology to more general topological compositions of network applications.

Typed Abstraction of Complex Network Compositions

The heterogeneity and open nature of network systems make analysis of compositions of components quite challenging, making the design and implementation of robust network services largely inaccessible to the average programmer. We propose the development of a novel type system and practical type spaces which reflect simplified representations of the results and conclusions which can be derived from complex compositional theories in more accessible ways, essentially allowing the system architect or programmer to be exposed only to the inputs and output of compositional analysis without having to be familiar with the ins and outs of its internals. Toward this end we present the TRAFFIC (Typed Representation and Analysis of Flows For Interoperability Checks) framework, a simple flow-composition and typing language with corresponding type system. We then discuss and demonstrate the expressive power of a type space for TRAFFIC derived from the network calculus, allowing us to reason about and infer such properties as data arrival, transit, and loss rates in large composite network applications.

TRADITION AND INNOVATION: ANALYSIS AND PERFORMANCE OF SELECTED COMPOSITIONS FOR VIOLONCELLO BY HEITOR VILLA-LOBOS

Brazilian composer Heitor Villa-Lobos (1887-1959) began his musical career as a cellist. When he was only twelve years old, it became imperativeupon the sudden and untimely death of his fatherthat the young Villa-Lobos earn money as a cellist to provide financial support for his mother and sisters. Villa-Lobos's intimate relationship with the cello eventually inspired him to compose great music for this instrument. This dissertation explores both the diversity of compositional technique and the evolution of style found in the music for cello written by Villa-Lobos. The project consists of two recorded recital performances and a written document exploring and analyzing those pieces. In the study of the music of Villa-Lobos, it is of great interest to consider the music's traditional European elements in combination (or even juxtaposition) with its imaginative and sometimes wildly innovative Brazilian character. His early works were greatly influenced by European Romantic composers such as Robert Schumann, Frédéric Chopin, and the virtuoso cellist/composer David Popper (whom Villa-Lobos idolized). Later, Villa-Lobos flourished in a newfound compositional independence and moved away from Euro-romanticism and toward the folk music of his Brazilian homeland. It is intriguing to experience this transition through an exploration of his cello compositions. The works examined and performed in this dissertation project are chosen from among the extensive number of Villa-Lobos's cello compositions and are his most important works for cello with piano, cello with another instrument, and cello with orchestra. The chosen works demonstrate the evolving range and combination of characteristic elements found in Villa-Lobos's compositional repertoire.

COMPOSITIONS FEATURING THE PIANO IN FANTASY FORM: 1820-1920

The Fantasy form offered a composer the freedom to create a work without concerns for fitting into the current stylistic and traditional structures. The flowering of the form seems to be concentrated from 1820-1920 since the composer started to use it as a way to convey a personal idea or to portray a special spirit. This dissertation is comprised of three recitals with fantasies in different genres and styles. Through performing these diverse fantasies, I have been inspired to connect with the imagery and spirit of the compositions in order to capture the unique sentiments of each piece. Also, in order to keep the audience absorbed in the music that is without structure, I have focused on expanding my technical abilities to vary color, sonority, and phrasing. Program one (April 26,2004) includes Fantasie, Op. 17 and Piano Concerto, Op. 54 (assisted by Ya-Hsin Wu) by R. Schumann. Program two (December 10, 2004) includes Three Fantastic Dances, Op. 5 by D. Shostakovitch, Fantasy "Sonataecossaise ", Op. 28 by F. Mendelssohn, Sonata No.2 "Sonata-Fantasy", Op. 19 by A. Scriabin and Fantasie for Piano and Violin, D 934 by F. Schubert with violinist, TaoChang Yu. The last program (November 1, 2005) includes Fantasia baetica by E. de Falla, Morceaux de Fantaisie, Op. 3 by S. Rachrnaninoff, Fantaisie, Op. 49, Impromptu No. 4 '%h.ntasy-hpromptu", Op. 66 and Polonaise-Fantaisie, Op. 61 by F. Chopin.

THE PERFORMER’S INFLUENCE ON FRANCO-BELGIAN COMPOSITIONS FROM 1870 TO 1930

The turn of the 20th century marked an ascendancy of the Franco-Belgian school of composers. French composers were inspired by the great German composers of the Romantic era, and they created their own defined national style that emerged toward the end of the 19th century. The Franco-Belgian composers’ special emphasis on tone, timbre and color encouraged a more individual, personally interpretative approach. These devices underscore the importance and influence a performer can have on the outcome of a piece. I researched the relationship between composers and violinists at a time when the Franco-Belgian style developed and flourished. The Franco-Belgian school of violin playing emerged from the Paris and Brussels conservatories as well as the symbiotic relationship between the performers and composers. Three recitals in collaboration with pianist David Ballena, which comprise this dissertation project, were performed at the University of Maryland. Each recital featured music for violin and piano from 1870 through 1930. The repertoire was chosen to reflect a performer’s influence on a composer. I examined specific composer/performer relationships that helped shape the birth of a newly defined “French” style of playing. My research focused on the stylistic interactions composers, such as César Franck, his disciple Guillaume Lekeu had with the leading prominent Belgian violinist Eugène Ysaye and between Maurice Ravel and the Hungarian violinist Jelly d’Aranyi. I also looked into the personal relationship between friends who inspired each other: Gabriel Fauré and Paul Viardot, Edouard Lalo and Pablo de Sarasate, Claude Debussy and Arthur Hartmann, and the young Lili Boulanger and Yvonne Astruc. Furthermore, I looked into the unfulfilled love between Maurice Ravel and Hélène Jourdan-Morhange, as well as the marriage of Olivier Messiaen with Claire Delbos, both relationships resulting in masterpieces for violin that have remained a part of the standard violin repertoire. My research led me to understand what type of violin playing each composer had in mind while composing, all of which led me to understand the importance a performer has in preserving national styles. The recitals were recorded on compact discs and archived within the Digital Repository at the University of Maryland (DRUM).