- talks - lists.cs.princeton.edu

4:30pm Thu Jun 25 talk on P2P live video streaming in E-Quad B-205
by Jennifer Rexford 23 Jun '09

23 Jun '09

Speaker: S. H. Gary Chan, Department of Computer Science and Engineering The Hong Kong University of Science and Technology (HKUST) Title: Proxy-P2P Live Streaming Date/time: 4:30pm on Thursday June 25th Location: B-205 in the E-Quad Abstract: Peer-to-peer (P2P) is a promising technique for live streaming to large distributed group (such as IPTV services). In this talk, we address the design of a proxy-based peer-to-peer (proxy-P2P) streaming network, where the proxies (or super-nodes) are used as "backbone" to carry streams to local users (peers). Users, after mapping to their nearby proxies, get their streams in a peer-to-peer manner. We investigate how to achieve bandwidth-efficient low-delay streaming in such a network. At the proxy level, we study the use of mesh to achieve a certain streaming rate requirement. Since the delay is the slowest path from the source, we design a distributed algorithm called FastMesh which seeks to minimize the worst-case delay of the proxies. At the peer level, we propose and study an efficient distributed algorithm called SIM (Scalable Island Multicast) which combines overlay with IP-multicast. Through simulation and PlanetLab experiments, we show that our algorithms substantially outperform traditional and state-of-the-art approaches. At HKUST, we are currently implementing such a proxy-P2P streaming network and I will share our experience on that at the end of the talk.

1 0

H Ringberg FPO
by Melissa Lawson 17 Jun '09

17 Jun '09

Haakon's FPO will be held on Monday June 29. However, the committee will be Jen Rexford, Brian Kernighan, and Larry Peterson (in place of Rob Calderbank). Time will be 10AM in Room 402.

1 0

H Ringberg FPO
by Melissa Lawson 17 Jun '09

17 Jun '09

Haakon Ringberg will present his FPO on Monday June 29 at 10AM in Room 402. The members of his committee are: Jennifer Rexford, advisor; Mike Freedman and Nick Duffield (AT&T), readers; Brian Kernighan and Rob Calderbank, nonreaders. A copy of his thesis, "Privacy-Preserving Collaborative Anomaly Detection", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Talk Wednesday 6/17 - Room 402 - 10:30am
by Ginny Hogan 16 Jun '09

16 Jun '09

Talk: Wednesday 6/17 - Room 402 - 10:30am - Jean-Pierre INRIA: A Research Institute in Information and Communication Science and Technology. This presentation will introduce INRIA, a French Research Institute in Information and Communication Science and Technology. After giving some figures concerning the Institute itself (workforce, organization, ...), we will present its strategy for the next 4 years, its Research orientations and the opportunities this strategy may offer in terms of cooperation, mutual projects, research positions (PhD, Post docs, permanent positions, ...), .... We will also insist on the ambition of INRIA to become a key research Institution in ICST at the EUROPEAN level. INRIA Jean-Pierre

1 0

E Karpilovsky FPO
by Melissa Lawson 08 Jun '09

08 Jun '09

Elliott Karpilovsky will present his FPO on Friday June 12 at 10AM in Room 402. The members of his committee are: Jen Rexford, advisor; Larry Peterson and Aman Shaikh (AT&T), readers; Vivek Pai and Mike Freedman, nonreaders. A copy of his thesis, "Reducing Memory Requirements for Routing Protocols", is on display in Room 310. Everyone is invited to attend his talk.

1 0

C Kim FPO
by Melissa Lawson 04 Jun '09

04 Jun '09

Chang Kim will present his FPO on Tuesday June 9 at 10 AM in Room 402. The members of his committee are: Jennifer Rexford, advisor; Mike Freedman and Albert Greenberg (AT&T), readers; Vivek Pai and Margaret Martonosi, nonreaders. A copy of his thesis, "Scalable and Efficient Self-Configuring Networks", is on display in Room 310. Everyone is invited to attend his talk.

1 0

(no subject)
by Ginny Hogan 03 Jun '09

03 Jun '09

