Colloquium: Mergeable Replicated Data Types

This week, we're presenting a bonus computer science colloquium on Wednesday from 11:15 a.m. - 12:15 p.m.

This week's speaker, Gowtham Kaki (University of Colorado Boulder), will be giving a talk titled "Mergeable Replicated Data Types".

Abstract

Programming distributed applications with replicated state is challenging given the complexity of reasoning about different evolving states on different replicas. Existing approaches to this problem impose significant burden on application developers to consider the effect of how operations performed on one replica are witnessed and applied on others. In this talk, I present Mergeable Replicated Data Types (MRDTs) — a new abstraction to structure the replicated state that addresses this problem. MRDTs equip replicated state with a versioning scheme, and an ability to merge concurrent versions of the state in presence of a common ancestor version.  MRDTs are accompanied by an expressive distributed programming model that lets distributed applications be built using ordinary data types extended with three-way merge functions. Importantly, merge functions for various data types can be derived from the first principles, facilitating their automatic promotion to replicated data types. I present an OCaml implementation called Quark that adapts Git version control infrastructure to efficiently support MRDTs. As a testament to the versatility and practicality of MRDTs, I demonstrate various distributed application prototypes we built in this paradigm, and discuss their performance.

Biography

Gowtham Kaki is an Assistant Professor in the Department of Computer Science at CU Boulder. His research interests are Programming Languages and Formal Methods with a focus on automated verification techniques for concurrent and distributed programs. Gowtham earned his Ph.D in Computer Science from Purdue University in 2019. He received several recognitions for his thesis work, including Google’s PhD Research Fellowship (2018), Purdue’s Maurice H. Halstead Award (2018), and his alma mater BITS Pilani’s 30-under-30 award (2019).