- talks - lists.cs.princeton.edu

X Li general exam
by Melissa M. Lawson 15 Jan '13

15 Jan '13

Xiaozhou Li will present his research seminar/general exam on Tuesday January 22 at 10AM in room 402. The members of his committee are: Michael Freedman (advisor), Jen 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. ------------------------------------ Title: Scaling IP Multicast on Datacenter Topologies Many datacenter applications experience multicast communication patterns, and they could benefit from the reduced bandwidth consumption and server overhead from using IP multicast. Unfortunately, traditional IP multicast management protocols, designed for arbitrary service-provider or enterprise networks, do not provide sufficient scalability in the number of supported multicast groups. This paper examines how the unique topological structure of modern datacenter networks can be leveraged to increase group scalability. Our basic approach carefully partitions the multicast address space and assigns them across switches in datacenters’ multi-rooted tree networks. Our approach further improves scalability by locally aggregating multicast addresses at bottleneck switches, at the cost of slightly inflating downstream traffic. We evaluate the system’s scalability, traffic overhead, and fault tolerance through a mix of simulation and analysis. Experiments show that a datacenter with 27,648 servers and commodity switches can support up to 100,000 multicast groups with 50 members on average, which allows each physical server to subscribe to nearly 200 multicast groups concurrently. Textbook: Computer Networks: A Systems Approach (5th edition), L. Peterson and B. Davie Papers: Datacenter Network A Scalable, Commodity Data Center Network Architecture [SIGCOMM 08] M. Al-Fares, A. Loukissas, and A. Vahdat http://cseweb.ucsd.edu/~malfares/comm298-alfares.pdf VL2: A Scalable and Flexible Data Center Network [SIGCOMM 09] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandular, C. Kim, P. Lahiri,D. A. Maltz, P. Patel, and S. Sengupta http://research.microsoft.com/pubs/80693/vl2-sigcomm09-final.pdf F10: Fault-Tolerant Engineered Networks V. Liu, D. Halperin, A. Krishnamurthy, and T. Anderson ftp://ftp.cs.washington.edu/tr/2012/09/UW-CSE-12-09-05.PDF Multicast Dr. Multicast: Rx for Data Center Communication Scalability [EuroSys 10] Y. Vigfusson, H. Abu-Libdeh, M. Balakrishnan, K. Birman, R. Burgess,G. Chockler, H. Li, and Y. Tock http://research.microsoft.com/pubs/120744/mcmd-eurosys.pdf LIPSIN: Line Speed Publish/Subscribe Inter-Networking [SIGCOMM 09] P. Jokela, A. Zahemszky, C. E. Rothenberg, S. Arianfar, and P. Nikander http://dl.acm.org/citation.cfm?id=1592592 SplitStream: High-Bandwidth Multicast in Cooperative Environments [SOSP 03] M. Castro, P. Druschel, A. Kermarrec, A. Nandi, A. Rowstron and A. Singh http://research.microsoft.com/en-us/um/people/antr/PAST/SplitStream-sosp.pdf Ricochet: Lateral Error Correction for Time-Critical Multicast [NSDI 07] M. Balakrishnan, K. Birman, A. Phanishayee and S. Pleisch http://www.cs.cmu.edu/~amarp/papers/ricochet_nsdi_2007.pdf A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing [TON 97] S. Floyd, V. Jacobson, S. Mccanne, C. Liu and L. Zhang http://dl.acm.org/citation.cfm?id=270863 SDN / Network Management Onix: A Distributed Control Platform for Large-scale Production Networks [OSDI 10] T. Koponen, M. Casado, N. Gude, J. Stribling, L. Poutevski, M. Zhu,R. Ramanathan, Y. Iwata, H. Inoue, T. Hama, and S. Shenker http://yuba.stanford.edu/~casado/onix-osdi.pdf On Controller Performance in Software-Defined Networks [Hot-ICE 12] A. Tootoonchian, S. Gorbunov, Y. Ganjali, M. Casado, and R. Sherwood https://www.usenix.org/system/files/conference/hot-ice12/hotice12-final33_0…

1 0

Graham Cormode, Jan 30
by Ariel Rabkin 15 Jan '13

15 Jan '13

