Lectures

Ozalp Babaoglu, Università di Bologna

Seminar: Beyond Broadcast: Harnessing Gossiping for Robust Distributed Algorithms

Modern distributed systems face inherent challenges in achieving scalability, fault-tolerance, and efficient coordination. This talk explores gossiping, a decentralized communication paradigm where nodes exchange information only with a few immediate neighbors, as an effective approach for meeting these challenges. I will present our work in designing novel gossip-based algorithms that address a range of fundamental problems in distributed systems that go well beyond broadcasting, which had been the initial motivation for gossiping.  The problems I will address include dynamic network formation, robust distributed computation, large-scale heart-beat synchronization, adaptive topology management, and self-organizing formation creation.

Matteo Frigo, Google

Mini Course: The Cilk system for multi-threaded programming

We discuss how to analyze and estimate the performance of parallel algorithms in terms of "work" and "span".  We show how to express "fork/join" parallel algorithms in the Cilk language.  We discuss a simple randomized "work-stealing" scheduler that attains asymptotically optimal performance, and show practical implementation techniques that enable good concrete performance.  We extend the basic work/span model to include a memory hierarchy, and we show how to analyze algorithms in this extended setting.  We give examples of how a dynamic scheduler

benefits irregular problems, such as alpha/beta pruning in a chess game tree.

Flavio Chierichetti, Sapienza University of Rome

Mini Course: Algorithms in the Dark: Decision-Making with Partial Information

Modern algorithms must act in split seconds while seeing only fragments of a massive, ever-changing environment. This mini-course first tackles the expert problem, showing how its classic strategies drive real-world systems—from ad-selection engines that hedge among bidding tactics to news-feed rankers that combine many weak signals without ever over-committing to any single one. We then explore local graph sampling; we will show how a crawler can return near-uniform-at-random nodes in a social network to gauge global sentiment without downloading the full graph. Together, these two settings illuminate the broader challenge of making sound choices when the full input remains hidden.

Bill Joy, Water Street Capital

Seminar: 50 Years of Advancements: Computing and Technology 1975-2025 (and beyond)

I came to UC Berkeley CS in 1975 as a graduate student expecting to do computer theory—Berkeley CS didn’t have a proper departmental computer and I was tired of coding having written a lot of numerical code for early supercomputers.

But it’s hard to make predictions, especially about the future. Berkeley soon had a Vax Superminicomputer, I installed a port of UNIX and was upgrading the operating system, and the Internet and Microprocessor boom beckoned.

This talk is a brief overview of the last 50 years, of how software hardware and algorithms for numerical and symbolic computing have evolved, about the changes in programming and programming languages, and some thoughts on managing technology and addressing climate change, and especially, looking forward, about the future of scientific and AI computing.

Andrea Lodi, Cornell Tech

Seminar: Mixed-Integer Programming: 65+ years of history and the Artificial Intelligence challenge

Mixed-Integer Programming (MIP) technology is used daily to solve (discrete) optimization problems in contexts as diverse as energy, transportation, logistics, telecommunications, biology, just to mention a few. The MIP roots date back to 1958 with the seminal work by Ralph Gomory on cutting plane generation. In this talk, we will discuss — taking the (biased) viewpoint of the speaker — how MIP evolved in its main algorithmic ingredients, namely preprocessing, branching, cutting planes and primal heuristics, to become a mature research field whose advances rapidly translate into professional, widely available software tools. We will then discuss the next phase of this process, where Artificial Intelligence and, specifically, Machine Learning are already playing a significant role, a role that is likely to become even more crucial.

Nicola Prezza, University of Venice "Ca' Foscari"

Seminar: Algorithms, Data Structures, and Nucleotides

What do the bits of a computer have in common with the molecules (nucleotides) that make up our DNA? Both are used to store information: while the former encode documents such as images or videos, the latter are the symbols that nature has chosen to program living beings. At the most fundamental level, however, they are both information: we can encode a JPEG using DNA, just as we can store DNA in the RAM of a computer. In this presentation I will show how modern biologists and bioinformaticians translate DNA into bits and how modern computer scientists combine techniques from information theory and data structures to analyze this "digitized" DNA.

Michel Raynal, INRIA

Seminar: On Distributed Computing: A View, Physical Versus Logical Objects, and a Look at Fully Anonymous Systems

This talk presents a short (and partial) history of synchronization in systems made up of asynchronous sequential processes (automata). Among other points, it shows that synchronization (which consists in ordering operations issued by  processes on shared objects) has a different flavor according to the fact that the  objects are physical objects (such as a printer or a disk) or logical objects (immaterial  objects represented by sequences of bits). It then follows from this physical/logical nature of computing objects that mutual exclusion is to physical objects what consensus is to logical objects. The article also addresses recent results on process synchronization in fully anonymous systems (systems in which processes cannot be distinguished one from the other, and where there is a disagreement on the addresses of the shared memory registers.

Fred Schneider, Cornell University

Seminar 1: Laws for Cybersecurity?

Cyber-security today is focused largely on defending against known attacks. We learn about the latest attack and find a patch to defend against it. Our defenses thus improve only after they have been successfully penetrated. This is a recipe to ensure some attackers succeed—not a recipe for achieving system trustworthiness. We must move beyond reacting to yesterday's attacks and instead start building systems whose trustworthiness derives from first principles--laws that relate attacks, defense mechanisms, and security properties. This talk will explore examples of such laws and suggest avenues for future exploration.

Seminar 2: Hyperproperties: Beyond Safety and Liveness

Most formal assurance arguments prove safety and/or liveness trace-properties of a system  Trace properties are defined by predicates on individual execution traces; hyperproperties are defined by predicates on sets of trace-properties.  We illustrate why the added expressiveness of hyperproperties is needed. And we discuss how to verify an important class of hyperproperties, focusing on aspects of a logic for verifying trace properties that would facilitate verification of hyperproperties.

Seminar 3: System Principles vs System Artifacts

CS departments typically offer courses that focus on specific classes of system artifacts:  operating systems, networks, database systems, computer hardware.  However, a close look reveals overlap in the coverage of these courses, because they all instantiate a small set of principles for building these various kinds of systems.  This talk will discuss what are those principles and what is the essence of "systems" as a subject of study, independent of specific artifacts.