On the complexity of basic abstractions to implement consensus

In this paper we study an important subset of these objects: adopt-commit [1], conflict-detector [2], value-splitter [3] and grafarius [4]. We show that while some of these objects (adopt-commits and conflict-detectors) ensure a superset of the properties ensured by the others (value-splitter and grafarius), their space and individual step complexity is the same if implemented anonymously (the algorithm does not use process IDs). On the other hand, adopt-commit and conflict-detector objects have a larger complexity if we consider non anonymous implementations.