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

A Garg general exam
by Melissa M. Lawson 30 Apr '13

30 Apr '13

Ankit Garg will present his research seminar/general exam on Monday may 6 at 2PM in Room 402. The members of his committee are: Mark Braverman (advisor), Zeev Dvir, and Moses Charikar. 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 : Communication Complexity of Small-Set Disjointness Abstract : We obtain a tight bound of $\frac{2}{\ln 2}k \pm o(k)$ on the randomized communication complexity of disjointness of sets of size $\le k$. An asymptotic bound of $\Theta(k)$ was previously shown by H{\aa}stad and Wigderson. One of the key components is the tight analysis for the zero-error information complexity of the 2-bit $AND$ function. This is obtained using a new local characterization of the zero-error information complexity function for two party communication problems. The lower bound for small-set disjointness requires an additional continuity argument for information complexity. It is trickier than disjointness, since we have to deal with very small information costs. Also the upper bound requires a nontrivial application of the ``information equals amortized communication" theorem. This is joint work with Mark Braverman, Denis Pankratov and Omri Weinstein. Reading List : Book : Computational Complexity - Sanjeev Arora and Boaz Barak Papers : 1. Information equals amortized communication - Mark Braverman, Anup Rao, FOCS 2011. 2. How to compress interactive communication - Boaz Barak, Mark Braverman, Xi Chen, Anup Rao, STOC 2010 3. Interactive information complexity - Mark Braverman, STOC 2012 4. Communication lower bounds using directional derivatives - Alexander Sherstov, ECCC 2013 5. Direct products in communication complexity - Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff, ECCC 2013. 6. Rounding Parallel Repetitions of Unique Games - Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev and David Steurer, FOCS 2008. 7. Lower bounds on information complexity via zero-communication protocols and applications - I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao. FOCS 2012. 8. Parallel Repetition in Projection Games and a Concentration Bound - Anup Rao, STOC 2008. 9. Algebrization: A New Barrier in Complexity Theory - S. Aaronson, A. Wigderson, STOC 2008. 10. On proving Super-Logarithmic Depth Lower Bounds via the Direct sum in Communication Complexity, M.Karchmer, R.Raz, A.Wigderson, Journal of Computational Complexity, 1995. 11. On ACC, R. Beigel and J. Tarui, Computational Complexity, 1994.

1 0

R Oda general exam
by Melissa M. Lawson 30 Apr '13

30 Apr '13

Reid Oda will present his research seminar/general exam on Monday May 6 at 10AM in Room 402. The members of his committee are: Rebecca Fiebrink (advisor), Adam Finkelstein, 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: The Internet allows musicians and other artists to collaborate remotely with one another. However, network latency presents a fundamental challenge for remote collaborators who need to coordinate and respond to each other's performance in real time. Latencies of more than 55 ms round-trip make it difficult for performers to synchronize with one another. Each performer slows down to keep in time with the other, causing the performance to fall apart. Researchers have optimized client software in order to reduce latency as far as possible, but the leading cause of the latency, the architecture of the Internet, is beyond the control of the user. Recently a system was developed to recognize patterns in the music being played, and to synthesize those same classes of patterns on the far end of the connection. This allows musicians to "play" in synchrony, but because of the pattern-level granularity of the synthesis algorithm, the receiver will not hear actual notes being played by the sender. I present a system which attempts note-level prediction. The system predicts percussion hits before they have occurred, so that information about the predicted drum hit can be sent over a network, and the sound can be synthesized at a receiver's location at approximately the same moment the hit occurs locally. The system uses a high-speed camera to track a percussion mallet. It uses regression and pattern matching to predict the note, timing and velocity of the percussion hit. In order to synchronize music events in real-time, it uses a modified version of Marzullo's clock synchronization algorithm. I show that it is possible to predict a percussion note within the bounds of perceptual synchrony, 30-40 ms before the event occurs. A 40 ms lead time means that two artists in Boston and New York city could potentially play together with perfect synchrony. TEXT: E. R. Miranda and M. M. Wanderley, New Digital Musical Instruments. A-R Editions, Inc., 2006. (Chapter 3) J. P. Caceres, “Synchronization Of Rhythmic Performance With Delay,” 2013. (Chapters 6 & 7) A. Greenbaum and T. P. Chartier, Numerical Methods. Princeton University Press, 2012. S. Dahl, “Striking movements: A survey of motion analysis of percussionists,” Acoust. Sci. & Tech., vol. 32, no. 5, pp. 168–173, 2011. J. P. Caceres and C. Chafe, “JackTrip: Under the hood of an engine for network audio,” Journal of New Music Research, vol. 39, no. 3, pp. 183–187, 2010. P. Oliveros, S. Weaver, M. Dresser, J. Pitcher, J. Braasch, and C. Chafe, “Telematic music: six perspectives,” Leonardo Music Journal, vol. 19, no. 1, pp. 95–96, 2009. (Chapter 3) M. Sarkar, “Tablanet: a real-time online musical collaboration system for indian percussion,” Massachusetts Institute of Technology, 2007. J. P. Lewis, “Fast template matching,” vol. 95, no. 120123, pp. 15–19, 1995. M. V. Mathews, “The radio baton and conductor program, or: Pitch, the most important and least expressive part of music,” Computer Music Journal, pp. 37–46, 1991. K. Marzullo and S. Owicki, “Maintaining the time in a distributed system,” pp. 295–305, 1983. V. Cerf and R. Kahn, “A Protocol for Packet Network Intercommunication,” Communications, IEEE Transactions on, vol. 22, no. 5, pp. 637–648, 1974.

