- talks - lists.cs.princeton.edu

4:30pm Wed Sep 29 colloquium by Michael Mitzenmacher
by Jennifer Rexford 28 Sep '10

28 Sep '10

Some Open Questions Related to Cuckoo Hashing Michael Mitzenmacher, Harvard Wednesday, September 29 4:30pm in CS 105 (with tea at 4pm in the 2nd floor tea room) In this talk, we will describe cuckoo hashing, a recently developed hashing scheme that offers the benefits of very high memory utilization and worst-case constant lookup times. We then discuss recent work in the area, including theoretical bounds on performance, practical methods for improving performance, and implementations on a GPU. Along the way, we will suggest several remaining open questions. The talk will require no prior background on cuckoo hashing, and is aimed for a wide audience, including both theory and systems. Michael Mitzenmacher is a Professor of Computer Science in the School of Engineering and Applied Sciences at Harvard University. Michael has authored or co-authored over 150 conference and journal publications on a variety of topics, including Internet algorithms, hashing, load-balancing, erasure codes, error-correcting codes, compression, bin-packing, and power laws. His work on low-density parity-check codes received the 2002 IEEE Information Theory Society Best Paper Award and the 2009 SIGCOMM Test of Time Award. His textbook on probabilistic techniques in computer science, co-written with Eli Upfal, was published in 2005 by Cambridge University Press.

2 1

2pm Fri Oct 1 talk on "predicting faults in heterogenous federated distributed systems"
by Jennifer Rexford 24 Sep '10

24 Sep '10

Speaker: Professor Dejan Kostic, EPFL Title: Predicting Faults in Heterogeneous, Federated Distributed Systems Date/time: 2:00-3:00pm on Friday October 1 Location: CS 302 Abstract: It is notoriously difficult to make distributed systems reliable. This becomes even harder in the case of the widely-deployed systems that become heterogeneous and federated. The set of routers in charge of the inter-domain routing in the Internet is a prime example of such a system. The unanticipated interaction of nodes under seemingly valid configuration changes and local fault-handling can have a profound effect. For example, the Internet has suffered from multiple IP prefix hijackings, as well as performance and reliability problems due to emergent behavior resulting from a local session reset. We argue that the key step in making these systems reliable is the need to automatically predict faults. In this talk, I will describe the design and implementation of DiCE, a system that uses temporal and spatial awareness to predict faults in heterogeneous, federated systems. Our live evaluation in the testbed shows that DiCE quickly and successfully predicts two important classes of faults, operator mistakes and programming errors, that have plagued BGP routing in the Internet. Joint work with Marco Canini, Vojin Jovanovic, and Gautam Kumar Bio: Dejan Kostić obtained his Ph.D. in Computer Science at the Duke University, under Amin Vahdat. He spent the last two years of his studies and a brief stay as a postdoctoral scholar at the University of California, San Diego. He received his Master of Science degree in Computer Science from the University of Texas at Dallas, and his Bachelor of Science degree in Computer Engineering and Information Technology from the University of Belgrade (ETF), Serbia. In January 2006, he started as a tenure-track assistant professor at the School of Computer and Communications Sciences at EPFL (Ecole Polytechnique Fédérale de Lausanne), Switzerland. In 2010, he received a European Research Council (ERC) Starting Investigator Award. His interests include Distributed Systems, Computer Networks, Operating Systems, and Mobile Computing.

1 0

Colloquium Speaker, Sept. 22- Dick Sites
by Nicole E. Wagenblast 21 Sep '10

21 Sep '10

