May 2015 - talks - lists.cs.princeton.edu

Thiago Pereira will present his FPO on Wednesday, 5/13/2015 at 4pm in CS 401
by Nicki Gotsis 05 May '15

05 May '15

Thiago Pereira will present his FPO, "New methods for the computational fabrication of appearance" on Wednesday, 5/13/2015 at 4pm in CS 401. The members of his committee are: Szymon Rusinkiewicz (adviser), readers: Tom Funkhouser and Wojciech Matusik (MIT); examiners: Szymon Rusinkiewicz, Adam Finkelstein, Jianxiong Xiao. A copy of his thesis, is available in Room 310. Everyone is invited to attend his talk.

1 0

Amy Tai will present her Generals on May 12, 2015 at 2pm in CS 301.
by Nicki Gotsis 04 May '15

04 May '15

Amy Tai will present her Generals on May 12, 2015 at 2pm in CS 301. Committee Members: Mike Freedman (adviser), Kai Li, and Andrea LaPaugh. 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. abstract: Tango is a framework that allows clients to use distributed data structures without worrying about the underlying implementation. Tango achieves this through an underlying distributed log, called Corfu. Corfu currently has a bottleneck in the single sequencer that all requests must go through in order to write to the log. To overcome this bottleneck, we propose modifying Corfu to employ multiple sequencers. We show that in order to preserve Corfu's linearizability guarantee, the system on average only achieves a fractional additional throughput with each additional sequencer. Due to this result, we shift our analysis to the Tango layer of abstraction; we prove that the transactions in Tango with multiple sequencers still achieve strict serializability. We implement multiple sequencers in Tango and show that performance can increase almost linearly with additional sequencers, up to 3, as long as the read fraction of the workload is low. As expected, multiple sequencers have similar throughput to a single sequencer when all transactions contain reads. reading list: | 1. BALAKRISHNAN, M., MALKHI, D., WOBBER, T., WU, M., PRABHAKARAN, V., | WEI, M., DAVIS, J. D., RAO, S., ZOU, T., AND ZUCK, A. 2013. Tango: | Distributed data structures over a shared log. In Proceedings of the | ACM Symposium on Operating Systems Principles (SOSP). ACM, New York. | 2. Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted | Wobber, Michael Wei, and John Davis, CORFU: A Shared Log Design for | Flash Clusters , in 9th USENIX Symposium on Networked Systems Design | and Implementation (NSDI '12) , USENIX, April 2012. | 3. Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., | Spreitzer, M. J., and Hauser, C. H. 1995. Managing update conflicts | in Bayou, a weakly connected replicated storage system. In | Proceedings of the Fifteenth ACM Symposium on Operating Systems | Principles. ACM Press, New York, NY. | 4. B. Liskov and J. Cowling. Viewstamped replication revisited. | Technical report, MIT CSAIL, Cambridge, MA, 2012. | 5. ONGARO, D., AND OUSTERHOUT, J. In Search of an Understandable | Consensus Algorithm. In Proc. ATC’14, USENIX Annual Technical | Conference (2014), USENIX | 6. J. Terrace and M. J. Freedman. Object storage on CRAQ: | High-throughput chain replication for read-mostly workloads. In | Proc. USENIX Annual Technical Conference, June 2009. | 7. Tanenbaum, Andrew S., Van Steen, Maarten. Distributed Systems: | Principles and Paradigms. Prentice Hall, 2nd Ed. 2006. | 8. Thomson, A., Diamond, T., Shu-Chun Weng, T. D., Ren, K., Shao, P., | and Abadi, D. J. 2012. Calvin: Fast distributed transactions for | partitioned database systems. In Proceedings of the ACM SIGMOD | International Conference on Management of Data. | 9. SCHNEIDER, F. B. 1990. Implementing fault tolerant services using | the state machine approach: A tutorial. ACM Computing Surveys 22, 4 | (Dec.), 299–319. | 10. BERNSTEIN, P. A., SHIPMAN, D. W., AND WONO, W.S. "Formal Aspects | of Senalizability in Database Concurrency Control," IEEE Trans. | Softw Eng. SE-5, 3 (May 1979) 203-215.

1 0

Cole Schlesinger will present his FPO on Friday, May 15, 2015 at 10am in CS 302
by Nicki Gotsis 04 May '15

04 May '15

Cole Schlesinger will present his FPO "Abstractions for Software-defined Networks" on Friday, May 15 at 10am in CS 302. The members of his committee are David Walker (adviser), readers: Aarti Gupta and Arjun Guha (University of Massachusetts Amherst), nonreaders: Jen Rexford, Nick Feamster, and David Walker. A copy of his/her thesis, is available in Room 310. Everyone is invited to attend his talk.

1 0

Caroline Trippel will present her Generals on May 12, 2015 at 10am in CS 301
by Nicki Gotsis 04 May '15

04 May '15