1 0

Seminar speaker tomorrow: Prof. Josep Torrellas, UIUC
by Margaret Martonosi 30 Apr '13

30 Apr '13

Hello all-- A final reminder: Prof. Josep Torrellas from UIUC will be visiting Princeton and giving a seminar on Tuesday April 30. The seminar will be from 12:30-1:30 in CS Room 302, with pizza beforehand starting at noon. Title/abstract below. I have reserved a 1-hour slot for him to meet with grad students from 2:30-3:30pm that day. That will occur in CS room 401. Any interested grad students can feel free to just show up for that. Thanks, Margaret ----------------------------------------------------------------- Toward Programmable High-Performance Multicores Josep Torrellas University of Illinois, Urbana-Champaign http://iacoma.cs.uiuc.edu/~torrellas One of the biggest challenges facing us today is how to design parallel architectures that attain high performance while efficiently supporting a programmable environment. In this talk, I describe novel organizations that will make the next generation of multicores more programmable and higher performance. Specifically, I show how to automatically reuse the upcoming transactional memory hardware for optimized code generation. Next, I describe a prototype of Record&Replay hardware that brings program monitoring for debugging and security to the next level of capability. I also describe a new design of hardware fences that is overhead-free and requires no software support. Finally, if time permits, I will outline architectural support to detect sequential consistency violations transparently. BIO: Josep Torrellas is a Professor of Computer Science and Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign (UIUC). He is a Fellow of IEEE and ACM. He is the Director of the Center for Programmable Extreme-Scale Computing, a center funded by DARPA, DOE, and NSF that focuses on architectures for extreme energy and power efficiency. He also directs the Intel-Illinois Parallelism Center (I2PC), a center created by Intel to advance parallel computing in clients. He has made contributions to parallel computer architecture in the areas of shared-memory multiprocessor organizations, cache hierarchies and coherence protocols, thread-level speculation, and hardware and software reliability. He received a Ph.D. from Stanford University. ------------------------------------------------------------ Margaret Martonosi Hugh Trumbull Adams '35 Professor of Computer Science Princeton University http://www.princeton.edu/~mrm mrm(a)princeton.edu

2 1

N Kang general exam
by Melissa M. Lawson 26 Apr '13

26 Apr '13