Identifying Dark Latency Richard L. Sites, Google, Inc. Wednesday, September 22, 2010, 4:30 PM Small Small Auditorium CS105 In astronomy and cosmology, dark matter is hypothetical matter that is undetectable by its emitted radiation, but whose presence can be inferred from gravitational effects on visible matter. [Wikipedia] By analogy, dark latency in software is latency that is undetectable directly, but whose presence can be inferred from overall application delays. We bring four tools to bear to observe dark latency in some Google web services, then identify and fix several root causes, in low-level Google libraries and in the TCP stack. The talk makes a case for building and using very low-overhead tools to do bursty tracing of hundreds of thousands of timestamped events per second. A methodology of time-aligning multiple traces (remote procedure call, network, CPU, and lock-contention) across scores of interacting machines is the minimum needed to understand some sources of latency in real web services. Dick Sites is a Senior Staff Engineer at Google, where he has worked for 6 years. He previously worked at Adobe Systems, Digital Equipment Corporation, Hewlett-Packard, Burroughs, and IBM. His accomplishments include co-architecting the DEC Alpha computers, advancing the art of binary translation for computer executables, adding electronic book encryption to Adobe Acrobat, decoding image metadata for Photoshop, and building various computer performance monitoring and tracing tools at the above companies. He also taught Computer Science for four years at UC/San Diego. Most recently he has been working on Unicode text processing and on CPU and network performance analysis at Google. Dr. Sites holds a PhD degree in Computer Science from Stanford and a BS degree in Mathematics from MIT. He also attended the Master's program in Computer Science at University of North Carolina 1969-70. He holds 34 patents and was recently elected to the U.S. National Academy of Engineering.

1 0

Colloquium Speaker, Sept. 22- Dick Sites
by Nicole E. Wagenblast 16 Sep '10

16 Sep '10

Identifying Dark Latency Richard L. Sites, Google, Inc. Wednesday, September 22, 2010, 4:30 PM Small Small Auditorium CS105 In astronomy and cosmology, dark matter is hypothetical matter that is undetectable by its emitted radiation, but whose presence can be inferred from gravitational effects on visible matter. [Wikipedia] By analogy, dark latency in software is latency that is undetectable directly, but whose presence can be inferred from overall application delays. We bring four tools to bear to observe dark latency in some Google web services, then identify and fix several root causes, in low-level Google libraries and in the TCP stack. The talk makes a case for building and using very low-overhead tools to do bursty tracing of hundreds of thousands of timestamped events per second. A methodology of time-aligning multiple traces (remote procedure call, network, CPU, and lock-contention) across scores of interacting machines is the minimum needed to understand some sources of latency in real web services. Dick Sites is a Senior Staff Engineer at Google, where he has worked for 6 years. He previously worked at Adobe Systems, Digital Equipment Corporation, Hewlett-Packard, Burroughs, and IBM. His accomplishments include co-architecting the DEC Alpha computers, advancing the art of binary translation for computer executables, adding electronic book encryption to Adobe Acrobat, decoding image metadata for Photoshop, and building various computer performance monitoring and tracing tools at the above companies. He also taught Computer Science for four years at UC/San Diego. Most recently he has been working on Unicode text processing and on CPU and network performance analysis at Google. Dr. Sites holds a PhD degree in Computer Science from Stanford and a BS degree in Mathematics from MIT. He also attended the Master's program in Computer Science at University of North Carolina 1969-70. He holds 34 patents and was recently elected to the U.S. National Academy of Engineering.

1 0

U Syed FPO today - time change
by Melissa Lawson 26 Aug '10

26 Aug '10

Umar's FPO has been moved from 2PM to 3PM today. It will still be held in Room 402. --Melissa

1 0

U Syed FPO
by Melissa Lawson 20 Aug '10

20 Aug '10

Umar Syed will present his FPO on Thursday August 26 at 2PM in Room 402. The members of his committee are: Rob Schapire, advisor; David Blei and Warren Powell (ORFE), readers; Yael Niv (PSY) and Michael Littman (Rutgers), nonreaders. A copy of his thesis, "Reinforcement Learning Without Rewards", is available in Room 310. Everyone is invited to attend his talk.

1 0

M Mahmoody Ghidary FPO
by Melissa Lawson 20 Aug '10

20 Aug '10

Mohammad Mahmoody Ghidary will present his FPO on Wednesday August 25 at 2PM in Room 402. The members of his committee are: Boaz Barak, advisor; Bernard Chazelle and Russell Impagliazzo (IAS and UCSD), readers; Sanjeev Arora and Moses Charikar, nonreaders. A copy of his thesis, "Studies in the Efficiency and (versus) Security of Cryptographic Tasks", is on display in Room 310. Everyone is invited to attend his talk.

