Google Scholar tells me that “Why Functional Programming Matters” was published in 1989 and has been cited over 1000 times. Here’s a quote. Recall that a complete functional program is just a function from its input to its output. If
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
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
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
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
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
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
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
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
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