When: Wednesday, June 10, 2009 3:30 PM (EDT) Where: AT&T Shannon Laboratory Florham Park NJ auditorium, C050 Simulcast to Middletown, MT A3_4G23 Also available via NetMeeting. Details to follow. Reception: 4:30pm-5:30pm in the Florham Park Cafeteria *~*~*~*~*~*~*~*~*~* Frontiers in Research and Education in Computing: A View from the National Science Foundation Jeannette M. Wing President's Professor of Computer Science, Computer Science Department, Carnegie Mellon University Assistant Director, Computer and Information Science and Engineering Directorate, National Science Foundation Abstract: The NSF Computer and Information Science and Engineering Directorate funds 84% of all academic computer science research in the United States. I will present highlights of CISE's research and education programs, including current interests in cyber-enabled discovery and innovation, cyber physical systems, data-intensive computing, network science and engineering, socially intelligent computing, and trustworthy computing; and future interests in information technology's role in energy and the environment and the intersection of computer science and economics. I will also put NSF's investments in computing within the broader national and international context. Bio: Dr. Jeannette M. Wing is the President's Professor of Computer Science in the Computer Science Department at Carnegie Mellon University. She received her S.B. and S.M. degrees in Electrical Engineering and Computer Science in 1979 and her Ph.D. degree in Computer Science in 1983, all from the Massachusetts Institute of Technology. From 2004-2007, she was Head of the Computer Science Department at Carnegie Mellon. Currently on leave from CMU, she is the Assistant Director of the Computer and Information Science and Engineering Directorate at the National Science Foundation. Professor Wing's general research interests are in the areas of specification and verification, concurrent and distributed systems, programming languages, and software engineering. Her current focus is on the foundations of trustworthy computing. Professor Wing was or is on the editorial board of eleven journals. She has been a member of many advisory boards, including: the Networking and Information Technology (NITRD) Technical Advisory Group to the President's Council of Advisors on Science and Tecbnology (PCAST), the National Academies of Sciences's Computer Science and Telecommunications Board, ACM Council, the DARPA Information Science and Technology (ISAT) Board, NSF's CISE Advisory Committee, Microsoft's Trustworthy Computing Academic Advisory Board, and the Intel Research Pittsburgh's Advisory Board. She is a member of the Sloan Research Fellowships Program Committee. She is a member of AAAS, ACM, IEEE, Sigma Xi, Phi Beta Kappa, Tau Beta Pi, and Eta Kappa Nu. Professor Wing is an AAAS Fellow, ACM Fellow, and IEEE Fellow.

1 0

Talk Today - Friday May 15th 1:30 pm Carl Ican Lab 280
by Ginny Hogan 15 May '09

15 May '09

TITLE: Discrete Methods for the Computational Analysis of Biological Networks and Pathways SPEAKER: Ron Y. Pinter, Dept. of Computer Science and the Rappaport School of Medicine, Technion - Israel Institute of Technology LOCATION: Carl Ichan Lab 280 ABSTRACT: Elucidating the structure and function of biological networks and pathways requires the development and the application of computational tools and techniques. Naturally, different methods are suitable for different kinds of analyses, e.g. employing discrete vs. continuous models, extracting qualitative vs. observing quantitative properties, and utilizing static vs. dynamic analyses. In this talk I will describe a number of discrete methods that we have devised recently to analyze both metabolic pathways as well as protein-protein interaction and regulation networks. In some cases these analyses have been static, allowing us to extract instructive information from the description of a network or a pathway; and in others - dynamic, aiming to understand and predict the behavior of a network or a pathway over time. In all cases I will present both the modeling as well as algorithmic issues along with the biological consequences that they have yielded. Specifically, the talk will include a detailed description of identifying composite network motifs, a method for the alignment of metabolic pathways and some of its applications, and the dynamic analysis of transient behavior in developmental pathways.

1 0

S Sen general exam
by Melissa Lawson 14 May '09

14 May '09

Sid Sen will present his research seminar/general exam on Wednesday May 20 at 1:30PM in Room 402. The members of his committee are: Mike Freedman and Bob Tarjan, co-advisors, and Jen Rexford. 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 -------- We work at the boundary of systems and theory with the goal of designing data structures and algorithms for scalable, fault-tolerant distributed systems and other applications. This talk presents foundational progress on both sides, guided by a common theme: simplicity. That is, we allow complexity in the analysis of our designs, not their implementations. On the theory side, we present two new data structures for organizing information: the rank-pairing heap and the rank-balanced tree. Rank-pairing heaps use the minimum balance information possible in arguably the simplest way, matching the performance guarantees of Fibonacci heaps with no cascading structural changes. Rank-balanced trees support insertion and deletion in O(1) amortized time and at most two rotations worst-case, improving on red-black trees. A novel analysis based on an exponential potential function shows that nodes in a rank-balanced tree are rebalanced exponentially infrequently in their heights. We are conducting a thorough experimental evaluation of these data structures, with promising preliminary results. On the systems side, we propose a simple architecture for making fault tolerant protocols scalable and efficient in the wide area. We present Prophecy, a system that interposes itself between clients and a service replica group to minimize request replication when results are historically consistent. Prophecy uses compact sketching and load-balancing to provide what we call delay-once consistency: informally, faulty nodes can return only stale (not arbitrary) data and only for an exponentially-small number of times. We have implemented Prophecy and demonstrated its high throughput and scalability compared to Byzantine fault-tolerant (BFT) and quorum-based systems. We also present a measurement study of popular websites that demonstrates a high extent of static (historically- consistent) data. Reading list ------------ Books: 1. Thomas. H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, Cambridge, MA, 2nd edition, 2001. [Chapters 1-26, 34-35] 2. Andrew S. Tanenbaum and Maarten van Steen. Distributed Systems: Principles and Paradigms. Prentice Hall, Upper Saddle River, NJ, 2002. [Chapters 7-8] Papers: [1] R. E. Tarjan. Amortized computational complexity. SIAM J. Alg. Disc. Meth., 6:306-318, 1985. [2] Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. [3] Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652-686, 1985. [4] M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1(1):111-129, 1986. [5] Robert E. Tarjan. Efficiency of a good but not linear set union algorithm. J. of the ACM, 22(2):215-225, 1975. [6] Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. [7] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, 1982. [8] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In OSDI, pages 173-186, 1999. [9] Ramakrishna Kotla, Lorenzo Alvisi, Michael Dahlin, Allen Clement, and Edmund L. Wong. Zyzzyva: speculative byzantine fault tolerance. In SOSP, pages 45-58, 2007. [10] Yanhua Mao, Flavio Paiva Junqueira, and Keith Marzullo. Mencius: Building efficient replicated state machine for WANs. In OSDI, pages 369-384, 2008. [11] Brian F. Cooper, Raghu Ramakrishnan, Utkarsh Srivastava, Adam Silberstein, Philip Bohannon, Hans-Arno Jacobsen, Nick Puz, Daniel Weaver, and Ramana Yerneni. PNUTS: Yahoo!'s hosted data serving platform. VLDB, 1(2):1277-1288, 2008. [12] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon's highly available key-value store. In SOSP, pages 205-220, 2007.