1 0

S Nikolova FPO
by Melissa Lawson 09 Jul '10

09 Jul '10

Sonya Nikolova will present her FPO on Friday July 16, 2010 in Room 402 at 10AM. The members of her committee are: Perry Cook, advisor; Christiane Fellbaum and Marilyn Tremaine (Rutgers), readers; Adam Finkelstein and Szymon Rusinkiewicz, nonreaders. A copy of her thesis, "Improving Word-Finding in Assistive Communication Tools: A Mixed-Initiative Approach", is on display in Room 310. Everyone is invited to attend her talk.

1 0

[Released] Z Khan preFPO
by Melissa Lawson 07 Jul '10

07 Jul '10

Zia Khan will present his preFPO on Friday, July 23, 2010 at 1:30pm in Carl Ichan Lab (CIL) 200. The members of his committee are: Mona Singh (CS) advisor, Leonid Kruglyak (EEB) advisor, Ben Garcia (MOL) reader, Hillary Coller (MOL), and Saeed Tavazoie (MOL) nonreaders. Everyone is invited to attend his talk. His abstract follows below. Title: Efficient Algorithms for Liquid Chromatography Coupled Mass Spectrometry Based Protein Quantification Abstract: One of the driving aims of studies that conduct comprehensive, quantitative surveys of proteins and across many experimental samples and replicates is the identification of genes and genetic pathways effected in disease and disease treatment. The prevailing experimental tool for such surveys is instrumentation known as liquid chromatography coupled tandem mass spectrometry (LC-MS/MS). LC-MS/MS generates large data sets in the form of thousands to millions of mass spectra in a single experiment. Converting these spectra into interpretable quantitative output that shows changes in amounts of proteins, their peptide fragments, or enrichment and depletion of post translational modifications presents a substantial computational challenge. This thesis describes a new application of space partitioning data structures: a series of algorithms that leverage fast geometry queries supported by these data structures to significantly improve the speed and quality LC-MS/MS data analysis. In addition, this thesis develops a collection methods, implemented in an open-source software system called PVIEW (http://compbio.cs.princeton.edu/pview), that use the output of these algorithms to enable accurate quantification of proteins, protein fragments, and post translational modifications. These methods are evaluated for quantitative quality and computational efficiency on a wide range of experimental data sets spanning several experimental methodologies and source protein samples.

1 0

11am Tue Jun 15 talk on wide-area route control for distributed services
by Jennifer Rexford 14 Jun '10

14 Jun '10

Speaker: Vytautas Valancius, Georgia Tech Title: Wide-Area Route Control for Distributed Services Date/time: 11:00-11:45am, Tuesday June 15 Location: 402 in CS building Abstract: Many distributed services would benefit from control over the flow of traffic to and from their users, to offer better performance and higher reliability at a reasonable cost. Unfortunately, although today's cloud-computing platforms offer elastic computing and bandwidth resources, they do not give services control over wide-area routing. We propose replacing the data center's border router with a Transit Portal (TP) that gives each service the illusion of direct connectivity to upstream ISPs, without requiring each service to deploy hardware, acquire IP address space, or negotiate contracts with ISPs. Our TP prototype supports many layer-two connectivity mechanisms, amortizes memory and message overhead over multiple services, and protects the rest of the Internet from misconfigured and malicious applications. Our implementation extends and synthesizes open-source software components such as the Linux kernel and the Quagga routing daemon. We also implement a management plane based on the GENI control framework and couple this with our four-site TP deployment and Amazon EC2 facilities. Bio: Vytautas Valancius is a Ph.D candidate at Georgia Institute of Technology, advised by professor Nick Feamster. His research interests include interdomain routing, Internet economics, and network virtualization. Prior to his Ph.D studies, Vytautas obtained M.S. in KTH, Sweden and worked in the networking industry as a consultant for 5 years, earning CCIE#14359 certification.

1 0