- talks - lists.cs.princeton.edu

M Meola general exam
by Melissa Lawson 07 May '09

07 May '09

Matt Meola will present his research seminar/general exam on Wednesday May 13 at 2PM in Room 402. The members of his committee are: David Walker, advisor, Andrew Appel, and Ed Felten. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------------------------------------- Abstract -------- As semiconductor manufacturing technologies improve, feature sizes get smaller, and transistors more densely packed, computer users face an ever-increasing chance that cosmic rays and other sources of high energy particles will disrupt the workings of their processors. When implementing cryptographic algorithms, security protocols, long-running simulations, and safety-critical systems, software developers must consider the possibility that such intermittent hardware faults will cause irreparable harm to their applications. Boneh, DeMillo, and Lipton were the first to show that a single fault could be exploited to break common implementations of RSA. Others followed, demonstrating exploits of cryptosystems and runtime systems achieved by inducing transient faults. To support the higher degrees of confidence required in these critical applications, we have developed a new logic for reasoning about faulty programs. Our logic allows the verification of programs even in the presence of transient faults. It operates over a standard language of imperative while programs augmented with a single new instruction to indicate the possibility of faults at particular program points. The logic itself is a relative of Separation Logic in which the separating conjunction is used to reason about the limits to which faults may affect different parts of program state. As much as is practical, the logic is intended to be agnostic of the particular model used to decide when faults may occur. In particular, our current work deals with standard fault models that allow a certain maximum number of faults to occur in program variables in a single run of the program and limits faults according to how they affect data (typically either allowing only a single bit flip or allowing arbitrary changes in value). Faults in control-flow and many control logic faults (such as misinterpretation of opcodes) are ignored, except where they can be simulated by data faults. We prove the logic is sound and illustrate how to use it on several simple examples, including a simplified, idealized version of the RSA message signing algorithm. We show how the introduction of a modal connective helps to simplify program assertions and facilitate the reasoning process. Books ----- Pierce, B.C. Types and Programming Languages. MIT Press, 2002. Ch 1, 2, 4, 5 of Huth, M.R.A. and Ryan, M.D. Logic in Computer Science: Modelling and Reasoning about Systems. Cambridge University Press, 2000. Papers ------ [1] Bar-El, H., Choukri, H., Naccache, D., Tunstall, M., and Whelan, C. The Sorcerers Apprentice Guide to Fault Attacks. Proc. IEEE, Vol. 94. 370-382, Feb. 2006. [2] Barthe, G., Grégoire, B., and Zanella Béguelin, S. 2009. Formal certification of code-based cryptographic proofs. In Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Savannah, GA, USA, January 21 - 23, 2009). POPL '09. ACM, New York, NY, 90-101. [3] Boneh, D., DeMillo, R., and Lipton, R., On the importance of checking cryptographic protocols for faults, Journal of Cryptology 14 (2001). 101-119. [4] Chang, J., G. A. Reis and D. I. August. Non-Uniform Fault Tolerance. In Proceedings of the 2nd Workshop on Architectural Reliability (WAR), December 2006. [5] Ishtiaq, S. and O'Hearn, P. Bi as an assertion language for mutable data structures. In Proceedings of the 28th ACM Symposium on Principles of Programming Languages, London, United Kingdom, 2001, 14-26. [6] Perry, F., Mackey, L., Reis, G. A., Ligatti, J., August, D. I., and Walker, D. 2007. Fault-tolerant typed assembly language. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (San Diego, California, USA, June 10 - 13, 2007). PLDI '07. ACM, New York, NY, 42-53. [7] Rebaudengo, M., Sonza Reorda, M., Torchiano, M., and Violante, M., Soft-error Detection through Software Fault-Tolerance techniques, in: IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, 1999, 210-218. [8] Reis, G. A., Chang, J., and August, D. I. 2007. Automatic Instruction-Level Software-Only Recovery. IEEE Micro 27, 1 (Jan. 2007), 36-47. [9] Shirvani, P. P., Saxena, N., and McCluskey, E. J. 2000. Software-implemented EDAC protection against SEUs. In IEEE Transactions on Reliability. Vol. 49. 273284. [10] Walker, D., Mackey, L., Ligatti, J., Reis, G. A., and August, D. I. 2006. Static typing for a faulty lambda calculus. In Proceedings of the Eleventh ACM SIGPLAN international Conference on Functional Programming (Portland, Oregon, USA, September 16 - 21, 2006). ICFP '06. ACM, New York, NY, 38-49.

