- talks - lists.cs.princeton.edu

Tobechukwu Nwanna MSE thesis talk
by Melissa M. Lawson 01 May '13

01 May '13

Tobechukwu Nwanna will present his MSE thesis talk on Monday May 6 at 1PM in Room 402. The members of his committee are: Szymon Rusinkiewicz, advisor and Margaret Martonosi, reader. Everyone is invited to attend his talk. His abstract follows below. -------------------- Real time three dimensional motion sensing using sensor fusion on smartphones The need for users to explore three dimensional spaces is becoming increasingly common. Currently most input devices for interfacing with these environments try to map two dimensional movement to a three dimensional space. This means that to fully explore the environment, either mode switching or other combinations of inputs are required. While this works, it is unintuitive and unnatural. There have been a number of natural user interfaces that provide more intuitive controls through a wide variety of methods including inertial navigation and visual odometry. Inertial navigation tracks the relative position and orientation of an object with dead reckoning, using the objects' internal motion sensors. Visual odometry, on the other hand, tracks the optical flow of features identified using a camera and attempts to estimate the camera pose and movement from that. While each method has its advantages, each also has weaknesses that usually require the use of an external sensor for correction. We propose a solution that does not require an external sensor and instead uses each method to correct for errors in the other. We chose smartphones as a medium as they are sensor rich devices and ubiquitous enough to most users are comfortable using them. Our method tracks the orientation of the device using internal motion sensors while tracking the linear motion using camera data. Both types of input are placed into a kalman filter that attempts to minimize the effects of noise and reduce the accumulation of errors in each using data from the other. In addition to explaining the system, we will detail some potential uses and how this interface improves over existing ones.

1 0

Profiling big data systems at google- Talk today at 3:30pm
by Nicole E. Wagenblast 01 May '13

01 May '13

Profiling Latency in Deployed Distributed Systems Gideon Mann , Google Wednesday, May 1, 2013, 3:30pm Computer Science 105 Understanding the sources of latency within a deployed distributed system is complicated. Asynchronous control flow, variable workloads, pushes of new backend servers, and unreliable hardware all can make significant contribution to a job's performance. In this talk, I'll present the work of the Weatherman effort to build a profiling tool for deployed distributed systems. The method uses distributed traces to estimate the code control flow and predict/explain observed performance. I'll then illustrate how this method has been applied to understand and tune large distributed systems at Google and how it has been used in a differential profiling fashion to understand the sources of latency changes. To provide another view of latency, I'll quickly discuss our recent work on distributed convex optimization with an emphasis on the interface between the algorithm and the computing substrate performing the computation. In particular, I'll show that data center architecture, in particular network architecture, should have a significant impact on machine learning algorithm design. Gideon is a Staff Research Scientist at Google NY. He attended Brown University as an undergraduate where he hung out in the AI lab and drank too much Mountain Dew. He then attended graduate school at Johns Hopkins University, worked in CLSP, and graduated in 2006 with a Ph.D. He still misses Charm City. He then spent a post-doc at the UMass/Amherst with Andrew McCallum working on weakly-supervised learning. In 2007, he joined Google. At Google, his team works on applied machine learning. The Weatherman effort leverages statistical methods to data center management. The team also is responsible for the Prediction API (https://developers.google.com/prediction/). Publicly released in 2010, Prediction was an early machine learning as a service offering and remains an ongoing research project.

1 1

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