- talks - lists.cs.princeton.edu

CS Colloquium Speaker: Sarah Dean, Monday, March 29 at 4:30
by Emily C. Lawrence 23 Mar '21

23 Mar '21

CS Colloquium Speaker Sarah Dean, University of California, Berkeley Host: Elad Hazan Date: Monday, March 29 Time: 4:30pm EST Event page: [ https://www.cs.princeton.edu/events/26052 | https://www.cs.princeton.edu/events/26052 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_tGTox7xySEK97iKWXtIOSg | https://princeton.zoom.us/webinar/register/WN_tGTox7xySEK97iKWXtIOSg ] Title: Reliable Machine Learning in Feedback Systems Abstract: Machine learning techniques have been successful for processing complex information, and thus they have the potential to play an important role in data-driven decision-making and control. However, ensuring the reliability of these methods in feedback systems remains a challenge, since classic statistical and algorithmic guarantees do not always hold. In this talk, I will provide rigorous guarantees of safety and discovery in dynamical settings relevant to robotics and recommendation systems. I take a perspective based on reachability, to specify which parts of the state space the system avoids (safety) or can be driven to (discovery). For data-driven control, we show finite-sample performance and safety guarantees which highlight relevant properties of the system to be controlled. For recommendation systems, we introduce a novel metric of discovery and show that it can be efficiently computed. In closing, I discuss how the reachability perspective can be used to design social-digital systems with a variety of important values in mind. Bio: Sarah is a PhD candidate in the Department of Electrical Engineering and Computer Science at UC Berkeley, advised by Ben Recht. She received her MS in EECS from Berkeley and BSE in Electrical Engineering and Math from the University of Pennsylvania. Sarah is interested in the interplay between optimization, machine learning, and dynamics in real-world systems. Her research focuses on developing principled data-driven methods for control and decision-making, inspired by applications in robotics, recommendation systems, and developmental economics. She is a co-founder of a transdisciplinary student group, Graduates for Engaged and Extended Scholarship in computing and Engineering, and the recipient of a Berkeley Fellowship and a NSF Graduate Research Fellowship.

1 0

Khiem Ngo will present his Pre-FPO "Tolerating Slowdowns in Replicated State Machines using Copilots" on Tuesday, March 23, 2021 at 3pm via Zoom.
by Nicki Mahler 22 Mar '21

22 Mar '21

Khiem Ngo will present his Pre-FPO "Tolerating Slowdowns in Replicated State Machines using Copilots" on Tuesday, March 23, 2021 at 3pm via Zoom. Zoom link: [ https://princeton.zoom.us/j/98688513083 | https://princeton.zoom.us/j/98688513083 ] Committee Members: Wyatt Lloyd (Advisor) Michael Freedman (Examiner) Ravi Netravali (Examiner) Amit Levy (Reader) Siddhartha Sen (MSR, Reader) All are welcome to attend. Title: Tolerating Slowdowns in Replicated State Machines using Copilots Abstract. Replicated state machines (RSMs) are linearizable, fault-tolerant groups of replicas coordinated by a consensus algorithm. Linearizability gives the RSM the illusion of being a single machine that responds to client commands one by one. Fault-tolerance enables the RSM to continue operating despite the failure of a minority of replicas. RSMs are used throughout large-scale systems, such as distributed databases, cloud storage, and service managers. At such scale, it is common for some machines to be slow. The slowdowns manifest as machines whose latency for responding to other machines is higher than usual. Thus, RSMs should also be slowdown-tolerant, i.e., provide similar performance despite the presence of slow replicas. Unfortunately, no existing consensus protocol is slowdown-tolerant: a single slow replica can sharply increase their latency. This increased latency decreases availability because a service that does not respond in time is not meaningfully available. In this talk, I will first define s-slowdown-tolerance and explain why existing consensus protocols are not slowdown-tolerant. Then I will introduce Copilot replication, the first 1-slowdown-tolerant consensus protocol. Copilot replication uses two pilots to ensure the RSM stays fast, by using proactive redundancy in all stages of processing a client command. Our evaluation shows that Copilot delivers normal latency despite the slowdown of any 1 replica.

1 0

CS Colloquium Speaker: Riad Wahby, today at 12:30pm
by Emily C. Lawrence 22 Mar '21

22 Mar '21

CS Colloquium Speaker Riad Wahby, Stanford University Host: Andrew Appel Date: Monday, March 22 Time: 12:30pm EST Event page: [ https://www.cs.princeton.edu/events/26050 | https://www.cs.princeton.edu/events/26050 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_SMKdFMoQRo2Cj3zvU57zyw | https://princeton.zoom.us/webinar/register/WN_SMKdFMoQRo2Cj3zvU57zyw ] Title: Probabilistic Proofs: Theory, Hardware, and Everything in Between Abstract: In the past decade, systems that use probabilistic proofs in real-world applications have seen explosive growth. These systems build upon some of the crown jewels of theoretical computer science---interactive proofs, probabilistically checkable proofs, and zero-knowledge proofs---to solve problems of trust and privacy in a wide range of settings. This talk describes my work building systems that answer questions ranging from "how can we build trustworthy hardware that uses untrusted components?" to "how can we reduce the cost of verifying smart contract execution in blockchains?" Along the way, I will discuss the pervasive challenges of efficiency, expressiveness, and scalability in this research area; my approach to addressing these challenges; and future directions that promise to bring this exciting technology to bear on an even wider range of applications. Bio: Riad S. Wahby is a Ph.D. candidate at Stanford, advised by Dan Boneh and Keith Winstein. His research interests include systems, computer security, and applied cryptography. Prior to attending Stanford, Riad spent ten years as an analog and mixed-signal integrated circuit designer. Riad and his collaborators received a 2016 IEEE Security and Privacy Distinguished Student Paper award; his work on hashing to elliptic curves is being standardized by the IETF.

1 0

Reminder: Riad Wahby, tomorrow at 12:30
by Emily C. Lawrence 21 Mar '21

21 Mar '21

CS Colloquium Speaker Riad Wahby, Stanford University Host: Andrew Appel Date: Monday, March 22 Time: 12:30pm EST Event page: [ https://www.cs.princeton.edu/events/26050 | https://www.cs.princeton.edu/events/26050 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_SMKdFMoQRo2Cj3zvU57zyw | https://princeton.zoom.us/webinar/register/WN_SMKdFMoQRo2Cj3zvU57zyw ] Title: Probabilistic Proofs: Theory, Hardware, and Everything in Between Abstract: In the past decade, systems that use probabilistic proofs in real-world applications have seen explosive growth. These systems build upon some of the crown jewels of theoretical computer science---interactive proofs, probabilistically checkable proofs, and zero-knowledge proofs---to solve problems of trust and privacy in a wide range of settings. This talk describes my work building systems that answer questions ranging from "how can we build trustworthy hardware that uses untrusted components?" to "how can we reduce the cost of verifying smart contract execution in blockchains?" Along the way, I will discuss the pervasive challenges of efficiency, expressiveness, and scalability in this research area; my approach to addressing these challenges; and future directions that promise to bring this exciting technology to bear on an even wider range of applications. Bio: Riad S. Wahby is a Ph.D. candidate at Stanford, advised by Dan Boneh and Keith Winstein. His research interests include systems, computer security, and applied cryptography. Prior to attending Stanford, Riad spent ten years as an analog and mixed-signal integrated circuit designer. Riad and his collaborators received a 2016 IEEE Security and Privacy Distinguished Student Paper award; his work on hashing to elliptic curves is being standardized by the IETF.

1 0

CS Colloquium Speaker: Fraser Brown, today at 12:30pm EST
by Emily C. Lawrence 18 Mar '21

18 Mar '21

CS Colloquium Speaker Fraser Brown, Stanford University Host: Wyatt Lloyd Date: Thursday, March 18 Time: 12:30pm EST Event page: [ https://www.cs.princeton.edu/events/26053 | https://www.cs.princeton.edu/events/26053 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_zrh31QWnTI2rkKRYabO8rg | https://princeton.zoom.us/webinar/register/WN_zrh31QWnTI2rkKRYabO8rg ] Title: Eliminating Bugs in Real Systems Abstract: Software is everywhere, and almost everywhere, software is broken. Some bugs just crash your printer; others hand an identity thief your bank account number; still others let nation-states spy on dissidents and persecute minorities. This talk outlines my work preventing bugs using a blend of programming languages techniques and systems design. First, I'll talk about securing massive, security-critical codebases without clean slate rewrites. This means rooting out hard-to-find bugs---as in Sys, which scales symbolic execution to find exploitable bugs in systems like the twenty-million line Chrome browser. It also means proving correctness of especially vulnerable pieces of code---as in VeRA, which automatically verifies part of the Firefox JavaScript engine. Finally, I'll discuss work on stronger foundations for new systems---as in CirC, a recent project unifying compiler infrastructure for program verification, cryptographic proofs, optimization problems, and more. Bio: Fraser Brown is a PhD student at Stanford advised by Dawson Engler, occasional visiting student at UCSD with Deian Stefan, and NSF graduate research fellowship recipient. She works at the intersection of programming languages, systems, and security, and her research has been used by several companies. She holds an undergraduate degree in English from Stanford.

1 0

Reminder: Fraser Brown, tomorrow at 12:30
by Emily C. Lawrence 17 Mar '21

17 Mar '21

CS Colloquium Speaker Fraser Brown, Stanford University Host: Wyatt Lloyd Date: Thursday, March 18 Time: 12:30pm EST Event page: [ https://www.cs.princeton.edu/events/26053 | https://www.cs.princeton.edu/events/26053 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_zrh31QWnTI2rkKRYabO8rg | https://princeton.zoom.us/webinar/register/WN_zrh31QWnTI2rkKRYabO8rg ] Title: Eliminating Bugs in Real Systems Abstract: Software is everywhere, and almost everywhere, software is broken. Some bugs just crash your printer; others hand an identity thief your bank account number; still others let nation-states spy on dissidents and persecute minorities. This talk outlines my work preventing bugs using a blend of programming languages techniques and systems design. First, I'll talk about securing massive, security-critical codebases without clean slate rewrites. This means rooting out hard-to-find bugs---as in Sys, which scales symbolic execution to find exploitable bugs in systems like the twenty-million line Chrome browser. It also means proving correctness of especially vulnerable pieces of code---as in VeRA, which automatically verifies part of the Firefox JavaScript engine. Finally, I'll discuss work on stronger foundations for new systems---as in CirC, a recent project unifying compiler infrastructure for program verification, cryptographic proofs, optimization problems, and more. Bio: Fraser Brown is a PhD student at Stanford advised by Dawson Engler, occasional visiting student at UCSD with Deian Stefan, and NSF graduate research fellowship recipient. She works at the intersection of programming languages, systems, and security, and her research has been used by several companies. She holds an undergraduate degree in English from Stanford.

1 0

Divyarthi Mohan will present her Pre-FPO "Simplicity and Optimality in Algorithmic Economics: Multi-item Mechanism Auctions and Social Learning" on Wednesday, March 24 at 10.30am via Zoom.
by Nicki Mahler 16 Mar '21

16 Mar '21

Divyarthi Mohan will present her Pre-FPO " Simplicity and Optimality in Algorithmic Economics: Multi-item Mechanism Auctions and Social Learning" on Wednesday, March 24 at 10.30am via Zoom. Zoom link: [ https://princeton.zoom.us/j/95620223131?pwd=SWJIOFhQOGd1djR2a0ZVWm8rQUJ0QT09 | https://princeton.zoom.us/j/95620223131?pwd=SWJIOFhQOGd1djR2a0ZVWm8rQUJ0QT09 ] Committee Members: Prof. Matt Weinberg (Advisor) Prof. Bernard Chazelle (Examiner) Prof. Ran Raz (Examiner) Prof. Mark Braverman (Reader) Dr. Nicole Immorlica (Reader) Title: " Simplicity and Optimality in Algorithmic Economics: Multi-item Mechanism Auctions and Social Learning" Abstract. Designing mechanisms to maximize revenue is a fundamental question in mathematical economics, motivated by numerous practical applications like pricing goods, online ad auctions, and spectrum auctions. In his seminal work, Myerson resolved the single-dimensional case by proving that simply posting a take-it-or-leave-it price is the optimal mechanism. Unfortunately, optimal auctions for selling multiple items can be unreasonably complex and computationally intractable. In response, the past decade has seen a long line of work in theoretical computer science studying simple and computationally-efficient auctions through the lens of approximation. These works study particular simple auctions and show that they can get approximately optimal revenue (usually a constant factor). More recently, there are works that move away from this binary take on simplicity and instead explore the trade-off between simplicity and optimality. In this talk, we consider a revenue-maximizing seller with n items facing a single unit-demand buyer. Our work shows that simple mechanisms can achieve almost optimal revenue. We approached the tradeoffs of simplicity formally through the lens of computation and "menu size". Our main result provides a mechanism that gets a (1 − ε)-approximation to the optimal revenue in time quasi-polynomial in n. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distinct options the buyer may purchase, up to permutations of the items. We show that the above approximately optimal mechanism has quasi-polynomial symmetric menu complexity. Prior to our work, no sub-exponential upper bounds (or super-polynomial lower bounds) were known in any multi-dimensional setting, for either measure. I will also discuss recent work on social learning between two Bayesian agents with limited/simple communication. In our model, to reflect real social exchanges, agents simply share a signal/anecdote they observed instead of sending arbitrary messages. When the agents have a fundamental difference, we show that the optimal communication scheme can vary drastically (from sending the most representative anecdote to an extremely biased anecdote) depending on whether the receiver can observe the communication scheme used by the sender.

1 0

CS Colloquium Speaker: Riad Wahby, Monday, March 22 at 12:30
by Emily C. Lawrence 15 Mar '21

15 Mar '21

CS Colloquium Speaker Riad Wahby, Stanford University Host: Andrew Appel Date: Monday, March 22 Time: 12:30pm EST Event page: [ https://www.cs.princeton.edu/events/26050 | https://www.cs.princeton.edu/events/26050 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_SMKdFMoQRo2Cj3zvU57zyw | https://princeton.zoom.us/webinar/register/WN_SMKdFMoQRo2Cj3zvU57zyw ] Title: Probabilistic Proofs: Theory, Hardware, and Everything in Between Abstract: In the past decade, systems that use probabilistic proofs in real-world applications have seen explosive growth. These systems build upon some of the crown jewels of theoretical computer science---interactive proofs, probabilistically checkable proofs, and zero-knowledge proofs---to solve problems of trust and privacy in a wide range of settings. This talk describes my work building systems that answer questions ranging from "how can we build trustworthy hardware that uses untrusted components?" to "how can we reduce the cost of verifying smart contract execution in blockchains?" Along the way, I will discuss the pervasive challenges of efficiency, expressiveness, and scalability in this research area; my approach to addressing these challenges; and future directions that promise to bring this exciting technology to bear on an even wider range of applications. Bio: Riad S. Wahby is a Ph.D. candidate at Stanford, advised by Dan Boneh and Keith Winstein. His research interests include systems, computer security, and applied cryptography. Prior to attending Stanford, Riad spent ten years as an analog and mixed-signal integrated circuit designer. Riad and his collaborators received a 2016 IEEE Security and Privacy Distinguished Student Paper award; his work on hashing to elliptic curves is being standardized by the IETF.

1 0

CS Colloquium Speaker: Fraser Brown, Thursday, March 18 at 12:30
by Emily C. Lawrence 11 Mar '21

11 Mar '21

CS Colloquium Speaker Fraser Brown, Stanford University Host: Wyatt Lloyd Date: Thursday, March 18 Time: 12:30pm EST Event page: [ https://www.cs.princeton.edu/events/26053 | https://www.cs.princeton.edu/events/26053 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_zrh31QWnTI2rkKRYabO8rg | https://princeton.zoom.us/webinar/register/WN_zrh31QWnTI2rkKRYabO8rg ] Title: Eliminating Bugs in Real Systems Abstract: Software is everywhere, and almost everywhere, software is broken. Some bugs just crash your printer; others hand an identity thief your bank account number; still others let nation-states spy on dissidents and persecute minorities. This talk outlines my work preventing bugs using a blend of programming languages techniques and systems design. First, I'll talk about securing massive, security-critical codebases without clean slate rewrites. This means rooting out hard-to-find bugs---as in Sys, which scales symbolic execution to find exploitable bugs in systems like the twenty-million line Chrome browser. It also means proving correctness of especially vulnerable pieces of code---as in VeRA, which automatically verifies part of the Firefox JavaScript engine. Finally, I'll discuss work on stronger foundations for new systems---as in CirC, a recent project unifying compiler infrastructure for program verification, cryptographic proofs, optimization problems, and more. Bio: Fraser Brown is a PhD student at Stanford advised by Dawson Engler, occasional visiting student at UCSD with Deian Stefan, and NSF graduate research fellowship recipient. She works at the intersection of programming languages, systems, and security, and her research has been used by several companies. She holds an undergraduate degree in English from Stanford.

1 0

Andrew Or will present his Pre FPO "Abstracting systems challenges from distributed deep learning" on Wednesday, March 17, 2021 at 1pm via Zoom.
by Nicki Mahler 10 Mar '21

10 Mar '21

Andrew Or will present his Pre FPO " Abstracting systems challenges from distributed deep learning" on Wednesday, March 17, 2021 at 1pm via Zoom. Zoom link: [ https://princeton.zoom.us/j/91618635317?pwd=cyt5WmdFQ2xaWmNGb2U0bTNlZXBYZz09 | https://princeton.zoom.us/j/91618635317?pwd=cyt5WmdFQ2xaWmNGb2U0bTNlZXBYZz09 ] Committee: Michael J. Freedman (advisor, examiner) Kai Li (examiner) Wyatt Lloyd (examiner) Amit Levy (reader) Ravi Netravali (reader) Talk abstract follows below. All are welcome to attend. Abstract: State-of-the-art distributed deep learning systems tightly couple model execution with the underlying hardware. Existing frameworks assume resource allocations must be fixed throughout the lifetime of a job, often leading to inefficiency in the usage of cluster resources. Further, model hyperparameters need to be retuned across different hardware configurations in order to achieve the same training result. In a world where the scale of deep learning workloads is growing rapidly, this requirement poses significant barriers to experimentation on smaller test beds and reproducing results across different hardware. In this thesis, we demonstrate that the above assumptions are not fundamental to distributed deep learning, and we resolve these limitations by proposing two systems built on top of TensorFlow. The first is an autoscaling engine that, through trial-and-error, automatically determines the most resource-efficient hardware configuration for a given job. We propose pluggable heuristics tailored for deep learning workloads that incrementally guide the system towards such a configuration. Instead of repeatedly stopping the job and restarting it from checkpoints, which can lead to GPUs or TPUs going idle for minutes every time, our system adjusts the all-reduce membership dynamically in between batches without interrupting the job. The second system is VirtualFlow, which leverages a novel abstraction between the model and the underlying hardware called virtual node processing. From the perspective of the model, virtual nodes, instead of physical devices (GPUs or TPUs), perform the computation. When multiple virtual nodes are mapped to a physical device, they are processed sequentially on that device. This representation allows users to train a model using the same batch size (and other hyperparameters) across different hardware, thereby preserving application-level semantics while hiding hardware-level details from the user. Using this technique, VirtualFlow also enables a variety of new important use cases that improve resource efficiency, including resource elasticity and heterogeneous training (using different types of GPUs in the same job).

1 0