January 2013 - talks - lists.cs.princeton.edu

Graham Cormode visiting
by Ariel Rabkin 30 Jan '13

30 Jan '13

Hi all. Here's another in our series of data and database talks. Talk will be on Weds Jan 30, Room 302 at noon. NOTE THAT THERE WILL NOT BE A REMINDER THE DAY-OF, BECAUSE MAILING LISTS WILL BE DOWN DUE TO MIGRATION!!! Let me know if you want to meet with the speaker; should be of interest to both theory and systems people. Talk: 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

2 1

11am Thu Feb 7 talk on flow-cut gaps and network coding
by Jennifer Rexford 21 Jan '13

21 Jan '13

Speaker: Anna Blasiak, Cornell Title: Flow-Cut Gaps and Network Coding Date/time: 11am-noon on Thursday February 7 Place: 402 in the CS building Abstract: The classic max-flow min-cut theorem states that in a network with one source and one sink, the amount of information that can be sent from the source to the sink is equal to the minimum capacity of a set of edges separating the source from the sink. This equivalence allows for efficient computation of both parameters. Modifying traffic demands, constraints, and optimization functions yields many variations of the max-flow problem. In all of these variations there is a corresponding cut minimization problem whose optimal value serves as an upper bound on the max-flow. But unlike the single source-sink version, the cut upper bound is rarely equal to the max-flow. The flow-cut gap, the worst possible ratio between the max-flow rate and the cut upper bound, is an important area of study for developing approximation algorithms and gaining a better understanding of network flow. Related to the max-flow problem is the network coding rate, the maximum transmission rate of information in networks whose nodes can perform nontrivial encoding and decoding operations on incoming messages. The network coding rate is always as big as the max-flow rate and can be much larger. A spectacular result of network coding theory is that in the multicast problem, a setting with a large flow-cut gap, the coding rate is always equal to the cut bound. This talk considers the relations between the flow rate, coding rate, and cut bounds for multicommodity flow problems. I present new coding-cut gaps, the worst-case ratio between the coding rate and cut upper bound. Further, I show that there exist paradigms apart from multicast in which coding can bridge the flow-cut gap. Specifically, in the network that provides the largest known separation (Saks et al.) between the maximum multicommodity flow and multicut, the coding rate is equal to the multicut. This is joint work with Robert Kleinberg (Cornell University) and Eyal Lubetzky (Microsoft Research Redmond).

1 0

A Blankstein general exam
by Melissa M. Lawson 17 Jan '13

17 Jan '13

Aaron Blankstein will present his research seminar/general exam on Thursday January 24 at Noon in Room 402. The members of his committee are: Michael Freedman (advisor), Ed Felten, 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. ----- Original Message ----- Abstract: In many client-facing applications, a vulnerability in any portion can compromise the entire application. In this talk, I describe the design and implementation of Passe, a web framework that provides integrity and conﬁdentiality guarantees for existing applications. Passe automatically splits (previously single-process) web applications into sandboxed processes, and then limits the types of queries each component can make to shared storage. While previous approaches like Decentralized Information Flow Control sought to provide security guarantees by explicitly labeling and tracking data, Passe provides similar guarantees by instead enforcing integrity constraints on database queries, even when they originate from compromised components. Further, rather than requiring developers to specify such constraints explicitly, Passe infers these constraints during a testing phase, in which it assumes that the “proper” execution of database queries is reading and writing data appropriately. Such policy inference allows Passe to execute unmodiﬁed applications without explicit policies. I present a prototype of Passe which acts as a drop-in replacement for the Django web framework. By running seven unmodiﬁed, off-the shelf applications in Passe, I demonstrate its ability to provide strong security guarantees with reasonable performance. Reading List "Principles of Computer System Design" - Saltzer and Kaashoek "The KeyKOS Nanokernel Architecture" A. Bomberger, A. Frantz, W. Frantz, A. Hardy, N. Hardy, C. Landau, and J. Shapiro. "Complete, Safe Information Flow with Decentralized Labels" A. Myers and B. Liskov. "Hails: Protecting data privacy in untrusted web applications." Daniel B. Giffin, Amit Levy, Deian Stefan, David Terei, David Mazières, John Mitchell, and Alejandro Russo. “The protection of information in computer systems,” J. H. Saltzer and M. D. Schroeder, "Information Flow Control for Standard OS Abstractions" (Flume) Max Krohn, Alexander Yip, Micah Brodsky, Natan Cliffer, M. Frans Kaashoek, Eddie Kohler, Robert Morris "Making information flow explicit in HiStar. " Nickolai Zeldovich, Silas Boyd-Wickizer, Eddie Kohler, and David Mazières. “Bugs as deviant behavior: a general approach to inferring errors in systems code" D. Engler, D. Y. Chen, S. Hallem, A. Chou, and B. Chelf “All you ever wanted to know about dynamic taint analysis and forward symbolic execution (but might have been afraid to ask),” E. J. Schwartz, T. Avgerinos, and D. Brumley “Building secure high-performance web services with OKWS" - Max Krohn

1 0

I Davey generals
by Melissa M. Lawson 16 Jan '13

16 Jan '13

Ian Davey will be presenting his research seminar/general exam (talk only) on Wednesday January 23 at 2PM in Sherrerd 306 (Note Location!). The members of his committee are: Ed Felten (advisor), Michael Freedman, and Zeev Dvir. Everyone is invited to attend his talk. ----- Original Message ----- Collective Security for Resistance to Mass Harvesting of Publicly-Available Information As internet users produce and share increasing amounts of content, some new privacy concerns appear. In particular, various entities who have no personal interest in any particular author will nonetheless crawl the internet and harvest any public data they can find. While users may be perfectly happy to share thoughts, photos, video, and contact information with other human users (including complete strangers), they may not wish for the data to be grabbed automatically at scale and used for targeted advertising, spam, search indexing and archiving, etc. Ultimately this becomes an instance of the key distribution problem --- while normal encryption may appear at first the obvious solution, in this case we cannot expect the author to have an existing relationship with his/her audience, and thus there is not necessarily an out-of-band channel through which to exchange key data. However, also in this case, while each member of the desired audience has a limit to the amount of content he/she wishes to view, the adversary has no such limit and wishes to scrape everything. We can exploit this property to find a solution. In this talk we formally define a notion of ``collective security,'' which allows for the recovery of individual pieces of data but provides resistance to mass harvesting of the entire corpus of content. We then propose methods which use weak symmetric ciphers and/or hyperencryption to fill this requirement and prove a theoretical upper bound on its effectiveness. We also propose a system of ``shortcuts'' in case a (possibly one-way) channel for key exchange exists between an author and a viewer. We then present experimental results, explore an economy where barriers to mass information harvesting exist, and describe a browser extension which implements some of our techniques.

1 0

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