1 0

J Huang general exam
by Melissa Lawson 05 May '09

05 May '09

Jialu Huang will present her research seminar/general exam on Tuesday May 12 at 2PM in room 402. The members of her committee are: David August, advisor, Brian Kernighan, and Andrew Appel. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ============================================ General abstract: While multi-core systems have become prevalent, using them efficiently remains an unsolved problem. DOALL is a highly efficient parallelization technique, however, cross-iteration dependences limit DOALL's applicability. Decoupled software pipelining (DSWP) partitions the code into stages with dependences flowing unidirectionally from earlier stages to later stages. DSWP is more generally applicable than DOALL, but its scalability is limited by the number of stages and by the workload in each stage. Parallel stage decoupled software pipelining (PS-DSWP) addresses this problem by enabling DOALL parallelization to some stages of a DSWP pipeline in loops where DOALL wasn't originally applicable. Inspired by the idea that DSWP can make DOALL more applicable, this work proposes other parallelization techniques can become more broadly applicable through the use of DSWP. LOCALWRITE, which requires each thread to only update the data belonging only to itself, if applied alone, suffers from redundant computations. Introducing LOCALWRITE into a DSWP framework, removes this limitation, by having a separate DOALL stage produce the iteration state to the LOCALWRITE stages. Experiments show combining all three parallelizations (DOALL, LOCALWRITE, DSWP) yields performance superior to applying any of these techniques alone. Reading List: Books: [1] Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998. Chapter 1~13, 17~21. [2] Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2001. Chapter 9, 10. Papers: [1] Raman, E., Ottoni, G., Raman, A., Bridges, M. J., and August, D. I. 2008. Parallel-stage decoupled software pipelining. In Proceedings of the Sixth Annual IEEE/ACM international Symposium on Code Generation and Optimization (Boston, MA, USA, April 05 - 09, 2008). CGO '08. ACM, New York, NY, 114-123. DOI= http://doi.acm.org/10.1145/1356058.1356074 [2] Guilherme Ottoni, Ram Rangan, Adam Stoler, and David I. August. Automatic Thread Extraction with Decoupled Software Pipelining. In Proceedings of the 38th IEEE/ACM International Symposium on Microarchitecture (MICRO), November 2005. [3] Matthew J. Bridges, Neil Vachharajani, Yun Zhang, Thomas Jablin, David I. August, "Revisiting the Sequential Programming Model for the Multicore Era," IEEE Micro, vol. 28, no. 1, pp. 12-20, Jan./Feb. 2008, doi:10.1109/MM.2008.13. [4] Vachharajani, N., Rangan, R., Raman, E., Bridges, M. J., Ottoni, G., and August, D. I. 2007. Speculative Decoupled Software Pipelining. In Proceedings of the 16th international Conference on Parallel Architecture and Compilation Techniques (September 15 - 19, 2007). PACT. IEEE Computer Society, Washington, DC, 49-59. DOI= http://dx.doi.org/10.1109/PACT.2007.66. [5] Singh, D. E., Martin, M. J., and Rivera, F. F. 2005. Runtime characterisation of irregular accesses applied to parallelisation of irregular reductions. Int. J. Comput. Sci. Eng. 1, 1 (Feb. 2005), 1-14. DOI= http://dx.doi.org/10.1504/IJCSE.2005.008906. [6] Gutiérrez, E., Plata, O. G., and Zapata, E. L. 1999. On Automatic Parallelization of Irregular Reductions on Scalable Shared Memory Systems. In Proceedings of the 5th international Euro-Par Conference on Parallel Processing (August 31 - September 03, 1999). P. Amestoy, P. Berger, M. J. Daydé, I. S. Duff, V. Frayssé, L. Giraud, and D. Ruiz, Eds. Lecture Notes In Computer Science, vol. 1685. Springer-Verlag, London, 422-429. [7] Eladio Gutiérrez, Oscar Plata, Emilio L. Zapata, "Improving Parallel Irregular Reductions Using Partial Array Expansion," sc,pp.56, ACM/IEEE SC 2001 Conference (SC 2001), 2001. [8] Saltz, J. H., Mirchandaney, R., and Crowley, K. 1989. The doconsider loop. In Proceedings of the 3rd international Conference on Supercomputing (Crete, Greece, June 05 - 09, 1989). ICS '89. ACM, New York, NY, 29-40. DOI= http://doi.acm.org/10.1145/318789.318794. [9] Y. Lin and D. Padua. On the Automatic Parallelization of Sparse and Irregular Fortran Programs. Scientific Programming, 7(1999), pp. 231-246. ISSN 1058-9244, IOS Press. [10] Y. Lin and D. Padua. Analysis of Irregular Single-indexed Arrays and Its Applications in Compiler Optimizations. In Proceedings of the 9th International Conference on Compiler Construction. Berlin, Germany, March 2000.

