Generalizing State Machine Replication

We show that, with k-set consensus, any number of processes can emulate k state machines of which at least one progresses. This generalizes the celebrated universality of consensus which enables to build a state machine that always progresses. Besides some interesting extensions and even potential “practical” applications, theoretically, a fundamental ramification of our main result, derived by considering the state machines to be interacting read-write threads, is a flagpole to the thesis that distributed computing is all about wait-freedom. We indeed show that the set of tasks that are read-write solvable “k-concurrently” , i.e., when concurrency goes below k, is the same set of tasks that are read-write solvable with k-set consensus.