Modular Software Upgrades for Distributed Systems

Abstract. Upgrading the software of long-lived, highly-available distributed sys-tems is di fficult. It is not possible to upgrade all the nodes in a system at once,since some nodes may be unavailable and halting the system for an upgrade is unacceptable. Instead, upgrades must happen gradually, and there may be longperiods of time when di fferent nodes run different software versions and need tocommunicate using incompatible protocols. We present a methodology and infrastructure that make it possible to upgrade distributed systems automaticallywhile limiting service disruption. We introduce new ways to reason about correctness in a multi-version system. We also describe a prototype implementationthat supports automatic upgrades with modest overhead