1 0

J Hung general exam
by Melissa Lawson 05 May '09

05 May '09

Jack Tzu-Han Hung will present his research seminar/general exam on Tuesday May 12 at 10AM in Room 402. the members of his committee are: David August, advisor, Margaret Martonosi, and Doug Clark. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----------------------------- Abstract: Recently, the multicore systems have emerged as the dominate and promising architecture in the computing area. Unfortunately, a parallelizing compiler is essential to extract the potential parallelism from the existing sequential programs and utilize the power of multicore systems. Independent multi-threading (e.g., DOALL) and pipelined multi-threading (e.g., decouple software pipelining, DSWP) parallelization techniques have been researched extensively. However, each has its own advantages and limitations. On one hand, DOALL exploits data parallelism and scales well to the number of cores; however, it requires the lack of loop-carried dependencies and thus suffers from its applicability. On the other hand, DSWP handles the program dependencies via the use of communication queue and makes it applicable to more programs; however, the scalability of this approach is limited by the number of stages in the pipeline, which is usually far less than the number of cores. In this work, we propose two techniques to enhance the scalability of DSWP. First, instead of being inner-loop-blind, as DSWP does, we examine the structure of inner loops in the pipeline and exploit the DOALL opportunities if applicable. This improves the scalability of DSWP since the additional cores could be used for executing DOALL inner loops. Second, we optimize the communication for loop live-in and live-out variables by performing pre- and post-partitioning analyses. The post-partitioning analysis leverages the existing liveness analysis and is applied for each partition, instead of the entire loop. The pre-partitioning analysis takes the communication cost into consideration and could achieve better partitioning. Our initial results show a speedup up to 5.4x for 052.alvinn and ECLAT. Reading List: [Text Books] * Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998. * Compilers: Principles, Techniques, and Tools (2nd Edition) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2006. [Papers] * Thies, W., Chandrasekhar, V., and Amarasinghe, S. 2007. A Practical Approach to Exploiting Coarse-Grained Pipeline Parallelism in C Programs. In Proceedings of the 40th Annual IEEE/ACM international Symposium on Microarchitecture (December 01 - 05, 2007). * Gordon, M. I., Thies, W., and Amarasinghe, S. 2006. Exploiting coarse-grained task, data, and pipeline parallelism in stream programs. In Proceedings of the 12th international Conference on Architectural Support For Programming Languages and Operating Systems (San Jose, California, USA, October 21 - 25, 2006). * Hongtao Zhong, Mojtaba Mehrara, Steve Lieberman, Scott Mahlke. " Uncovering Hidden Loop Level Parallelism in Sequential Applications". The 14th International Symposium on High-Performance Computer Architecture (HPCA), February, 2008. * Guilherme Ottoni, Ram Rangan, Adam Stoler, and David I. August. Automatic Thread Extraction with Decoupled Software Pipelining. In Proceedings of the 38th IEEE/ACM International Symposium on Microarchitecture (MICRO), November 2005. * EaswaranRaman, Guilherme Ottoni, Arun Raman, Matthew Bridges, and David I. August. Parallel-Stage Decoupled Software Pipelining. In Proceedings of the 2008 International Symposium on Code Generation and Optimization (CGO), April 2008. * Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme Ottoni and David I. August. Speculative Decoupled Software Pipelining. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques (PACT), September 2007. * Guilherme Ottoni and David I. August. Global Multi-Threaded Instruction Scheduling: Technique and Initial Results. In Proceedings of the Sixth Workshop on Explicitly Parallel Instruction Computer Architectures and Compiler Technology (EPIC), March 2007. * J. R. B. Davies. Parallel loop constructs for multiprocessors. Master's thesis, Department of Computer Science, University of Illinois, Urbana, IL, May 1981. * J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9:319-349, July 1987.

