Publication

Generalizing State Machine Replication

Rachid Guerraoui
2010
Reports

Abstract

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 ramiﬁcation of our main result, derived by considering the state machines to be interacting read-write threads, is a ﬂagpole 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.

Official source

https://infoscience.epfl.ch/entities/publication/c024eef7-d3e0-498b-8af2-168606e46494

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Rachid Guerraoui
2010
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/c024eef7-d3e0-498b-8af2-168606e46494

About this result

Related concepts (23)

Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition.

Moore machine

In the theory of computation, a Moore machine is a finite-state machine whose current output values are determined only by its current state. This is in contrast to a Mealy machine, whose output values are determined both by its current state and by the values of its inputs. Like other finite state machines, in Moore machines, the input typically influences the next state. Thus the input may indirectly influence subsequent outputs, but not the current or immediate output. The Moore machine is named after Edward F.

Mealy machine

In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs. This is in contrast to a Moore machine, whose output values are determined solely by its current state. A Mealy machine is a deterministic finite-state transducer: for each state and input, at most one transition is possible. The Mealy machine is named after George H. Mealy, who presented the concept in a 1955 paper, "A Method for Synthesizing Sequential Circuits".

Related publications (8)

Generalizing State Machine Replication

Chat with Graph Search

Partitioning Complete Geometric Graphs on Dense Point Sets Into Plane Subgraphs

Barriers to the net zero target in personal mobility

Multiple criteria design analysis of a compensation basin to mitigate hydro-pealink