Dan Alistarh • IST, Austria
Relaxed Semantics Scalable Distributed Algorithms and Systems
Distribution has been a major trend in computing over the last two decades, and has enabled a wide range of applications, from the fast training of large-scale machine learning models, to cloud services which can process our requests within milliseconds. In this talk, I will describe some of the basic ideas underpinning these applications, in the context of the work done by our lab. Specifically, I will first describe the role of efficient distributed algorithms in machine learning, as well as the intriguing trade-offs between their synchronization costs and their convergence properties. Second, I will discuss our work on scalable variants of classic data structures such as priority queues, and their applications to scalable concurrent graph algorithms.
Bio: Dan Alistarh is currently an Assistant Professor at IST Austria. Previously, he was affiliated with ETH Zurich, Microsoft Research, and MIT, and he received his PhD from the EPFL, under the guidance of Prof. Rachid Guerraoui. His research focuses on distributed algorithms and concurrent data structures, and spans from algorithms and lower bounds to practical implementations. Recently, his focus has been on efficient algorithms for machine learning, for which he has been awarded an ERC Starting Grant in 2018. He is an ACM distinguished speaker, ELLIS scholar, and a member of the Vienna Graduate School for Computational Optimization. He was a keynote speaker at the International Symposium on Distributed Computing in 2019, and a co-recipient of best paper awards at OPODIS 2019 and ACM PPoPP 2020. In his spare time, he is the Machine Learning research lead at Neural Magic, a startup based in Boston, MA.
Kenneth Cheung • NASA, USA
Structure Structuring Structures
We consider programmable materials as systems with the ability to form versatile structures as similar to the ability of a digital image to approximate any image, given high enough resolution, with a very simple set of discrete components. Instead of colors, we can tune effective shape and mechanical behavior (instead of pixels, we refer to building blocks as voxels, for volumetric pixels). Modular reconfigurable structures have been appreciated throughout technological history. A key philosophical idea behind programmable materials is that they can be engineered to maintain a fixed precision at essentially arbitrary scale, achieved by careful design of connections that display symmetric error distributions [Gregg et al. 2018], allowing for tolerances that do not increase with system size. This principle is well exercised in the scaling robustness of digital communication and computation systems, which rely on well-engineered encoding, error detection, and correction for systems composed of many similar discrete information building blocks [Shannon 1948]. Can we formulate a general mathematical theory of structured fabrication of physical products? An argument for the timeliness of this question (and revisiting prior versions thereof) is given by the existence of examples of physical modular structural systems that no longer present a mechanical performance compromise relative to conventionally manufactured hardware. These “metamaterials” are possible because assembly allows production of almost any geometry with almost any material [Cheung et al. 2013], and with progress in our ability to characterize the effect of geometry on the whole of material mechanical properties [Ashby and Gibson 1997]. The most significant benefit might be in extended material life-cycles and corresponding reductions in energy use [Gregg et al. 2019].
Bio: Kenny Cheung directs the NASA Ames Research Center Coded Structures Laboratory, which conducts interdisciplinary research at the intersection of design, control theory, material science, mechanical engineering, and aeronautical engineering. Current work focuses on applying building-block based programmable materials and algorithms to aeronautical and space applications. This includes large scale, long duration, and reconfigurable space infrastructure, as PI for the Automated Reconfigurable Mission Adaptive Digital Assembly Systems (ARMADAS) project, and high efficiency shape morphing aircraft, under the Mission Adaptive Digital Composite Aerostructures Technologies (MADCAT) project.
He also serves as the technical lead on advanced materials and manufacturing for the Ames Center Chief Technologist (CCT) staff, helping to identify, define, develop and integrate new and emerging technologies for application to aeronautics research and space exploration goals. Before joining NASA, Kenny received his Ph.D. from the Center for Bits and Atoms at the Massachusetts Institute of Technology, where he showed that digital material strategies can be used to make new kinds of materials (strong and light weight), and new kinds of robots (like transformers). His M.S. work at the MIT Media Lab was on anonymized empirical models of human behavior using mobile devices, and prior work includes research on natural mechanical systems (plant biomechanics) and the science of the human environmental response (environmental psychology). He has papers and patents on topics ranging from high performance composite material manufacturing systems to synthetic protein folding algorithms, surgical devices, and indoor mobile device location systems. He’s particularly fond of applying rapid prototyping to test ideas that can change the status quo in design, based on physical first-principles analyses
Rotem Oshman • Tel Aviv University, Israel
Distributed Zero-Knowledge Proofs
Zero-knowledge proofs are one of the most influential concepts in theoretical computer science. In the seminal definition due to Goldwasser, Micali and Rackoff dating back to the 80’s, a computationally-bounded verifier interacts with a powerful but untrusted prover, with the goal of becoming convinced that the input is in some language. In addition to the usual requirements of completeness and soundness, in a zero-knowledge proof, we protect the prover’s knowledge: assuming the prover is honest, anything that the verifier can deduce after interacting with the prover, it could have deduced by itself. Zero-knowledge proofs have found many applications within theoretical computer science and beyond, e.g., in cryptography, client-cloud computing, blockchains and cryptocurrencies, electronic voting and auctions, and in the financial industry.
In this talk I will describe recent work on extending the notion of zero-knowledge proofs to distributed networks, where a network of verifiers interacts with an untrusted prover to decide some distributed language. The prover is assumed to know the entire network graph, as well as any input that the nodes may possess, and, as in the centralized setting, the protocol we design should protect this knowledge. Building on the recent introduction of distributed interactive proofs, we define distributed zero-knowledge proofs and construct such proofs for the 3-coloring problem and for other fundamental problems.
Joint work with Aviv Bick and Gillat Kol.
Friedhelm Meyer auf der Heide
Heinz Nixdorf Institut
Universität Paderborn, Germany
2021 SIROCCO Prize Awardee
Continuous Strategies for Swarms of Mobile Robots
Consider large swarms of relatively simple mobile robots deployed to the plane (or higher dimensional space). Each robot has only very limited local information about the swarm. More precisely, a swarm consists of identical, anonymous robots: they are points in the plane and their local information consists only of the relative positions of the robots within a small, bounded viewing radius. I will focus on strategies of such swarms that solve formations problems like “gathering in one point”, “forming a straight line connecting two stations”, or “forming a line of maximum length”. Most of the past and current work deals with strategies that assume a discrete, round-based time model: In a round, each robot performs a so-called look-compute-move cycle.
In this talk, I discuss a continuous model, where each robot continuously observes its neighborhood and continuously adapts its speed (with given speed limit) and direction following a local rule. For the above-mentioned formation problems, I present and analyse continuous strategies. A comparison to their discrete counterparts demonstrates the elegance of continuous strategies. For example, a simple criterion – being contracting – that essentially all known continuous gathering strategies have in common, guarantees gathering and a quadratic time bound.
Laudatio: click here