Hi all. Here's another in our series of data and database talks. Talk will be on Jan 30. Room and time TBA. Let me know if you want to meet with the speaker; should be of interest to both theory and systems people. Small Summaries for Big Data In dealing with big data, we often need to look at a small summary to get the big picture. Over recent years, many new techniques have been developed which allow important properties of large distributions to be extracted from compact and easy-to-build summaries. In this talk, I'll highlight some examples of different types of summarization: sampling, sketching, and special-purpose. Then I'll outline the road ahead for further development of such summaries. Graham Cormode is a Principal Member of Technical Staff in the Database Management Group at AT&T Shannon Laboratories in New Jersey. Previously, he was a researcher at Bell Labs, after postdoctoral study at the DIMACS center in Rutgers University from 2002-2004. His PhD was granted by the University of Warwick in 2002. His work considers aspects of managing and working with large amounts of data, with particular emphasis on privacy and anonymization, and large scale analytics. --Ari

1 0

T Jablin FPO
by Melissa M. Lawson 07 Jan '13

07 Jan '13

Tom Jablin will present his FPO on Monday January 14 at 10AM in Room 402. The members of his committee are: David August, advisor; Doug Clark and Scott Mahlke (Michigan), readers; Margaret Martonosi and David Walker, nonreaders. A copy of his thesis, "Automatic parallelization for GPUs", is on display in Room 310. Everyone is invited to attend his talk.

1 0

CJ Bell preFPO
by Melissa M. Lawson 07 Jan '13

07 Jan '13

CJ Bell will present his preFPO on Monday January 14 at 8AM in Room 402. The members of his committee are: David Walker, advisor; Andrew Appel and David August, readers; Sharad Malik (ELE) and Ed Felten, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------- Title: Proving the Correctness of Parallelizing Optimizations Sustaining scalable performance trends in the multicore era requires that programmers and compiler writers rely on thread-level parallelism to attain greater performance from their programs. One way to do so is to develop a sequential program and then apply parallelizing transformations to that sequential program; some compilers do this automatically. However, the optimization phase is the most common source of bugs in a compiler; they are often subtle and hard to detect because many complex optimizations are combined in unique ways for each input program. Thus we have developed a framework of local program rewrite rules, triggered by logical preconditions, and have proven this framework sound in the Coq proof assistant. These local transformations may be composed and recombined in a variety of different ways; in particular, they may be used to implement classic parallelizing optimizations such as DOALL and DOACROSS as well as more modern techniques such as DSWP (Decoupled Software Pipelining) and combinations of the above. The key challenges to proving the soundness of our framework were to develop a generic loop transformation that can rewrite two parallel while loops into one single while loop; a parallelization transformation that allows threads to communicate and does not require termination; and a new definition of behavioral equivalence that is preserved by parallelization, which we call decoupled bisimulation. In this talk, our primary focus is on the details of decoupled bisimulation: why existing definitions of equivalence are insufficient for stating the correctness of parallelization, how it compares to existing definitions, and which behavioral properties it preserves.

1 0

S Gerrish FPO
by Melissa M. Lawson 02 Jan '13

02 Jan '13

Sean Gerrish will present his FPO on Tuesday January 8 at 1PM in Room 402. The members of his committee are: David Blei, advisor; Rob Schapire and Hanna Wallach (U Mass Amherst), readers; Kosuke Imai (POL) and Matthew Salganik (SOC), nonreaders. A copy of his thesis, "Applications of :Latent Variable Models in Modeling Influence and Decision Making", is on display in Room 310. Everyone is invited to attend his talk.

1 0

CS Colloquium Talk By Alyosha Efros on Monday
by Thomas Funkhouser 10 Dec '12

10 Dec '12

*What makes Big Visual Data hard?* *Alexei (Alyosha) Efros* <http://www.google.com/url?sa=t&rct=j&q=&esrc=s&frm=1&source=web&cd=1&cad=rj…> Carnegie Mellon University Princeton CS Colloquium Monday, Dec 10th CS 105 (Small Auditorium), 4:30PM There are an estimated 3.5 trillion photographs in the world, of which 10% have been taken in the past 12 months. Facebook alone reports 6 billion photo uploads per month. Every minute, 72 hours of video are uploaded to YouTube. Cisco estimates that in the next few years, visual data (photos and video) will account for over 85% of total internet traffic. Yet, we currently lack effective computational methods for making sense of all this mass of visual data. Unlike easily indexed content, such as text, visual content is not routinely searched or mined; it's not even hyperlinked. Visual data is Internet's "digital dark matter" [Perona,2010] -- it's just sitting there! In this talk, I will first discuss some of the unique challenges that make Big Visual Data difficult compared to other types of content. In particular, I will argue that the central problem is the lack a good measure of similarity for visual data. I will then present some of our recent work that aims to address this challenge in the context of visual matching, image retrieval and visual data mining. As an application of the latter, we used Google Street View data for an entire city in an attempt to answer that age-old question which has been vexing poets (and poets-turned-geeks): "What makes Paris look like Paris?"

