- talks - lists.cs.princeton.edu

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

3pm talk today on Sustainable Networks and Systems for the Developing World in room 402
by Jennifer Rexford 28 Apr '09

28 Apr '09

Speaker: Lakshmi Subramanian, NYU Title: Sustainable Networks and Systems for the Developing World Date/time: 3-4pm Tuesday April 28 Location: room 402 in the Computer Science building Abstract: The Internet and the World Wide Web have largely remained urban phenomena and a significant fraction of the developing world, especially in rural and underdeveloped regions, remains disconnected from the rest of the world. In this talk, I will briefly elaborate on our current efforts in addressing three broad challenges that can help in bridging the digital divide: (a) developing low-cost high-bandwidth connectivity solutions; (b) extending the Web to developing regions; (c) building new mobile applications for enhancing healthcare and financial services. This talk will specifically focus on the challenge of low-cost connectivity solutions for developing regions. I will describe our experiences in developing and deploying WiFi-based Long Distance (WiLD) Networks, a low-cost connectivity solution which provides the ability to achieve nearly 6-10 Mbps over 100s of kilometers for roughly $1000/link. WiLD networks have been deployed in 10 developing countries and have been used to provide telemedicine services in Aravind Eye hospitals in India to 50,000 patients/year in rural areas which is currently being expanded to cover 500,000 patients/year. We are currently extending WiLD networks to develop WiFi based Rural Extensions (WiRE), a low-cost alternative to cellular networks for rural settings. Bio Prof. Lakshminarayanan Subramanian is an Assistant Professor in the Courant Institute of Mathematical Sciences at NYU. His research interests are in the space of networks, distributed systems, security and technologies for developing regions. He received his MS and PhD from UC Berkeley and B.Tech from IIT-Madras.

1 0

F Cole FPO
by Melissa Lawson 24 Apr '09

24 Apr '09

Forrester Cole will present his FPO on Friday May 1, 2009 in Room 401 (note room). The members of his committee are: Adam Finkelstein, advisor; Tom Funkhouser and Doug DeCarlo (Rutgers), readers; Szymon Rusinkiewicz and David Blei, nonreaders. A copy of his thesis, "Line Drawings of 3D Models", is on display in Room 310. Everyone is invited to attend his talk.

1 0

T Capra FPO
by Melissa Lawson 24 Apr '09

24 Apr '09

Tony Capra will present his FPO on Friday May 1, 2009 at 10AM in Room 302 (note room). The members of his committee are: Mona Singh, advisor; Olga Troyanskaya and Tom Funkhouser, readers; Frederick Hughson (MOL) and Christodoulos Floudas (ChemEng), nonreaders. A copy of his thesis, "Algorithms for the Identification of Functional Sites in Proteins", is on display in Room 310. Everyone is invited to attend his talk.

1 0

FW: generals stuff
by Melissa Lawson 22 Apr '09

22 Apr '09

Peng Jiang will present his research seminar/general exam on Tuesday April 28 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: Large-scale biological networks are being determined at an increasing pace. Computational analyses of the resulting data provide new opportunities for revealing cellular organization and uncovering protein function and pathways. Clustering is one of the most widely used computational approaches for analyzing these types of biological data, and can reveal important modular structures. Previous network clustering algorithms in bio-informatics community work well on midsized networks such as, for example, the yeast protein interaction network. However, by recent computational techniques for data integration, we are starting to get large biological networks for numerous organisms. In these networks, there might be tens thousands of nodes and millions or even hundreds millions of interactions in a single graph. In such cases, previous biological clustering algorithms will be impractically slow or entirely unapplicable. In our work, we present a graph clustering algorithm with time complexity O(Vlog(V)+E) and space complexity O(E), where V and E are the number of vertices edges in the graph. By testing on several large genomic networks, our algorithm successfully clustered all of them, whereas most previous approaches failed. In the cases where previous approaches were able to cluster these networks, our algorithm was hundreds of times faster. We validated our approach with respect to its ability to uncover biologically relevant clusters and show we get state-of-the-art performance. Our fast algorithm enables us to perform new types of analysis. For example, we clustered a recent human context specific network data set over 230 different conditions, resulting in 230 networks which are nearly 300GB in total. We were able to uncover clusters specific to individual networks, putatively corresponding to context-specific modules, a type of analysis which was not possible prior to our work. Readlist: Book: [1] Thomas HC, Charles EL, Ronald LR, Clifford S. (2001) Introduction to algorithm, 2nd edition. MIT press Papers: [1] Broh´ee S., van Helden J. (2006) Evaluation of clustering algorithms for protein-protein interaction networks, BMC Bioinformatics, 7, 488. [2] Enright A.J., Van Dongen S., Ouzounis C.A. (2002) An efficient algorithm for largescale detection of protein families, Nucleic Acids Research, 30(7), 1575-1584. [3] Altaf-Ul-Amin M, Shinbo Y, Mihara K, Kurokawa K, Kanaya S. (2006) Development and implementation of an algorithm for detection of protein complexes in large interaction networks, BMC Bioinformatics, 7, 207. [4] Jensen LJ, Kuhn M, Stark M, Chaffron S, Creevey C, Muller J, Doerks T, Julien P, Roth A, Simonovic M, Bork P, von Mering C. (2009) STRING 8a global view on proteins and their functional interactions in 630 organisms, Nucleic Acids Res, 37, D412-416. [5] Bobby-Joe Breitkreutz, Chris Stark, Teresa Reguly, Lorrie Boucher, Ashton Breitkreutz, Michael Livstone, Rose Oughtred, Daniel Lackner, Jurg Bhler, Valerie Wood, Kara Dolinski and Mike Tyers. (2008) The BioGRID Interaction Database: 2008 Update, Nucleic Acids Res, 36, D637-640. [6] Curtis Huttenhower, Erin M. Haley3, Matthew A. Hibbs, Vanessa Dumeaux, Daniel R. Barrett, Hilary A. Coller, Olga G. Troyanskaya. (2009) Exploring the human genome with functional maps, Genome Research, 4(9), e1000165. [7] Fredman ML, Tarjan RE. (1987) Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, 34(3), 596-615. [8] Rhee SY,Wood V, Dolinski K, Draghici S. (2008) Use and misuse of the gene ontology annotations, Nat Rev Genet, 9(7), 509-515. [9] Lord PW, Stevens RD, Brass A, Goble CA. (2003) Investigating semantic similarity measures across the Gene Ontology: the relationship between sequence and annotation, Bioinformatics, 19(10), 1275-1283.

1 0

4:30 p.m. Roger Johnston on physical and cyber security
by Andrew W. Appel 21 Apr '09

21 Apr '09

1 0