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
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
See the current pdf in Arxiv 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
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 =
RTLinux early paper from 20 years ago
An early RTLinux paper with Michael Barabanov. real_time_1996 Only 20 years later, the idea is now not too scary. Real-Time Linux Michael Barabanov Victor Yodaiken March 3, 1996 1 Introduction If you wanted to control a camera or a