<story><title>In search of a simple consensus algorithm</title><url>http://rystsov.info/2017/02/15/simple-consensus.html</url></story><parent_chain></parent_chain><comment><author>ReidZB</author><text>The article abuses Kolmogorov complexity...&lt;p&gt;&amp;gt; When it is applied to the algorithms, it means that an algorithm with the shortest implementation is simpler.&lt;p&gt;That is misleading. Kolmogorov complexity is the length of the shortest program (in a pre-defined language) that produces a given object. So, if the &lt;i&gt;shortest program&lt;/i&gt; that produces Algorithm A is smaller than the &lt;i&gt;shortest program&lt;/i&gt; that produces Algorithm B, then the Algorithm A is less Kolmogorov-complex (&amp;quot;simpler&amp;quot;) than Algorithm A.&lt;p&gt;This does not mean you can take two existing implementations (in C, say) and compare the implementation length and declare one is &amp;quot;simpler,&amp;quot; unless you are claiming that both implementations are as short as possible. Since Kolmogorov complexity is not computable, that seems like a tall order.&lt;p&gt;Maybe they are right that Single-Decree Paxos is simpler (either in the sense of Kolmogorov complexity or in some other sense, who knows), but invoking Kolmogorov complexity here seems totally unwarranted -- it doesn&amp;#x27;t add anything substantive.</text></comment>
<story><title>In search of a simple consensus algorithm</title><url>http://rystsov.info/2017/02/15/simple-consensus.html</url></story><parent_chain></parent_chain><comment><author>irfansharif</author><text>It is my understanding that the motivation in seeking out consensus algorithms with strong leaders (or equivalent) as opposed to horizontally weighted peer-to-peer ones is due to the performance penalty imposed by the latter in the general case. Structuring the protocol to be a dissemination from the &amp;#x27;leader&amp;#x27; node down to the followers as opposed to a bottom-up approach fares better when your leader is long-lived, circumventing the cost of determining &amp;#x27;consensus&amp;#x27; every single time. It&amp;#x27;s readily apparent that this would lend to a performance penalty in the pathological case, as is demonstrated here, when the leader node is taken down repeatedly - but I&amp;#x27;m skeptical if this is true for workloads that systems like coreos&amp;#x2F;etcd, cockroachdb&amp;#x2F;cockroach were intended to handle.</text></comment>