1 0

M Hardt general exam
by Melissa Lawson 05 May '09

05 May '09

Moritz Hardt will present his research seminar/general exam on Monday May 11 at 2PM in Room 302 (note room). The members of his committee are: Boaz Barak, advisor, Sanjeev Arora, and Bernard Chazelle. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. -------------------------------------------------- I. Title + abstract What are plausible hard instances for Unique Games? Unique Games are a family of constraint satisfaction problems conjectured to be NP-hard. This conjecture due to Khot implies that simple semidefinite programs (SDP) achieve optimal approximation ratios for several important problems including Max-Cut and Vertex Cover. Unfortunately, little evidence in support of the conjecture exists. Indeed, random instances of Unique Games are known to be easy. In this work we thus address the question: What are plausible hard instances for Unique Games? Our approach is to consider the refutation problem induced by subsampling a given SDP gap instance to constant degree. While subsampling preserves global parameters such as the integrality gap, the lack of local structure may lead to computational hardness. In support of our methodology, we observe that a constant degree subsample of essentially any unsatisfiable k-CSP instance gives rise to strong lower bounds in the Lasserre SDP hierarchy so long as k is greater than 3. Based on the work of Charikar, Makarychev and Makarychev, we also show that for 2-CSPs and Unique Games a constant degree subsample of any unsatisfiable instance gives strong lower bounds in the Sherali-Adams linear programming hierarchy. Unfortunately, our approach can only go so far. Appealing to Grothendieck's inequality, we show that for any 2-CSP the induced refutation problem is solvable in polynomial time. We then consider the question whether known SDP gaps withstand additional constraints when subsampled to constant degree. Somewhat surprisingly, we can show that already the triangle inequalities annihilate the integrality gap of the well known Feige-Schechtman gap instance for Max-Cut. This remains true even in a constant degree subsample. As for a future research direction, similar ideas could apply to all known Unique Games gap instances. My talk is based on ongoing research with Boaz Barak, Thomas Holenstein and David Steurer. II. Reading list Books: * Arora, Barak. Computational Complexity. Chapters 11,13,14,18--23 Papers: [Ale03] Alekhnovich. More on average case vs approximation complexity [ABW09] Applebaum, Barak, Wigderson. Public Key Cryptography from Different Assumptions [AKK+08] Arora, Khot, Kolla, Steurer, Tulsiani and Vishnoi. Unique Games on Expanding Constraint Graphs are Easy [CMM09] Charikar, Makarychev, Makarychev. Integrality Gaps for Sherali- Adams Relaxations [Fei02] Feige. Relations between Average Case Complexity and Approximation Complexity [FS02] Feige and Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT [Hol07] Holenstein. Parallel Repetition: Simplifications and the no-signaling case [KKMO04] Khot, Kindler, Mossel, O'Donnell. Optimal inapproximability results for max-cut and other 2-variable CSPs? [KV05] Khot, Vishnoi. The unique games conjecture, integrality gap for cut problems, and embeddability of negative type metrics into l1. [Rag08] Raghavendra. Optimal Algorithms and Inapproximability Results for Every CSP? [Sch08] Schoenebeck. Linear Level Lasserre Lower Bounds for Certain k-CSPs [TTV09] Trevisan, Tulsiani, Vadhan. Regularity, Boosting, and Efficiently

1 0

T Yue general exam
by Melissa Lawson 05 May '09

05 May '09

