# Séminaire REGAL

# Generalized Universality

05/28/2013

Speaker(s) : Rachid GUERRAOUI (EPFL)

Replicated state machine is a fundamental computing construct for it essentially makes a distributed system emulate a, highly available, centralized one using a consensus abstraction through which processes agree on common decisions. The idea is at the heart of the fault-tolerance of most data centers today.

Any sequential object is modeled by a state machine that can be replicated over all processes of the system and accessed in a wait-free manner: we talk about the universality of the construct and of its underlying consensus abstraction. Yet, consensus is just a special case of a more general abstraction, k-set consensus, where processes agree on at most k different decisions. It is natural to ask whether there exists a generalization of state machine replication with k-set agreement, for otherwise distributed computing would not deserve the aura of having an underpinning Theory as 1 (k-set consensus with k=1) would be special.

The talk will recall the classical state machine replication construct and show how, using k-set consensus as an underlying abstraction, the construct can be generalized to implement k state machines of which at least one makes progress, generalizing in a precise sense the very notion of consensus universality.

franck.petit (at) nulllip6.fr