Collective consistency work in progress

Abstract

Collective consistency is a weak form of agreement in which processes try to reach a common view of group membership under a rather relaxed definition of 'common'. This paper provides a knowledge-based specification for a simple protocol for the collective consistency. The implementation of this specification is sound if it provides a function that returns a Boolean in the place of the knowledge operator and its argument such that, when the function returns true, the argument is actually true in the set of possible executions provided by the system in which each participant uses this implementation. Extremely fast, nontrivial, sound implementations are presented.