Tao Yue will present his research seminar/general exam on Monday May 11 at 10AM in room 402. The members of his committee are: Mona Singh, advisor, Olga Troyanskaya, and Tom Funkhouser. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------------------------------------- ABSTRACT --------- Sequence similarity has long been used to find orthologs between proteins in different species, or to find paralogs within a species. Predictions of these evolutionary relationships can be exploited to infer and transfer functional annotations between proteins. In the past decade, high-throughput screening techniques have enabled the construction of protein interaction networks for many model organisms. In addition to direct protein interactions, other associations can also be made between pairs of proteins: coexpression, phylogenetic, neighborhood, gene fusion, etc. Such networks provide the opportunity to characterize a protein not just by its sequence, but by its interaction and association partners. This talk explains how to exploit these networks to detect functionally similar proteins between different species. Such networks, particularly the protein interaction networks, provide more direct evidence of function than does sequence similarity. We evaluate the power of various metrics for uncovering functionally similar proteins without using sequence similarity. In addition, we apply Rankprop, a diffusion-based process that has previously been used on sequence similarity, to these networks. We show that the use of networks from multiple organisms yields improvements in precision and recall. Furthermore, this procedure can be used to disambiguate predictions made by sequence-based methods, as well as correct errors. These techniques show promising applications as more interaction data becomes available. They also have potential future applications to the detection of analogous proteins, i.e., those that evolved the same function independently and thus lack sequence similarity. TEXTBOOK --------- Mount, Bioinformatics: Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press, 2004. Chapters 1-7, 11. PAPERS: General area: Protein networks --------------------------------------- Barabasi and Oltvai, Network Biology: Understanding the Cell's Functional Organization. Nature Reviews Genetics, February 2004, 101-113. Nabieva and Singh, Protein function prediction via analysis of interactomes. Prediction of Protein Structures, Functions, and Interactions (ed J. Bujnicki), 2009. Zhu et al, Getting connected: analysis and principles of biological networks. Genes & Developmnent 21 (2007): 1010-1024. PAPERS: Subareas ----------------------------------------------------------------------- Bandyopadhyay et al. Systematic identification of functional orthologs based on protein network comparison. Genome Research 16 (2006), pp. 428-435. Li et al. OrthoMCL: Identification of Ortholog Groups for Eukaryotic Genomes. Genome Research 13 (2003), pp. 2178-2189. Remm et al. Automatic Clustering of Orthologs and In-paralogs from Pairwise Species Comparisons. J. Molecular Biology (2001) 314, pp. 1041-1052. Sharan et al. Conserved patterns of protein interaction in multiple species. PNAS, February 8, 2005, 1974-1979. Sharan and Ideker. Modeling cellular machinery through biological network comparison. Nature Biotechnology 24 (2006), 427-433. Singh et al. Global alignment of multiple protein interaction networks with application to functional orthology detection. PNAS, September 2, 2008, pp. 12763-12768. Yosef et al. Improved Network-based Identification of Protein Orthologs. Bioinformatics Vol. 24 ECCB 2008, pp. i200-i206.

1 0

A Halderman FPO
by Melissa Lawson 04 May '09

04 May '09

Alex Halderman will present his FPO on Friday May 8 at 8AM in Room 402. The members of his committee are: Ed Felten, advisor; Andrew Appel and Avi Rubin (Johns Hopkins), readers; Brian Kernighan and Adam Finkelstein, nonreaders. A copy of his thesis, "Investigating Security Failures and their Causes: An Analytic Approach to Computer Security", is on display in Room 310. Everyone is invited to attend his talk.

1 0

J Terrace general exam
by Melissa Lawson 01 May '09

01 May '09

Jeff Terrace will present his research seminar/general exam on Friday May 8 at 2PM in Room 302 (note room). The members of his committee are: Mike Freedman, advisor, Jennifer Rexford, and Vivek Pai. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. --------------------------------------------------- Abstract: Massive storage systems typically replicate and partition data over many potentially-faulty components to provide both reliability and scalability. Yet many commercially- deployed systems, especially those designed for inter- active use by customers, sacrifice stronger consistency properties in the desire for greater availability and higher throughput. I will present the design, implementation, and evaluation of CRAQ, a distributed object-storage system that challenges this inflexible tradeoff. The basic approach, an improvement on Chain Replication, maintains strong consistency while greatly improving read throughput. By distributing load across all object replicas, CRAQ scales linearly with chain size without increasing consistency coordination. At the same time, it exposes non- committed operations for weaker consistency guarantees when this suffices for some applications, which is especially useful under periods of high system churn. I will explore additional design and implementation considerations for geo-replicated CRAQ storage across multiple datacenters to provide locality-optimized operations. I will also discuss multi-object atomic updates and multicast optimizations for large-object updates. Reading List: [1] G. DeCandia, D. Hastorun, M. Jampani, G. Kakula-pati, A. Lak-shman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon’s highly available key-value store. [2] R. Guerraoui, D. Kostic, R. R. Levy, and V. Quma. A high throughput atomic storage algorithm. [3] R. van Renesse and F. B. Schneider. Chain replication for supporting high throughput and availability. [4] I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup protocol for Internet applications. [5] M. Burrows. The Chubby lock service for loosely-coupled distributed systems. [6] S. Ghemawat, H. Gobioff, and S.-T. Leung. The google ?le system. [7] M. Castro and B. Liskov. Practical byzantine fault tolerance. [8] B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS:Yahoo!'s Hosted Data Serving Platform. [9] M. K. Aguilera, A. Merchant, M. Shah, A. Veitch, and C. Karamanolis. Sinfonia: a new paradigm for building scalable distributed systems. In Proc. SOSP, Oct. 2007. [10] K. P. Berman. Reliable Distributed Systems, Chapters 13-19.

