Distributed systems according to Lamport?

Question

I need some clarification over the following quotation of Leslie Lamport:

A distributed system can be described as a particular sequential state machine that is implemented with a network of processors. The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system.

I see how a distributed system can be modeled as the product of several particular sequential state machines.

I understand that by totally ordering input requests, one can duplicate a given sequential state machine over several computers, and make sure that all input requests are processed in the same order at every computer, and thus ensuring that the individual local states are coherent.

What I don't understand is how this mechanism is sufficient to implement ANY distributed system. At least it's sufficient to duplicate a sequential state machine, but isn't that a very particular case of a distributed system?

Answer 1

My interpretation of this quote is that if we consider the whole distributed system as a black box containing multiple local processors, then when we send input requests to this box, the whole box moves to another state even though we don't know what that next state is (particularly in non-deterministic state machines), but we are sure that there's no inconsistent interpretation within the box.

Actually input requests could be thought of as an external node that does atomic broadcast to all internal nodes (within the box). This type of broadcast ensures us that all internal nodes receive messages in the same order, so all local state machines move to their next states. If we define state of the whole system as a set of all internal local states, so whenever we receive an atomic broadcast (i.e. input request), our system's state moves to a next state depending on the order of messages that all internal nodes agree on. Hence, each different order leads us to a non-deterministic destination (the next state) in the state machine of the whole system.

Therefore, total ordering is sufficient to model a distributed state machine. However in some applications some more properties might be needed, for instance, FIFO ordering, causal ordering, etc.

Answer 2

I don't think that quote trying to claim that this is necessarily the only possible definition of distributed system. It's one way to think about distributed systems that will often apply. For instance, if there's a single interface for interacting with the distributed system (so that the inputs and outputs can be totally ordered, as described in the quotation), then from an external perspective we can think of the entire system as implementing a single state machine.

---

A side remark. I don't think it's saying: given a sequential state machine, we can implement it in a distributed system (by replication, consensus protocols, etc.). Instead, I think it's saying the following: given a distributed system, its externally observable behavior could be described by a sequential state machine (e.g., the distributed system could be replaced by a non-distributed, sequential system that has the same input-output behavior).