Single Value Consensus Paxos Algorithm

Signle Value Consensus是这样一个问题，假设有许多Process (P1, P2 … Pn)，每个Process可以Propose任意value，那么要求实现这样一个算法，使得这N个Process可以达成一致，即Decide on a same signle value. 达成一致本来不难，不过如果考虑到各种可能出现的故障，问题就复杂了。比如Process Failure, Message loss etc. Consensus问题在完全异步系统（Asynchronous）是无解的(FLP Impossibility)，这里的系统假设是Partitialy Synchronous System. （对这两个系统假设的定义详见之前的博文）

Paxos是算法原作者Leslie Lamport提出来的一个假想希腊城邦名，更详细的故事背景可见原论文(1998)The Part-Time Parliament.

这个算法以难懂和难正确实现出名…我在这门课的最后一周卡了快一个月，也不是很好地理解它= =。Lamport 2001年还重写了篇论文，叫Paxos Made Simple，然而还是一样很难懂…

算法基本照着课程第五周给的这个PDFAlgorithms – Consensus in the Fail-Noisy Model 翻译成Scala就好了。我实现时遇到两个坑，

case BEB_Deliver(src, acc: Accept) => handle {
    // ...
    if (promisedBallot <= acc.acceptBallot) 
    //...
}

我把=漏掉了，结果算法无法terminate。另一个是

case PL_Deliver(src, accAck: Accepted) => handle  {
    // ...
    val needed = math ceil ((numProcesses+1)/2.0);
    if (numOfAccepts  == needed) 
    // ...
}    

我一开始直接写成if (numOfAccepts == ((numProcesses+1)/2)) ，结果决定值总是不一致。

算法的难点是理解那些edge case的出现导致了我们必须提出remedy solution。最简单的办法是直接指定一个 central acceptor，由它来决定最后是什么value。但是如果这个central acceptor挂了，那我们的算法也就挂了。

所以做出的一个改进就是指定a majority set of acceptor，只要多数Process正常，这个算法就能正常。

但是新的坑又来了… (未完待续= =。。。)

加了一些Print语句，代码通过测试的trace长这样子：

