Akshay Shah on "Epidemic algorithms in replicated databases"

Mini: Shadaj Laddad on "Perceus: Garbage Free Reference Counting with Reuse"

Abstract: We introduce Perceus, an algorithm for precise reference counting with reuse and specialization. Starting from a functional core language with explicit control-flow, Perceus emits precise reference counting instructions such that programs are garbage free, where only live references are retained. This enables further optimizations, like reuse analysis that allows for guaranteed in-place updates at runtime. This in turn enables a novel programming paradigm that we call functional but in-place (FBIP). Much like tail-call optimization enables writing loops with regular function calls, reuse analysis enables writing in-place mutating algorithms in a purely functional way. We give a novel formalization of reference counting in a linear resource calculus, and prove that Perceus is sound and garbage free. We show evidence that Perceus, as implemented in Koka, has good performance and is competitive with other state-of-the-art memory collectors.

Bio: Shadaj is an Applied Scientist at AWS, where he is the research lead for Hydro, a Rust framework for verifiably correct distributed systems. Previously, he completed his PhD at UC Berkeley co-advised by Alvin Cheung and Joe Hellerstein. When not researching, you'll find him playing the sitar, editing travel photos, or watching the latest season of Survivor.

Main: Akshay Shah on "Epidemic algorithms in replicated databases"

Abstract: When a database is replicated at many sites, maintaining mutual consistency among the sites in the face of updates is a significant problem. This paper describes several randomized algorithms for distributing updates and driving the replicas toward consistency. The algorithms are very simple and require few guarantees from the underlying communication system, yet they ensure that the effect of every update is eventually reflected in all replicas. The cost and performance of the algorithms are tuned by choosing appropriate distributions in the randomization step. The algorithms are closely analogous to epidemics, and the epidemiology literature aids in understanding their behavior. One of the algorithms has been implemented in the Clearinghouse servers of the Xerox Corporate Internet. solving long-standing problems of high traffic and database inconsistency.

Bio: Akshay is the Field CTO at Antithesis, where he makes tools to thoroughly test distributed systems. In the past, he’s been an infra and platform engineer at Uber, Microsoft, other people’s silly startups, and his own silly startup. Apart from computers, he likes bicycles and coffee. And as of tonight, he co-organizes Papers We Love!

RSVP to join us in person! If you can't make it live, join on Zoom - no RSVP needed. The agenda is also available online.