Logical clock systems and the challenges of autonomous operation

Abstract

Causality plays a central role as a building block in solving important problems in distributed systems, such as replication, debugging, group communication and global snapshots. To be useful, causality must be realised by actual mechanisms that can track it and encode it.

Existing causality tracking mechanisms, such as vector clocks and version vectors, rely on mappings from globally unique identifiers to integer counters. In a system with a well known set of entities these identifiers can be pre-configured and given distinct positions in a vector or distinct names in a mapping. Identity management is more problematic in dynamic systems, with a large and highly variable number of entities, being worsened when network partitions occur. Present solutions for causality tracking are not appropriate to these increasingly common scenarios.

This work introduces novel causality tracking mechanisms that can be used in scenarios with a dynamic number of entities. These allow completely decentralised creation of entities (processes or replicas) with no need for global identifiers or global coordination. These mechanisms have a variable size representation that adapts automatically to the number of entities, growing or shrinking appropriately.

This book is the published version of the second half of my PhD thesis, and focus its discourse on causality tracking for disconnected and semi-connected distributed systems.