<story><title>Neat Algorithms: Paxos</title><url>http://harry.me/blog/2014/12/27/neat-algorithms-paxos/?hn=1</url></story><parent_chain><item><author>Retr0spectrum</author><text>Surely that means that none of the nodes will reach a concensus, so the cluster cannot be updated?</text></item><item><author>nacs</author><text>Ah, thanks for the response. I didn&amp;#x27;t realize the majority encompassed the entire cluster and not just a majority within the split.</text></item><item><author></author><text></text></item><item><author>nacs</author><text>Thanks the presentation, helps a lot.&lt;p&gt;Quick question though. On this slide ( &lt;a href=&quot;http://i.imgur.com/m02CMxx.png&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;i.imgur.com&amp;#x2F;m02CMxx.png&lt;/a&gt; ) it shows a network split condition and shows how the 2 split networks will eventually negotiate and the 3 node split wins because it had a majority while the 2 node side&amp;#x27;s uncommitted changes are thrown out.&lt;p&gt;What happens if the split happens right down the middle (3 active nodes on each side instead of the 2 and 3)? Wouldn&amp;#x27;t both sides elect leaders that both have majorities with committed data?</text></item><item><author>krat0sprakhar</author><text>This is up for debate but this[0], IMHO, is pretty much the gold standard of explaining distributed algorithms.&lt;p&gt;[0] - &lt;a href=&quot;http://thesecretlivesofdata.com/raft/&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;thesecretlivesofdata.com&amp;#x2F;raft&amp;#x2F;&lt;/a&gt;</text></item></parent_chain><comment><author>Chris_Newton</author><text>Isn’t that what we need with Raft, in order to guarantee reaching eventual consistency after reconciling any pending changes when a division into multiple partitions is healed?&lt;p&gt;For example, suppose we have two nodes and they are placed into separate partitions. If we allow an exact 50% share to count as a “majority” then both nodes can potentially continue to accept and acknowledge updates during the division, because each is capable of updating a majority of the nodes in the cluster (in this case, just itself, but the same argument applies if we have larger numbers of nodes in each half). However, when the division is healed, a simple check to see which leader node has the higher term count and allow its log to take precedence is no longer sufficient.&lt;p&gt;The problem is that we have violated the State Machine Safety guarantee described in the Raft paper (that is, we can have different nodes that have different committed entries at the same index in their respective logs). We now have no way to resolve the conflict, because those updates were already committed by some of the nodes in the cluster and have been acknowledged by their respective leader nodes, so now we can’t just append any extra committed log entries from one node to another node’s log to get back to a consistent state.</text></comment>
<story><title>Neat Algorithms: Paxos</title><url>http://harry.me/blog/2014/12/27/neat-algorithms-paxos/?hn=1</url></story><parent_chain><item><author>Retr0spectrum</author><text>Surely that means that none of the nodes will reach a concensus, so the cluster cannot be updated?</text></item><item><author>nacs</author><text>Ah, thanks for the response. I didn&amp;#x27;t realize the majority encompassed the entire cluster and not just a majority within the split.</text></item><item><author></author><text></text></item><item><author>nacs</author><text>Thanks the presentation, helps a lot.&lt;p&gt;Quick question though. On this slide ( &lt;a href=&quot;http://i.imgur.com/m02CMxx.png&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;i.imgur.com&amp;#x2F;m02CMxx.png&lt;/a&gt; ) it shows a network split condition and shows how the 2 split networks will eventually negotiate and the 3 node split wins because it had a majority while the 2 node side&amp;#x27;s uncommitted changes are thrown out.&lt;p&gt;What happens if the split happens right down the middle (3 active nodes on each side instead of the 2 and 3)? Wouldn&amp;#x27;t both sides elect leaders that both have majorities with committed data?</text></item><item><author>krat0sprakhar</author><text>This is up for debate but this[0], IMHO, is pretty much the gold standard of explaining distributed algorithms.&lt;p&gt;[0] - &lt;a href=&quot;http://thesecretlivesofdata.com/raft/&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;thesecretlivesofdata.com&amp;#x2F;raft&amp;#x2F;&lt;/a&gt;</text></item></parent_chain><comment><author>nacs</author><text>I assumed the same thing from that response.&lt;p&gt;Does the cluster just remain in a read-only mode during that time? Maybe someone else knows.</text></comment>