2 2

L Luo preFPO
by Melissa M. Lawson 06 Dec '12

06 Dec '12

Linjie Luo will present his preFPO on Thursday December 13 at 11AM in Room 402. The members of his committee are: Szymon Rusinkiewicz, advisor; Tom Funkhouser and Sylvain Paris (Adobe), readers; Adam Finkelstein and David Dobkin, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --- Title: Towards High Quality Hair Capture and Modeling Abstract: Hair is one of human's most distinctive features and one important component in human digitalization. However, capturing and modeling hair remains challenging because of hair's unique properties: the specular appearance violates the Lambertian surface assumption used in most multi-view stereo reconstruction methods; The vast variations and complex topology of hair styles pose great technical difficulties for high quality hair capture and modeling. We propose an orientation-based matching metric for multi-view hair capture that is more robust to hair's view-dependent specular highlights. The metric is performed in multi-resolution to reveal increasing hair structures and details. The orientation-based metric also facilitates the structure-aware aggregation to reduce matching error and stereo noise along coherent hair structures. Our approach is able to reconstruct approximate surfaces to a variety of hair styles with detailed hair structures from ~30 input views. To alleviate the requirement for dense small-baseline capture setup, we introduce a visual hull based refinement method to enable wide-baseline full hair capture with only 8 views. The refinement is driven by the strands generated from the orientation map of each input view. The final shape is obtained by optimizing the orientation consistency of these strands against all the orientation maps as well as the regularization terms that account for the smoothness at strand, wisp and global levels. We find our method effective on various hair styles and suitable for dynamic hair capture. We achieve an average reconstruction accuracy of ~3mm on synthetic datasets. Finally, we address the challenge of robustly modeling hair strands from the captured incomplete exterior hair geometry with plausible topology for hair simulation. Our main contribution is the construction and analysis of the global connection graph to compute the plausible hair topology from the incomplete exterior hair geometry. The connection graph encodes coherent local strands and plausible inter-strand connections. The final hair strands can be generated from a wisp forest derived from the connection graph.

1 0

Systems Lunch Talk Matt Welsh, Friday (Dec 5) at 12:30pm
by Mike Freedman 05 Dec '12

05 Dec '12

This Friday at 12:30pm (lunch starts at 12:00pm) in Room 302, Matt Welsh will be talking about his experience "making the mobile web faster" at Google. --- Making the Mobile Web Fast Matt Welsh, Google Inc. Web usage on mobile devices is exploding, and in many countries, mobile devices are the predominant means of accessing the Internet. But the mobile web is still incredibly slow; clearly the web was not designed for mobile networks. Our team at Google is working to solve this problem, by optimizing all layers of the stack: device operating systems, browsers, network protocols, servers, and web content. In this talk, I'll talk about why the mobile web is slow, provide some insight into the inner workings of 3G and 4G networks, and provide an overview of some of our efforts to make the mobile web fast. I'll also talk a bit about what it was like to make the leap from academia to industry. Matt Welsh is the head of mobile web performance at Google. Prior to joining Google, he was a professor of Computer Science at Harvard, where he worked on projects ranging from deploying wireless sensor networks on volcanoes in Ecuador to building a swarm of robotic bees. He did his PhD at UC Berkeley.

1 0

Fwd: Zack Ives talk on Wednesday
by Ariel Rabkin 05 Dec '12

05 Dec '12