Nanxi Kang will present her research seminar/general exam on Friday May 3 at Noon in Room 301 (note room!). The members of her committee are: Jennifer Rexford (advisor), David Walker, and Vivek Pai. 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. ----- Original Message ----- Abstract Software Defined Networking (SDN) supports diverse network policies by offering direct, network-wide control over how the switches handle traffic. However, today’s controller platforms force applications to grapple with the space limits on each switch and the interaction between the packet-handling rules at different hops in a path. Instead, we believe SDN applications should specify high-level policies, and rely on the controller to generate the rules for each switch. A high-level policy defines the handling of traffic on a single abstract switch (indicating how packets should be modified, and dropped or forwarded to egress ports), as well as the routing of traffic across the “switching fabric.” Transforming the high-level policy into an equivalent set of switch-level rules is computationally difficult, since the policy may route traffic on arbitrary paths and match traffic on multiple dimensions of packet-header fields. We present a family of efficient rule-placement algorithms, starting with the simple case of policies matching one packet-header field along a chain, and building up to the general case which involves arbitrary routing, multi-dimensional patterns and the need to enable dynamic, incremental update of policies. Our experiments with synthetic benchmarks, and real firewall and routing policies, demonstrate that our algorithms can support realistic policies using the small rule tables available in commodity switches. ---------------------------------- Reading List [1] L. L. Peterson and B. S. Davie, Computer networks: a systems approach. Morgan Kaufmann, 2007. [2] J. H. Saltzer, D. P. Reed, and D. D. Clark, “End-to-end arguments in system design,” ACM Transactions on Computer Systems (TOCS), vol. 2, no. 4, 1984. [3] M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. Gude, N. McKeown, and S. Shenker, “Rethinking enterprise network control,” IEEE/ACM Trans. Networking, vol. 17, August 2009. [4] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling innovation in campus networks,” SIGCOMM Computer Communications Review, vol. 38, no. 2, 2008. [5]C. Monsanto, J. Reich, N. Foster, J. Rexford, and D. Walker, "Composing software dened networks," in NSDI, Apr 2013. [6] M. Yu, J. Rexford, M. J. Freedman, and J. Wang, "Scalable ﬂow-based networking with DIFANE," In ACM SIGCOMM, pp. 351-362, Sep 2010. [7] M. Moshref, M. Yu, A. Sharma, and R. Govindan, "VCRIB: Virtualized rule management in the cloud," in NSDI, Apr 2013. [8] Y. Kanizo, D. Hay, and I. Keslassy, "Palette: Distributing tables in software-dened networks," in IEEE INFOCOM Mini-conference, Apr 2013. [9] C. R. Meiners, A. X. Liu, and E. Torng, "TCAM Razor: A systematic approach towards minimizing packet classiers in TCAMs," IEEE/ACM Trans. Netw., vol. 18, pp. 490-500, Apr 2010. [10] P. Gupta and N. McKeown, "Packet classication on multiple fields," in ACM SIGCOMM, pp. 147-160, 1999. [11] S. Singh, F. Baboescu, G. Varghese, and J. Wang, "Packet classication using multidimensional cutting," in ACM SIGCOMM, pp. 213-224, 2003. [12] Y. Ma and S. Banerjee, "A smart pre-classier to reduce power consumption of tcams for multi-dimensional packet classication," in ACM SIGCOMM, pp. 335-346, Aug 2012.

1 0

Siyu Liu MSE thesis talk
by Melissa M. Lawson 26 Apr '13

26 Apr '13

Siyu Liu will present his MSE thesis talk on Friday May 3 at 3PM in Room 301 (note room!). The members of his committee are: Szymon Rusinkiewicz, advisor and Tom Funkhouser, reader. Everyone is invited to attend his talk. His abstract follows below. ------------------- Localization Using Feature Matching in Near-Random Textures Precise vehicle localization, whether performed via visual scene registration or specialized sensors such as GPS, is currently limited in robustness and accuracy. We propose a computer vision-based localization system that improves precision by matching features in small patches of asphalt or carpet imaged with a downward-facing camera. The key insight is that such images will have enough near-random detail to retrieve their correct positions in the original environment. In our system, the environment is first processed to construct a knowledge base. Then during the retrieval phase, we apply multilevel search to precisely localize the observed patch in the known environment. We adjust the patch registration algorithms previously developed for natural scenes to focus on ground environments with near-random textures. Our system is marker-free and robust against orientation as well as illumination changes. By combining temporal coherence with classification techniques, we can instantaneously provide accurate localization predictions. We also envision potential applications in navigation systems and precise control for 3D fabrication.

1 0

Diego Perez Botero MSE thesis talk
by Melissa M. Lawson 26 Apr '13

26 Apr '13

Diego Perez Botero will present his MSE thesis talk on Friday May 3 at 2PM in Room 301 (note room!). The members of his committee are: Ruby Lee (ELE), advisor and Jennifer Rexford, reader. Everyone is invited to attend his talk. His abstract follows below. ---------------------- TITLE Pwnetizer: Improving Availability in Cloud Computing through Fast Cloning and I/O Randomization ABSTRACT The rise of the Cloud Computing paradigm has led to security concerns amongst its adopters, given that resources are shared and mediated by a Hypervisor which may be targeted by rogue guest Virtual Machines (VMs) and remote attackers. We conducted a thorough analysis of the codebase of two popular open-source Hypervisors, Xen and KVM, followed by an extensive study of the vulnerability reports associated with them. Based on our findings, we propose a practical characterization of Hypervisor vulnerabilities. From this analysis, we see that more than one third of all attacks are due to device emulation and that availability breaches are by far the most common security breaches, considering the cornerstone security properties of Confidentiality, Integrity and Availability. We developed Pwnetizer, a novel VM cloning strategy, to address these weaknesses of virtualized environments. Pwnetizer facilitates increased availability by rapidly generating clone VMs that can instantly contribute to the overall throughput of a Cloud Customer's applications, as they increase the resources available to it (network bandwidth, CPU and RAM). Previously, VM Cloning research has prioritized the performance of computationally-intensive workloads by enabling the creation of transient clone VMs that depend on a master VM. Meanwhile, the few alternatives able to generate fully-independent stateful VM Clones suffer from considerable downtimes (tens of seconds), which is itself a loss of availability. A KVM-based prototype of our Pwnetizer solution is able to gracefully generate on-demand independent VM Clones with sub-second downtimes. At minimal additional overhead, our cloning technology also randomizes the device drivers employed by each clone VM. This takes advantage of the variety of device drivers with overlapping functionality supported by commodity Hypervisors. Without having to vet them beforehand, we defend a set of diversified clone VMs against current and future attacks on device drivers with security vulnerabilities. This further improves availability by preventing large-scale VM crashes caused by attacks made possible by device emulation bugs.