1 0

W Lloyd general exam
by Melissa Lawson 01 May '09

01 May '09

Wyatt Lloyd will present his research seminar/general exam on Friday May 8 at 10AM in Room 302 (note room). The members of his committee are: Mike Freedman, advisor, Jennifer Rexford, and Larry Peterson. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ---------------------------------------------- Abstract: Byzantine fault-tolerant (BFT) replication, while offering robustness in the face of arbitrary failures, arguably has not been widely adopted due to its performance overhead. System designers often opt for protocols that sacrifice consistency or avoid replicating work, at the cost of correctness in the face of failures. By using historical information, however, I will argue that stronger consistency and high performance are not mutually exclusive. This talk will present Prophecy, a system that interposes itself between clients and any replicated service to minimize request replication when results are historically consistent. At the core of Prophecy is a trusted sketcher component, designed to replace the semi-trusted load balancer that mediates access to a service. The sketcher maintains a compact history table of request/response pairs that allows it to perform fast, load-balanced reads when state transitions do not occur, and slow, replicated reads otherwise. Despite its simplicity, the sketcher provides a new form of consistency called delay-once consistency: informally, faulty nodes can return only stale (not arbitrary) data and only for an exponentially-small number of times. A prototype implementation demonstrates Prophecy's high throughput compared to BFT systems, and its competitiveness with traditional load-balancing. I will also describe and evaluate Prophecy's ability to scale-out to support large replica groups. As Prophecy is most effective when state transitions are rare, I will finally present a measurement study of popular websites that demonstrates a high extent of static data. Reading List: __Papers__ [1] L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Sys., 4(3), 1982. [2] Castro, M. and Liskov, B. Practical byzantine fault tolerance. In OSDI, 1999. [3] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: Speculative Byzantine fault tolerance. In SOSP, 2007. [4] A. Clement, E. Wong, L. Alvisi, and M. Dahlin. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults. In NSDI, 2009. [5] M. P. Herlihy, and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Sys. 12(3), 1990. [6] B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. In VLDB, 2008. [7] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. In SOSP, 2007. [8] Fitzpatrick, B. 2004. Distributed caching with memcached. Linux Journal, 124, 2004. [9] J. Karlin, S. Forrest, and J. Rexford. Pretty Good BGP: Improving BGP by cautiously adopting routes. In ICNP, Nov. 2006. [10] L. Poole, and V.S. Pai. ConfiDNS: leveraging scale and history to detect compromise. In USENIX Annual, June 2008. __Textbook__ K. P. Birman, Reliable Distributed Systems, Springer, 2008. Part III and Chapter 24.6.

1 0

Y Wang FPO
by Melissa Lawson 29 Apr '09

29 Apr '09

Yi Wang will present his FPO on Wednesday May 6 at 3PM in Room 402. The members of his committee are: Jen Rexford, advisor; Mike Freedman and Jacobus Van der Merwe (AT&T), readers; Larry Peterson and Ed Felten, nonreaders. A copy of his thesis, "A Principled Approach to Managing Routing in Large ISP Networks", is on display in Room 310. Everyone is invited to attend his talk.

1 0

E Raman FPO
by Melissa Lawson 29 Apr '09

29 Apr '09

Easwaran Raman will present his FPO on Wednesday May 6 at 9:30AM in Room 402. The members of his committee are: David August, advisor; Doug Clark and Teresa Johnson (HP Labs), readers; David Walker and Vivek Pai, nonreaders. A copy of his thesis "Parallelization Techniques with Improved Dependence Handling", is on display in Room 310. Everyone is invited to attend his talk.

1 0