SLF4J: Class path contains multiple SLF4J bindings.
SLF4J: Found binding in [jar:file:/usr/zeppelin/interpreter/kompics/slf4j-log4j12-1.7.10.jar!/org/slf4j/impl/StaticLoggerBinder.class]
SLF4J: Found binding in [jar:file:/usr/zeppelin/zeppelin-interpreter/target/lib/slf4j-log4j12-1.7.10.jar!/org/slf4j/impl/StaticLoggerBinder.class]
SLF4J: See http://www.slf4j.org/codes.html#multiple_bindings for an explanation.
SLF4J: Actual binding is of type [org.slf4j.impl.Log4jLoggerFactory]
rank 1 - (BEB_Broadcast) a Prepare msg - (1, 1)
rank 1 - (C_Propose) Propose a value - 1941228553
rank 2 - (BEB_Broadcast) a Prepare msg - (1, 2)
rank 2 - (C_Propose) Propose a value - 44682924
rank 3 - (BEB_Broadcast) a Prepare msg - (1, 3)
rank 3 - (C_Propose) Propose a value - -1617181610
rank 1 - (PL_Send) Send a Promise ((1,1), (0,0), None) to dest TAddress(/192.168.2.1:1000)
rank 4 - (PL_Send) Send a Promise ((1,3), (0,0), None) to dest TAddress(/192.168.2.3:1000)
rank 1 - (PL_Send) Send a Promise ((1,2), (0,0), None) to dest TAddress(/192.168.2.2:1000)
rank 3 - (PL_Send) Send a Promise ((1,3), (0,0), None) to dest TAddress(/192.168.2.3:1000)
rank 2 - (PL_Send) Send a Promise ((1,1), (0,0), None) to dest TAddress(/192.168.2.1:1000)
rank 2 - (PL_Send) Send a Promise ((1,2), (0,0), None) to dest TAddress(/192.168.2.2:1000)
rank 3 - (BEB_Broadcast) a Accept ((1, 3), proposedValue : Some(-1617181610))
rank 2 - (BEB_Broadcast) a Accept ((1, 2), proposedValue : Some(44682924))
rank 1 - (BEB_Broadcast) a Accept ((1, 1), proposedValue : Some(1941228553))
rank 4 - (PL_Send) Send a Accepted (Accept((1,3),-1617181610)) to dest TAddress(/192.168.2.3:1000)
rank 2 - (PL_Send) Send a Nack (Accept((1,1),1941228553)) to dest TAddress(/192.168.2.1:1000)
rank 3 - (PL_Send) Send a Accepted (Accept((1,3),-1617181610)) to dest TAddress(/192.168.2.3:1000)
rank 1 - (PL_Send) Send a Nack (Accept((1,1),1941228553)) to dest TAddress(/192.168.2.1:1000)
rank 1 - (PL_Send) Send a Accepted (Accept((1,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 2 - (PL_Send) Send a Accepted (Accept((1,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 1 - (BEB_Broadcast) a Prepare msg - (2, 1)
rank 2 - (PL_Send) Send a Promise ((2,1), (1,2), Some(44682924)) to dest TAddress(/192.168.2.1:1000)
rank 1 - (PL_Send) Send a Promise ((2,1), (1,2), Some(44682924)) to dest TAddress(/192.168.2.1:1000)
rank 1 - (BEB_Broadcast) a Accept ((2, 1), proposedValue : Some(1941228553))
rank 1 - (PL_Send) Send a Accepted (Accept((2,1),1941228553)) to dest TAddress(/192.168.2.1:1000)
rank 2 - (PL_Send) Send a Accepted (Accept((2,1),1941228553)) to dest TAddress(/192.168.2.1:1000)
rank 3 - (PL_Send) Send a Nack (Prepare((1,1))) to dest TAddress(/192.168.2.1:1000)
rank 4 - (PL_Send) Send a Nack (Prepare((1,1))) to dest TAddress(/192.168.2.1:1000)
rank 3 - (PL_Send) Send a Nack (Prepare((1,2))) to dest TAddress(/192.168.2.2:1000)
rank 4 - (PL_Send) Send a Nack (Prepare((1,2))) to dest TAddress(/192.168.2.2:1000)
rank 1 - (PL_Send) Send a Nack (Prepare((1,3))) to dest TAddress(/192.168.2.3:1000)
rank 2 - (PL_Send) Send a Nack (Prepare((1,3))) to dest TAddress(/192.168.2.3:1000)
rank 3 - (BEB_Broadcast) a Prepare msg - (2, 3)
rank 2 - (BEB_Broadcast) a Prepare msg - (2, 2)
rank 3 - (PL_Send) Send a Promise ((2,2), (1,3), Some(-1617181610)) to dest TAddress(/192.168.2.2:1000)
rank 2 - (PL_Send) Send a Promise ((2,2), (2,1), Some(1941228553)) to dest TAddress(/192.168.2.2:1000)
rank 1 - (PL_Send) Send a Promise ((2,2), (2,1), Some(1941228553)) to dest TAddress(/192.168.2.2:1000)
rank 4 - (PL_Send) Send a Promise ((2,2), (1,3), Some(-1617181610)) to dest TAddress(/192.168.2.2:1000)
rank 1 - (PL_Send) Send a Nack (Accept((1,3),-1617181610)) to dest TAddress(/192.168.2.3:1000)
rank 2 - (PL_Send) Send a Nack (Accept((1,3),-1617181610)) to dest TAddress(/192.168.2.3:1000)
rank 2 - (PL_Send) Send a Promise ((2,3), (2,1), Some(1941228553)) to dest TAddress(/192.168.2.3:1000)
rank 4 - (PL_Send) Send a Promise ((2,3), (1,3), Some(-1617181610)) to dest TAddress(/192.168.2.3:1000)
rank 3 - (PL_Send) Send a Promise ((2,3), (1,3), Some(-1617181610)) to dest TAddress(/192.168.2.3:1000)
rank 1 - (PL_Send) Send a Promise ((2,3), (2,1), Some(1941228553)) to dest TAddress(/192.168.2.3:1000)
rank 3 - (PL_Send) Send a Nack (Accept((1,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 4 - (PL_Send) Send a Nack (Accept((1,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 3 - (PL_Send) Send a Nack (Accept((1,1),1941228553)) to dest TAddress(/192.168.2.1:1000)
rank 4 - (PL_Send) Send a Nack (Accept((1,1),1941228553)) to dest TAddress(/192.168.2.1:1000)
rank 2 - (BEB_Broadcast) a Accept ((2, 2), proposedValue : Some(44682924))
rank 3 - (BEB_Broadcast) a Accept ((2, 3), proposedValue : Some(-1617181610))
rank 4 - (PL_Send) Send a Nack (Accept((2,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 2 - (PL_Send) Send a Nack (Accept((2,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 1 - (PL_Send) Send a Nack (Accept((2,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 3 - (PL_Send) Send a Nack (Accept((2,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 1 - (PL_Send) Send a Accepted (Accept((2,3),-1617181610)) to dest TAddress(/192.168.2.3:1000)
rank 2 - (PL_Send) Send a Accepted (Accept((2,3),-1617181610)) to dest TAddress(/192.168.2.3:1000)
rank 3 - (PL_Send) Send a Accepted (Accept((2,3),-1617181610)) to dest TAddress(/192.168.2.3:1000)
rank 2 - (BEB_Broadcast) a Prepare msg - (3, 2)
rank 3 - (PL_Send) Send a Nack (Prepare((2,1))) to dest TAddress(/192.168.2.1:1000)
rank 4 - (PL_Send) Send a Nack (Prepare((2,1))) to dest TAddress(/192.168.2.1:1000)
rank 4 - (PL_Send) Send a Accepted (Accept((2,3),-1617181610)) to dest TAddress(/192.168.2.3:1000)
rank 1 - (PL_Send) Send a Promise ((3,2), (2,3), Some(-1617181610)) to dest TAddress(/192.168.2.2:1000)
rank 4 - (PL_Send) Send a Promise ((3,2), (2,3), Some(-1617181610)) to dest TAddress(/192.168.2.2:1000)
rank 3 - (BEB_Broadcast) a Decided (Some(-1617181610))
rank 2 - (PL_Send) Send a Promise ((3,2), (2,3), Some(-1617181610)) to dest TAddress(/192.168.2.2:1000)
rank 3 - (PL_Send) Send a Promise ((3,2), (2,3), Some(-1617181610)) to dest TAddress(/192.168.2.2:1000)
rank 1 - (BEB_Broadcast) a Prepare msg - (3, 1)
rank 2 - (BEB_Broadcast) a Accept ((3, 2), proposedValue : Some(44682924))
rank 1 C_Decide on value - Decided(Some(-1617181610))
rank 2 C_Decide on value - Decided(Some(-1617181610))
rank 3 C_Decide on value - Decided(Some(-1617181610))
rank 3 - (PL_Send) Send a Nack (Accept((2,1),1941228553)) to dest TAddress(/192.168.2.1:1000)
rank 4 - (PL_Send) Send a Nack (Accept((2,1),1941228553)) to dest TAddress(/192.168.2.1:1000)
rank 4 - (PL_Send) Send a Nack (Prepare((3,1))) to dest TAddress(/192.168.2.1:1000)
rank 3 - (PL_Send) Send a Nack (Prepare((3,1))) to dest TAddress(/192.168.2.1:1000)
rank 2 - (PL_Send) Send a Nack (Prepare((3,1))) to dest TAddress(/192.168.2.1:1000)
rank 1 - (PL_Send) Send a Nack (Prepare((3,1))) to dest TAddress(/192.168.2.1:1000)
rank 4 - (PL_Send) Send a Accepted (Accept((3,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 4 C_Decide on value - Decided(Some(-1617181610))
rank 3 - (PL_Send) Send a Accepted (Accept((3,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 1 - (PL_Send) Send a Accepted (Accept((3,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 2 - (PL_Send) Send a Accepted (Accept((3,2),44682924)) to dest TAddress(/192.168.2.2:1000)
rank 2 - (BEB_Broadcast) a Decided (Some(44682924))

Single Value Consensus Paxos Algorithm

Similar Posts

Comments