Hi all. Reminder. This talk is today at 12:30 -- food beforehand. --Ari ---------- Forwarded message ---------- From: Ariel Rabkin <asrabkin(a)cs.princeton.edu> Date: Mon, Dec 3, 2012 at 6:03 PM Subject: Zack Ives talk on Wednesday To: ens(a)lists.cs.princeton.edu Zack Ives is visiting us from UPenn. He will be giving a lunch-time (12:30) talk in rm 302 on December 5. Let me know if you want to meet with him. ASPEN: Seamless Declarative Programming across Sensors, Streams, and the Cloud Due to advances in semiconductor and communications technology, we are steadily moving towards a world filled with a plethora of embedded sensing devices as well as "virtual" sensors within devices -- with the potential to monitor the environment and to react to or even anticipate changes. The environment being monitored might be a smart hospital, an entire campus, or even an office or data center. Often the behaviors we wish to produce involve combining constantly updating (streaming) data from multiple heterogeneous sensor and Internet sources. A major challenge is how to manage the resulting complexity, and to build large-scale, rich monitoring, learning, and control applications. In the ASPEN project we have been exploring an approach that seeks to separate logical dataflow from most of the algorithmic logic -- using a declarative, SQL-like (but iterative and incremental) programming model to capture the dataflow, data transformation, and state management needed by an application, combined with small bits of procedural code to handle complex logic. Our platform provides distributed query optimization that takes runtime conditions into account, while also supporting a range of learning, prediction, and connection-finding algorithms. In this talk I will describe our basic ASPEN prototype including cluster and sensor subsystems, and provide an overview of how we address issues of query optimization, distributed query execution, and incremental recomputation. Work done jointly with Mengmeng Liu, Svilen Mihaylov, Boon Thau Loo, and Sudipto Guha Zachary Ives is an Associate Professor and the Markowitz Faculty Fellow at the University of Pennsylvania. His research interests include data integration and sharing, "big data", sensor networks, and data provenance and authoritativeness. He is a recipient of the NSF CAREER award, and an alumnus of the DARPA Computer Science Study Panel and Information Science and Technology advisory panel. He has also been awarded the Christian R. and Mary F. Lindback Foundation Award for Distinguished Teaching. He serves as the undergraduate curriculum chair for Penn's Singh Program in Market and Social Systems Engineering. He is a co-author of the textbook Principles of Data Integration.

1 0

W Lloyd preFPO
by Melissa M. Lawson 04 Dec '12

04 Dec '12

Wyatt Lloyd will present his preFPO on Tuesday December 11 at 9AM in Room 402. The members of his committee are; Michael Freedman, advisor; Vivek Pai and David Andersen (CMU), readers; Jennifer Rexford and Margaret Martonosi, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------------ Title: Stronger Consistency and Semantics for Low-Latency Geo-Replicated Storage Abstract: Distributed data stores that support complex online applications, such as social networks, are built with a two-level architecture. Data is replicated across a small number of datacenters and within each datacenter is stored in clusters of thousands or more machines. These two levels bring different challenges for creating a scalable, responsive, and consistent data store. Our COPS system is the first distributed data store to guarantee the ALPS properties—availability, low latency, partition tolerance, and scalability—and achieve consistency stronger than eventual. Eventual consistency specifies only that writes in one datacenter eventually show up in the others. Causal consistency, which is what COPS provides, maintains the partial order over operations establish by potential causality. Under causal consistency, all of a user’s operations appear in the order they are issued and interactions between users, e.g., conversations in comments, appear in their correct order as well. This improvement in consistency gives users a better experience and makes the data store easier for programmers to reason about. The key technical contribution of the COPS work is its fully distributed and scalable architecture that uses explicit metadata and off-path dependency checks to enforce ordering instead of relying on any single point of coordination. Our Eiger system pushes on the semantics an ALPS data store can provide. Eiger provides high-performance, guaranteed low-latency read-only and write-only transactions across all the machines in a cluster. Read-only transactions allow a client to observe a consistent snapshot of an entire cluster. Write-only transactions allow clients to atomically write many values spread across many servers at a single point in time. One important use case for write-only transaction is maintaing symmetrical relationships, e.g., Alice “isAFriendOf” Bob and Bob “isAFriendOf” Alice should both appear or disappear at the same time. Eiger also improves the semantics of ALPS data stores by providing the Column-Family data model—which is used in BigTable and Cassandra, and can be used to built real applications like Facebook—instead of the key-value data model provided by COPS—which is useful mainly as an opaque cache.

1 0