Event Archive

This talk presents our ongoing efforts of applying formal methods to a critical component in the Linux kernel, the just-in-time compilers (“JITs”) for the extended Berkeley Packet Filter (BPF).  Building on our automated verification framework Serval, we have developed Jitterbug, a tool for writing JITs and proving them correct.  We have used Jitterbug to find 30+ new bugs in the BPF JITs for the x86-32, x86-64, arm32, arm64, and riscv64 architectures, and to develop a new BPF JIT for riscv32, RISC-V compressed instruction support for riscv64, and new optimizations in existing JITs.

A key challenge for high performance distributed storage systems is balancing load in the presence of highly skewed and dynamic workloads. In this talk, I will present our recent work Pegasus, a new storage system that leverages programmable switch ASICs to balance load across storage servers. Pegasus selectively replicates a small set of popular objects, and builds a coherence directory in the switch data plane to track and manage the location of these replicated objects.

Clock synchronization is critical for many datacenter applications such as distributed transactional databases, consistent snapshots, and network telemetry. As applications have increasing performance requirements and datacenter networks get into ultra-low latency, we need submicrosecond-level bound on time-uncertainty to reduce transaction delay and enable new network management applications (e.g., measuring one-way delay for congestion control).

As datacenter network bandwidth keeps growing, proactive transport becomes attractive, where bandwidth is proactively allocated as “credits” to senders who then can send “scheduled packets” at a right rate to ensure high link utilization, low latency, and zero packet loss. While promising, a fundamental challenge is that proactive transport requires at least one-RTT for credits to be computed. In this talk, I will introduce Aeolus, a solution focusing on “pre-credit” packet transmission as a building block for proactive transports.

Nonprofit crowdsourcing platforms such as food recovery organizations rely on volunteers to perform time-sensitive tasks. To encourage volunteers to complete a task, platforms use nudging mechanisms to notify a subset of volunteers with the hope that at least one of them responds positively. However, since excessive notifications may reduce volunteer engagement, the platform faces a trade-off between notifying more volunteers for the current task and saving them for future ones.

Part of the IBM Back to School Series.  This is a continuing series held at IBM where university professors share their knowledge and experience with the IBM technical community.  Duke CS and Duke ECE is invited to attend as colleagues of the speaker.

The automotive industry is a driver of global economic development, acting as a force of scientific research and technological innovation. In the 21st century, this industry is on the cusp of revolutionary change with the emergence of self-driving vehicles. Without human oversight, these autonomous vehicles operate with the assistance of cameras, sensors, and software. Currently, AD generally suffers from bad vision in low-light conditions, especially from the glares of other vehicles.

The unprecedented amount of data available today opens the door to many new applications in areas such as finance, scientific simulation, machine learning, etc. Many such applications perform the same computations on different data, which are called data-parallel. However, processing this enormous amount of data is challenging, especially in the post-Moore's law era. Specialized accelerators are a promising solution to meet the performance requirements of data-parallel applications. Among these are graphics processing units (GPUs), as well as more application-specific solutions.

After viewing the Picture A Scientist movie over the weekend of November 13-15, join us for a follow-up discussion with a Duke Computer Science panel on Tuesday, November 17 at 12:00 Noon EST, hosted by the Duke Department of Computer Science and the Duke Computer Science Student Union (CSSU). Learn more about this movie.

FOCS 2020, the IEEE Symposium on Foundations of Computer Science, is the flagship conference sponsored by the IEEE Computer Society Technical Committee on the Mathematical Foundations of Computing (TCMF) and covers a broad range of theoretical computer science as you can see in the Program and in the Accepted Papers. FOCS is held annually and is hosted virtually in 2020 by Duke!

Join us for a screening of the Picture A Scientist movie over the weekend of November 13-15.  You have a 72-hour period over that weekend to view this powerful and timely 2020 documentary featured at the Tribeca Film Festival.  See the movie trailer at https://vimeo.com/405966332.

Large organization that collect data about populations (like the US Census Bureau) release summary statistics about these populations to satisfy the data needed by multiple resource allocation and policy making problems. These organizations are also legally required to ensure privacy of the individuals, and hence, differential privacy (DP) is a perfect solution. However, most differentially private mechanisms are designed to answer a single set of queries and optimize the total accuracy across the entire set.

A famous 1986 result by Tardos on combinatorial linear programs showed that a linear program can be solved in poly(n,m,log Delta) arithmetic operations, where Delta is the maximum subdeterminant of the integer constraint matrix. Note that this bound is independent from the right hand side and the cost vector.

The generation of synthetic data is useful in multiple aspects, from testing applications to benchmarking to privacy preservation. Generating the links between relations, subject to cardinality constraints (CCs) and integrity constraints(ICs) is an important aspect of this problem.

Algorithmic recommendation systems impact the choices of millions of consumers daily; these systems exist for a wide variety of markets, including both consumable and durable goods, as well as digital and physical goods. After a recommendation system is in place, it will need to be periodically updated to incorporate new users, new items, and new observed interactions between users and items. These observed data, however, are algorithmically confounded: they are the result of a feedback loop between human choices and the existing algorithmic recommendation system.

Consider the problem of computing the majority of a stream of n i.i.d. uniformly random bits. This problem, known as the coin problem, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant advantage (over the uniform distribution) must use Ω(log n) bits of space. Previously, it was known that computing the majority on every input with a constant probability takes Ω(log n) space.

Digital contact-tracing is a tantalizing new tool for helping governments and public-health agencies slow the spread of COVID-19. This talk will recount the history of the technology, outline its fundamental privacy-utility trade-offs, and describe Washington State's experience deploying Apple and Google's Exposure Notifications system.

Motivated by online labor markets, we consider the online assortment optimization problem faced by a two-sided matching platform that hosts a set of suppliers waiting to match with a customer. Arriving customers are shown an assortment of suppliers, and may choose to issue a match request to one of them. Before leaving the platform, each supplier reviews all the match requests he has received and, based on his preferences, he chooses whether to match with a customer or to leave unmatched.

We provide a new protocol for Validated Asynchronous Byzantine Agreement in the authenticated setting. Validated (multi-valued) Asynchronous Byzantine Agreement is a key building block in constructing Atomic Broadcast and fault-tolerant state machine replication in the asynchronous setting.

Traditional machine learning methods often assume access to trustworthy data.  However, this assumption fails to hold in many real-world scenarios.  In particular, entities being classified may be incentivized to misreport their private information (i.e., their features) in order to receive a more desirable outcome.  In such cases, the performance of traditional methods may be arbitrarily bad, and it is therefore crucial to design incentive-aware machine learning methods that are robust to such strategic behavior.  In this talk, we introduce a general framework for incenti