menu
  • Algorithmic Programmable Matter by Andrea Richa (Arizona State University)
    Abstract
    Many programmable matter systems have been developed, including modular and swarm robotics, synthetic biology, DNA tiling, and smart materials. We describe programmable matter as an abstract collection of simple computational elements (particles) with limited memory that each execute distributed, local, asynchronous algorithms to self-organize and solve system-wide problems such as movement, configuration, and coordination. Self-organizing particle systems (SOPS) have many interesting applications like coating objects for monitoring and repair purposes, and forming nano-scale devices for surgery and molecular-scale electronic structures. We describe some of our work on establishing the algorithmic foundations of programmable matter, investigating how macro-scale system behaviors can naturally emerge from local micro-behaviors by individual particles. In particular, we utilize tools from statistical physics and Markov chain analysis to translate Markov chains defined at a system level into asynchronous, distributed, local algorithms for SOPS that drive the desired emergent collective behavior. We further establish the notion of algorithmic matter, where we leverage standard binary computation, as well as physical characteristics of the robots and interactions with the environment in order to implement our micro-level algorithms in actual testbeds composed of robots that are not capable of any standard computation.
    Biography
    Andrea Richa is the Professor of Computer Science and Engineering at Arizona State University. Her main areas of expertise are in distributed and network algorithms and computing in general. More recently, she has focused on developing the algorithmic foundations on what has been coined as programmable matter, through her work on self-organizing particle systems (SOPS). Her work has been widely cited, and includes, besides SOPS, work on bio-inspired distributed algorithms, distributed load balancing, packet routing, wireless network modeling and topology control, wireless jamming, data mule networks, underwater optical networking, and distributed hash tables (DHTs). She received the 2017 Best Senior Researcher award from the School of Computing, Informatics, and Decision Systems Engineering (CIDSE). She was the recipient of an NSF CAREER Award in 1999, an associate editor of IEEE Transactions on Mobile Computing, and the keynote speaker and program and general chair of several prestigious conferences. She has also delivered several invited talks both nationally and internationally.

  • Blockchains and the Future of Distributed Computing by Maurice Herlihy (Brown University)
    Abstract
    There has been a recent explosion of interest in blockchain-based distributed ledger systems such as Bitcoin, Ethereum, and many others. Much of this work originated outside the distributed computing community, but the questions raised, such as consensus, replication, fault-tolerance, privacy, and security, and so on, are all issues familiar to our community.
    This talk, intended for a general audience, surveys the theory and practice of blockchain-based distributed systems from the point of view of classical distributed computing, along with speculation about promising future research directions for the distributed computing community.
    Biography
    Maurice Herlihy has an A.B. in Mathematics from Harvard University, and a Ph.D. in Computer Science from M.I.T. He served on the faculty of Carnegie Mellon University, on the staff of DEC Cambridge Research Lab, and is currently Professor in the Computer Science Department at Brown University. He received the 2003 Dijkstra Prize in Distributed Computing, the 2004 Goedel Prize in Theoretical Computer Science, and the 2012 Dijkstra Prize in Distributed Computing. He is an ACM Fellow and a member of the National Academy of Engineering. His research focuses on practical and theoretical aspects of concurrent and distributed computing. His early work on wait-free synchronization showed that different synchronization operations have different computational power, but that any operation that can solve consensus is universal. With Jeannette Wing, he invented the notion of linearizability, a popular correctness condition for concurrent data structures. With James Aspnes and Nir Shavit, he developed counting networks, a class of highly-concurrent, low-contention data structures for counting and related tasks. With Nir Shavit, he developed new ways to reason about distributed algorithms, based on combinatorial and algebraic topology, yielding new lower bounds to previously unsolved problems. With Eliot Moss, he invented transactional memory, a multiprocessor synchronization architecture that has been incorporated into recent processors by Intel and IBM.

  • The Pit and the Pendulum by Lorenzo Alvisi (Cornell University)
    Abstract
    Since the elegant foundations of transaction processing were established in the mid 70’s with the notion of serializability and the codification of the ACID (Atomicity, Consistency, Isolation, Durability) paradigm, performance has not been considered one of ACID’s strong suits, especially for distributed data stores. Indeed, the NoSQL/BASE movement of the last decade was born out of frustration with the limited scalability of traditional ACID solutions, only to become itself a source of frustration once the challenges of programming applications in this new paradigm began to sink in. But how fundamental is this dichotomy between performance and ease of programming? In this talk, I will share what my students and I have learned while trying to overcome the traditional terms of this classic tradeoff.
    Biography
    Lorenzo Alvisi is the Tisch University Professor of Computer Science at Cornell University. Prior to joining Cornell, he held an endowed professorship at UT Austin, where he is now a Distinguished Professor Emeritus. Lorenzo received his Ph.D. in 1996 from Cornell, after earning a Laurea cum Laude in Physics from the University of Bologna. His research interests are in the theory and practice of distributed computing. He is a Fellow of the ACM and IEEE, an Alfred P. Sloan Foundation Fellow, and the recipient of a Humboldt Research Award, an NSF Career Award, and several teaching awards. He serves on the editorial boards of ACM TOCS and Springer’s Distributed Computing. In addition to distributed computing, he is passionate about classical music and red Italian motorcycles.