1 0

Dushyant Arora MSE thesis talk
by Melissa M. Lawson 26 Apr '13

26 Apr '13

Dushyant Arora will present his MSE thesis talk on Friday May 3 at 11:30 AM in Room 302 (note room!). The members of his committee are; Jennifer Rexford, advisor and Michael Freedman, reader. Everyone is invited to attend his talk. His abstract follows below. ------------------- PARIS: ProActive Routing in Scalable Data Centers Modern data centers must meet many challenges and expectations: (a) They must scale to a large number of servers, while offering high bisection bandwidth and flexible placement of virtual machines. (b) They must allow tenants to specify network policies and realize it by forwarding traffic through desired sequences of middleboxes. (c) They must allow tenants to bring their own IP address space to the cloud to ease transition of enterprise applications and middlebox configuration. The traditional approach of connecting layer-two pods through a layer-three core constrains VM placement. More recent "flat" designs are more flexible, but have scalability limitations due to flooding/broadcasting or querying directories of VM locations. Rather than reactively learn VM locations, our PARIS architecture has a controller that pre-positions IP forwarding entries in the switches. Switches within a pod have complete information about the VMs beneath them, while each core switch maintains complete forwarding state for part of the address space. PARIS offers network designers the flexibility to choose a topology that meets their latency and bandwidth requirements. PARIS also allows tenants to bring their own IP address space and utilizes lightweight virtualization using Linux containers to offer middlebox service in a manner that truly reflects the pay-as-you go model of cloud computing. It utilizes MPLS label forwarding and aggregation in the network core and uses source routing at the network edge to realize middlebox policies specified by tenants. Finally, we evaluate our prototype implementation built using Openflow-compliant switches and NOX controller.

1 0

S Sen FPO
by Melissa M. Lawson 26 Apr '13

26 Apr '13

Siddhartha Sen will present his FPO on Wednesday May 1 at 1PM in Room 401 (note room!). The members of his committee are: Bob Tarjan and Michael Freedman, co-advisors; Michael Freedman and Jennifer Rexford readers; Vivek Pai and Bob Sedgewick, nonreaders. A copy of his thesis, "New Systems and Algorithms for Scalable Fault Tolerance", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Nayden Nedev MSE thesis talk
by Melissa M. Lawson 25 Apr '13

25 Apr '13

Nayden Nedev will present his MSE thesis talk on Thursday May 2 at 1PM in Room 401 (note room!). The members of his committee are: David Walker, advisor, and Jennifer Rexford, reader. Everyone is invited to attend his talk. His abstract follows below. ------------------------------------------------- Title: Parallel Consistent Network Updates Abstract: Network configuration changes are a frequent operation performed by network administrators. Unfortunately, these changes can result in a wide range of problems such as network outages, security vulnerabilities or worse overall network performance. A recent result in this area proposes the notion of consistent network update - an update that preserves certain properties when updating from one network policy to another. The authors of the mentioned work describe a per-packet consistent update algorithm that guarantees that every packet in the network traverses either the old policy or the new one but not some mixture of the two. With the advent of software-defined networking, development of centralized, tightly-coordinated applications with strong global correctness properties has been made possible. However, it is an open problem how to bring more parallelism to these applications and how to leverage general-purpose multicore and multiprocessor machines to improve their performance. In this work, we propose two parallelized versions of the per-packet consistency update mechanism. We implement them on top of Floodlight - a new multi-threaded software-defined networking controller platform. We evaluate their performance on two example applications - a network-wide host location learning and a shortest-path routing application. ----- Original Message -----

1 0

B Kapicioglu FPO
by Melissa M. Lawson 25 Apr '13

25 Apr '13

Berk Kapicioglu will present his FPO on Thursday May 2 at 1:30PM in Room 402. The members of his committee are: Rob Schapire, advisor; David Blei and Tony Jebara (Columbia), readers; Jennifer Rexford and Andrea LaPaugh, nonreaders. A copy of his thesis, "Applications of Machine Learning to Location Data", is on display in Room 310. Everyone is invited to attend his talk.

1 0