Caroline Trippel will present her Generals on May 12, 2015 at 10am in CS 301. The members of her committee are Margaret Martonosi (adviser), Andrew Appel, and David August. 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. Title: Accurate and Precise Translation and Compilation in the Face of Varying Memory Consistency Models Abstract Architecture-level heterogeneity is increasing: numerous products and studies have proven the benefits of combining cores and accelerators with varying ISAs into a single system. However, an underappreciated barrier to unlocking heterogeneity’s full potential is that the wide range of memory consistency models (MCMs) make it difficult to reason about differences in MCMs, and this in turn raises challenges in verifying or translating between them. My talk will discuss ArMOR (Architecture-independent Memory Ordering Requirements), a framework for specifying, comparing, and translating between MCMs. As a concrete example using this framework, my work aims to enable translation between MCMs without dramatically modifying hardware or recompiling code. I have used the Pin dynamic binary translation (DBT) infrastructure to create tools that enable code expecting “strong” hardware to be migrated to “weaker” hardware. My work has also explored workload characteristics that affect the performance overhead of this operation. Furthermore, I have looked at static translation from “weak” MCMs to “strong” MCMs, specifically studying late-stage translation of Android applications to x86 hardware. Reading List 1. Hans-J. Boehm and Sarita V. Adve. 2008. Foundations of the C++ concurrency memory model. In Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation (PLDI '08). ACM, New York, NY, USA, 68-78. DOI=10.1145/1375581.1375591 http://doi.acm.org/10.1145/1375581.1375591 2. Matthew DeVuyst, Ashish Venkat, and Dean M. Tullsen. 2012. Execution migration in a heterogeneous-ISA chip multiprocessor. In Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS XVII). ACM, New York, NY, USA, 261-272. DOI=10.1145/2150976.2151004 http://doi.acm.org/10.1145/2150976.2151004 3. John L. Hennessy and David A. Patterson. 2003. Computer Architecture: A Quantitative Approach(3 ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. 4. L. Lamport. 1979. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Trans. Comput. 28, 9 (September 1979), 690-691. DOI=10.1109/TC.1979.1675439 http://dx.doi.org/10.1109/TC.1979.1675439 5. Daniel Lustig, Michael Pellauer, and Margaret Martonosi, “PipeCheck: Specifying and Verifying Microarchitectural Enforcement of Memory Consistency Models”, 47th International Symposium on Microarchitecture (MICRO), Cambridge, UK, December 2014. 6. Daniel Lustig, Caroline Trippel, Michael Pellauer, and Margaret Martonosi. 2015. ArMOR: Defending Against Memory Consistency Model Mismatches in Heterogeneous Architectures. In Proceedings of the 42nd Annual International Symposium on Computer Architecture (ISCA '15). Portland, OR, June 2015. 7. Abhayendra Singh, Satish Narayanasamy, Daniel Marino, Todd Millstein, and Madanlal Musuvathi. 2012. End-to-end sequential consistency. In Proceedings of the 39th Annual International Symposium on Computer Architecture (ISCA '12). IEEE Computer Society, Washington, DC, USA, 524-535. 8. Daniel J. Sorin, Mark D. Hill, and David A. Wood. 2011. A Primer on Memory Consistency and Cache Coherence (1st ed.). Morgan & Claypool Publishers. 9. Ashish Venkat and Dean M. Tullsen. 2014. Harnessing ISA diversity: design of a heterogeneous-ISA chip multiprocessor. In Proceeding of the 41st annual international symposium on Computer architecuture (ISCA '14). IEEE Press, Piscataway, NJ, USA, 121-132.

1 0

Steven Englehardt will present his Generals on May 11, 2015 at 2pm in CS 301
by Nicki Gotsis 04 May '15

04 May '15

Steven Englehardt will present his Generals on May 11, 2015 at 2pm in CS 301. Committee Members: Arvind Narayanan (adviser), Edward Felten, and Nick Feamster 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: Web tracking has been a longstanding issue undermining consumer privacy. The proliferation of a mixed-origin websites, where nearly every site includes third-party content from a relatively small set of providers has given these providers the ability to observe and track a large percentage of a user’s web history. Web measurement has been highly influential in online privacy debates and provided transparency into the tracking ecosystem. In this work, we briefly present the design of a platform for web measurement studies and explore a measurement of surveillance completed using the platform. We highlight the ability of a passive eavesdropper to leverage third-party cookies for mass surveillance, showing how such an adversary can reconstruct nearly 75% of a user’s browsing history in the absence of persistent network identifiers. Finally, we examine the effectiveness of browser-based privacy tools at mitigating the attack. Books: The Tangled Web: A Guide to Securing Modern Web Applications, Michal Zalewski Security Engineering, Ross Andersen: Ch. 1 - 7 Papers: > Third-party web tracking: Policy and technology Jonathan Mayer, John C. Mitchell > > Privacy diffusion on the web: a longitudinal perspective Balachander Krishnamurthy, Craig E. Wills > > Privacy leakage vs. protection measures: the growing disconnect Balachander Krishnamurthy, Konstantin Naryshkin, Craig E. Wills > > Detecting and defending against third-party tracking on the web Franziska Roesner, Tadayoshi Kohno, and David Wetherall > > FPDetective: dusting the web for fingerprinters Gunes Acar, et.al . > > Tracking the trackers: Fast and scalable dynamic analysis of web content for privacy violations Minh Tran, et. al. > > Automated Experiments on Ad Privacy Settings: A Tale of Opacity, Choice, and Discrimination Amit Datta, Michael Carl Tschantz, Anupam Datta > > XRay: Enhancing the Web’s Transparency with Differential Correlation Mathias Lecuyer, et. al. > > Why Johnny Can’t Browse in Peace: On the Uniqueness of Web Browsing History Patterns Lukasz Olejnik > > A Contextual Approach to Privacy Online Helen Nissenbaum > > What Can Behavioral Economics Teach Us About Privacy? Alessandro Acquisti, Jens Grossklags > > Privacy, Economics, and Price Discrimination on the Internet Andrew Odlyzko > > Protecting Consumer Privacy in an Era of Rapid Change FTC (executive summary / recommendations)

