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 ids can be preconfigured and given distinct positions in a vector or distinct names in a mapping. Id management is more problematic in dynamic systems, with high churn rate, that is, with highly variable number of entities. These are issues that need to be addressed in systems such as Amazon Dynamo. An alternative to explicit id management is to explore probabilistic approaches that avoid ids. This thesis aims to evaluate the use of a variant of bloom filters for probabilistic causality tracking.

Note: This theme has potential funding under the FCT project CASTOR, to begin in early 2010.

Supervision: CBM, PSA.