1 0

A Pop general exam
by Melissa Lawson 14 May '09

14 May '09

Ana Pop will present her research seminar/general exam on Wednesday May 20 at 10AM in room 402. The members of her committee are: Olga Troyanskaya, advisor, David Blei, and Rob Schapire. 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. ------ Abstract: ------ The availability of genome-scale data has enabled gene function prediction for different organisms. Computational approaches to this problem have aimed to integrate all this heterogeneous information. One method that has been applied with great success has been Bayesian data integration, which, given the genomic data and known functional relationships, can predict other functional relationships and organize the genomic information into functional relationship networks. In addition to understanding the function of genes we also aim to understand the progression of these genes' functions and interactions as the organism develops. Computational approaches have been applied mostly to simple organisms such as the very well-studied Saccharomyces cerevisiae (baker's yeast). More complex organisms, such as Arabidopsis thaliana (the model organism for plants), which is the focus of this project, are much more challenging to analyze as they are substantially more complex and have different tissues types and development stages. Therefore, this plant is ideal for a developmental gene functional networks study. We have created a global functional network for Arabidopsis where nodes are genes and links between the nodes represent a functional relationship (the link weight represents the probability of interaction). Analysis of this network showed that the top few hundred highest scoring functional relationships are between genes related to photosynthesis. In addition to the global network, we also have biological process context-specific networks for Arabidopsis, which shows gene functional relationships in different biological process contexts (such as cell cycle or DNA replication). We are also extending this model to determine developmental progression of gene function both globally and in various development-stage contexts. We expect that overlaying the biological process context-specific networks with the development stage context-specific networks will shed light on the way gene function progresses over the different developmental stages of the plant. ------ Reading List: ------ [Book] Artificial Intelligence: A Modern Approach (Second Edition) by Stuart Russell and Peter Norvig - section V (Uncertain knowledge and reasoning) - section VI (Learning) [1] C Huttenhower, O Troyanskaya; Bayesian data integration: a functional perspective; Comput. Syst. Bioinformatics, 2006 [2] Guan Y, Myers CL, Hess DC, Barutcuoglu Z, Caudy AA, Troyanskaya OG: Predicting gene function in a hierarchical context with an ensemble of classifiers. Genome Biol 2008, 9(suppl 1):S3. [3] Curtis Huttenhower, Erin M. Haley, Matthew A. Hibbs, Vanessa Dumeaux, Daniel R. Barrett, Hilary A. Coller, and Olga G. Troyanskaya. Exploring the human genome with functional maps, Genome Research 2009 [4] S Rogers, M Girolami, A Bayesian regression approach to the inference of regulatory networks from gene expression data., Bioinformatics, Vol. 21, No. 14. (15 July 2005), pp. 3131-3137 [5] Paul Pavlidis, Jason Weston, Jinsong Cai and William Noble Grundy, Learning gene functional classifications from multiple data types, Journal of Computational Biology. 9(2):401-411, 2002 [6] Quackenbush J., Computational analysis of microarray data., Nat Rev Genet. 2001 Jun;2(6):418-27 [7] Brendan J. Frey and Delbert Dueck, Clustering by Passing Messages Between Data Points, (11 January 2007) Science [8] Alter O, Brown PO, Botstein D (2000) Singular value decomposition for genomewide expression data processing and modeling. Proc Natl Acad Sci USA 97:10101-10106. [9] Boyes et al., 2001 D.C. Boyes, A.M. Zayed, R. Ascenzi, A.J. McCaskill, N.E. Hoffman and K.R. Davis, Growth stage-based phenotypic analysis of Arabidopsis: a model for high throughput functional genomics in plants, Plant Cell 13 (2001), pp. 1499-1510. [10] S.M. Brady et. al. A high-resolution root spatiotemporal map reveals dominant expression patterns. Science 318 (2007), 801-806 [11] Anjali Iyer-Pascuzzi, June Simpson, Luis Herrera-Estrella, Philip N Benfey, Functional genomics of Arabidopsis root functional genomics, Current Opinion in Plant Biology, In Press, Corrected Proof, Available online 29 December 2008

1 0