Re: [tipc-discussion] TIPC/RAFT?

[Jon M. <jm...@re...>]

(adding tipc-dek and tipc-discussion to thread)


On 7/21/20 6:04 AM, Xue, Ying wrote:
> Hi Jon,
>
> Exactly, when I learned Raft, I was always thinking how Raft and TIPC existing link/service discovery protocol can smoothly work together. Raft is a centralization consensus protocol. As you reminded below, it did match our TIPC philosophy indeed because TIPC is more close to a decentralization consensus protocol.
>
> After search, I found the famous decentralization consensus protocols include:
> https://en.wikipedia.org/wiki/Gossip_protocol
I studied the Gossip protocol before I implemented my neighbor 
monitoring ("Overlapping Ring Monitoring") algorithm. The fact is, that 
algorithm could just as well have been called a "A Biased Gossip Type 
Neighbor Monitor Algorithm", because that is what it is. In my view, 
regular Gossip is not suitable for TIPC because convergence times in 
large clusters typically become too long, and if anything changes during 
the convergence period, it will always struggle to catch up.
Also, consensus in the RAFT/PAXOS meaning is that changes in the cluster 
state must be reported with exactly the same events in exactly the same 
order on all nodes. I don't think Gossip can guarantee that any more 
than current TIPC can.
> https://en.wikipedia.org/wiki/Proof_of_work
This one seems to be used by Bitcoin. Looks interesting.
There are also a few others worth studying:
https://www.geeksforgeeks.org/consensus-algorithms-in-blockchain/


///jon

>
> It really worth learning them and I will try to research and understand which is more suitable for our case.
>
> By the way, I have to go home to take care of my kid and I could attend our today's meeting. If I have some new finding or understanding, I will keep updating.
>
> Thanks,
> Ying
>
> -----Original Message-----
> From: Jon Maloy <jm...@re...>
> Sent: Sunday, July 19, 2020 12:07 AM
> To: Xue, Ying <Yin...@wi...>
> Subject: Re: TIPC/RAFT?
>
> Hi Ying,
> I may be ranting now...
> I know that blockchain technologies (Bitcoin, Ethereum etc.) also can be used to implement consensus algorithms. Furthermore, those are completely decentralized and very scalable, something that fits much better into the TIPC philosophy than the leader electing algorithms of Paxos and Raft.
> It might be worth learning more about this before embarking on any major effort to re-implement Raft.
> I don't know much about blockchains yet, so I have no clue if this is at all feasible regarding code volumes, consensus times and other properties, but it should at least be considered before any other track is selected.
> I will try to read up on this on my side.
>
> Regards
> ///jon
>
>
> On 7/15/20 11:10 AM, Xue, Ying wrote:
>> Hi Jon,
>>
>> Raft protocol is much more complex than my initial image. The complexity mainly comes from: 1.Raft protocol itself is quite complex, so it's not very easy to totally understand it in a very detailed way; 2. Implementing a raft consensus algorithm might not be very difficult, but making sure its implementation's quality reaches an industrial criteria level is very difficult. However, for a consensus protocol, it must ensure it can work very well in any kinds of different conditions, otherwise, some distributed values become inconsistent.
>>
>> When it comes to this implementation (https://github.com/willemt/raft), I took a lot time to study, validate and understand its code so far. Although I have make all test cases contained in this implementation passed, the scenarios covered by these test cases are quite basic particularly compared to test cases included in etcd (https://github.com/etcd-io/etcd/tree/master/raft). Even in its code, it clearly comments some corner cases haven't handled yet.
>>
>> In my previous plan, I wanted to take shortcuts so that I can quickly port the implementation into Linux kernel, but it was found it's very difficult to properly adapt it into kernel space if I couldn't totally understand Raft protocol itself, which wasted my lots of time.
>>
>> Currently I have to study the following two papers:
>> https://raft.github.io/raft.pdf
>> https://github.com/ongardie/dissertation/blob/master/stanford.pdf
>>
>> While reading and understanding the papers, I am researching the code and test cases of "etcd", which can help to have a much deeper understanding of the protocol itself. Honestly, I still don't have a very well understanding for the protocol. When I read paper, I felt I had a very good understanding for some parts of the protocol, but when I came back to research its implementations, I lost again and again.
>>
>> With my understanding of the protocol becoming deeper and deeper, more and more concerns with the quality of https://github.com/willemt/raft, appear in my mind. In sum, I need more time to evaluate its quality and then consider whether we can use it as a  base to implement raft protocol in TIPC stack or if it's possible for us to well implement the protocol in kernel space within a not very long time.
>>
>> Although I have to admit studying and even implementing the protocol is a pretty challenging thing, I am still quite interested in continuing working on this topic.
>>
>> Thanks,
>> Ying
>>
>> -----Original Message-----
>> From: Jon Maloy <jm...@re...>
>> Sent: Saturday, July 11, 2020 2:29 AM
>> To: Xue, Ying <Yin...@wi...>
>> Subject: TIPC/RAFT?
>>
>> Hi Ying,
>> Since I haven't had any news from you for a while, I was just getting curious.
>> Did you have any time to look into the RAFT implementation references I sent you?
>> Do you have any thougths about this?
>>
>> BR
>> ///jon
>>