-
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 not silently corrupted. Is that a good assumption? Perhaps: Real data 1995 Checksums disagree 2000 …
-
The replicated state machine method of fault tolerance from 1980s
The first time I saw this method was when I went to work for Parallel Computer Systems, , later called Auragen, in the famous tech startup center of Englewood Cliffs, New Jersey. I commuted there from the East Village*. The company built a parallel computer based on Motorola 68000s with a replicated message bus. The bus guaranteed…
-
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 that essentially tells the followers what the values are. The challenges in such methods are…
-
RTLinux
-
IEEE 1588 PTP is a mess
IEEE 1588 was not designed for modern enterprise computer networks and contains many hacks to make it sort of work. The standard also suffers from being overly explicit on some things and overly unspecific on others. One marker of the flawed process is that IEEE 1588 transparent clocks don’t really comply with Ethernet standards because…
-
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 have a map α: X → Y where X is the set of finite sequences over X.…
-
Software quality at toyota
-
one way queues
Here’s some code for lock free queues for a single producer and single consumer. The code is designed for Intel multiprocessors with strong memory model. I don’t know what ARM offers these days. But the strong memory model for x86 means that the program doesn’t need any special synchronizing operations at all. All it needs…
-
Paxos and other consensus algorithms and the unaccountable love for asynchrony
I’ve been looking at Paxos and Raft and Zab and other algorithms that can loosely be called “consensus” algorithms because we want to see where we can improve distributed system operation with precision time synchronization or where we can offer novel features because of precision timing. Google’s Spanner database is an interesting example in this area but…