1 0

Raghav Sethi will present his masters thesis talk on Friday, May 8, 2015 at 1pm in CS 302
by Nicki Gotsis 01 May '15

01 May '15

Raghav Sethi will present his masters thesis talk on Friday, May 8, 2015 at 1pm in CS 302. His readers are Michael Freedman (adviser) and Jennifer Rexford. Everyone is invited to attend his talk. His abstract follows below. Title: Exoskeleton: Fast Cache-enabled Load Balancing for Key-Value Stores Abstract: Key-value stores are a fundamental building block for many large web-scale applications. These applications typically generate highly-skewed traffic, i.e. the most popular keys are requested many orders of magnitude more frequently than the least popular keys. Schemes that simply balance storage capacity across a cluster are therefore unable to adequately balance traffic load across cluster nodes. Dynamic load-balancing is therefore often necessary, but if it is imperfect or slow, operators must still over-provision individual nodes to be able to deal with rapidly-changing traffic distributions, increasing equipment and operational costs. An effective technique to provide load-balancing is to use popularity based caching. Exoskeleton is a cache architecture which enables the routing of requests for popular keys directly to cache nodes at line-rate. This architecture leverages the power and speed of programmable switches to perform content-aware routing. Clients do not need to maintain any state to take advantage of this architecture, and simply encode key information directly into request packet headers. Exoskeleton removes the constraints of previous architectures, which required operators to optimize for either low latency or scalability, but not both. In addition, Exoskeleton deals with rapidly-changing workloads through a cache update mechanism designed specifically for the limitations imposed by switch hardware. Effective load-balancing enables this system to efficiently deal with modern web workloads using a heterogeneous cluster architecture comprising cheap SSD-based backend nodes and a small number of powerful cache nodes.

1 0

Jieming Mao will present his Generals on May 8, 2015 at 1:30pm in CS 401
by Nicki Gotsis 01 May '15

01 May '15

Jieming Mao will present his Generals on May 8, 2015 at 1:30pm in CS 401 The members of his committee are: Mark Braverman(adviser), Sanjeev Arora, and Zeev Dvir. 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: In this talk, I will focus on presenting the paper "Simulating Noisy Channel Interaction". This is joint work with Mark Braverman. In the paper, we show that T rounds of interaction over the binary symmetric channel BSC 1 / 2 − ε with feedback can be simulated with O(ε 2 T) rounds of interaction over a noiseless channel. We also introduce a more general “energy cost” model of interaction over a noisy channel. We show energy cost to be equivalent to external information complexity, which implies that our simulation results are unlikely to carry over to energy complexity. Our main technical innovation is a self-reduction from simulating a noisy channel to simulating a slightly-less-noisy channel, which may have other applications in the area of interactive compression. Reading list: Books: Arora and Barak, Computational Complexity- A Modern Approach [Chapters 1-16] Kushilevitz and Nisan, Communication Complexity Papers: 1: Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 67–76, 2010. 2: Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. In Proceedings of the 43rd annual ACM symposium on Theory of computing, pages 159–166. ACM, 2011. 3: Mark Braverman and Anup Rao. Information equals amortized communication. In Rafail Ostrovsky, editor, FOCS, pages 748–757. IEEE, 2011. 4: Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. From information to exact communication. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 151–160. ACM, 2013. 5: Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 160–166. IEEE, 2012. 6: Mark Braverman. A hard-to-compress interactive task? In 51st annual Allerton Conference on Communication, Control, and Computing, 2013. 7: Mark Braverman and Klim Efremenko. List and unique coding for interactive communication in the presence of adversarial noise. In Electronic Colloquium on Computational Complexity (ECCC), volume 21, page 7, 2014. 8: Information lower bounds via self-reducibility Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein CSR'13 9: Interactive information complexity Mark Braverman STOC'12; 10: Direct products in communication complexity Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff FOCS'13;

1 0