The Chang-Maxemchuk algorithm (US Patent 4,725,834 ) solves atomic broadcast (and in-order broadcast) problems for distributed networks in a far simpler and more efficient way than some popular alternatives. In fact, the obscurity of this method is hard to understand given the
Distributed consensus and network reliability
All of the distributed consensus algorithms I have been reviewing recently (Paxos, Raft, Zab, Chang Maxemchuck, Viewstamped, … ) are based on a number of assumptions about the network environment, including the assumption that messages may be lost but are
circularity problems in distributed consensus
Distributed consensus involves organizing a collection of independent agents – processes or network sites – to agree on some value or sequence of values. Many distributed consensus methods depend on a leader-follower scheme in which the leader is an agent
Making Paxos face facts
Replaced by Paxos Demystified. Lamport’s “Paxos Made Simple” paper is notoriously hard to understand but at least part of the difficulty is that the algorithm changes radically in the middle of the presentation. The first part of the paper presents a
The difference between unspecified, undefined, and non-deterministic
There is too much confusion in the “formal methods” computer science literature between these three different terms. Let me start with what this means for a state machine and then move on to engineering objects such as threads. Suppose we
Keynes apology
The composition of this book has been for the author a long struggle of escape, and so must the reading of it be for most readers if the author’s assault upon them is to be successful,—a struggle of escape from
Process algebra is based on a misunderstanding of automata theory
Robin Milner’s book Communication and Concurrency involves a take on state machines that is fundamentally incorrect. “Now in standard automata theory, an automaton is interpreted as a language i.e. as a set of strings over the alphabet.“ That’s not at
More on Fischer, Lynch, Patterson and the parrot theorem.
I’m thinking about distributed consensus algorithms, timestamping, and databases and if you read that literature you will see many references to the Fischer, Lynch, Paterson “theorem”. Google Scholar tells me the paper has been cited more than 4500 times. The theorem
Theories of abstract automata – Arbib
We have said that automata theory deals with the realization of partial functions F: X* —» Y* by some finitely specifiable substrate. Before we specify in more detail the forms (of which the Turing machine is one) of substrate which
Kirkhart’s conjecture
Is that there is some insight into the nature of primes that comes from considering the classes of numbers that share the same set of prime factors. For example 2x3x5 = 30, 4x3x5 = 60, 2x9x5 = 90, 2x3x25 =