(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 <jma...@redhat.com>
Sent: Sunday, July 19, 2020 12:07 AM
To: Xue, Ying <ying....@windriver.com>
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 <jma...@redhat.com>
Sent: Saturday, July 11, 2020 2:29 AM
To: Xue, Ying <ying....@windriver.com>
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
_______________________________________________
tipc-discussion mailing list
tipc-discussion@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/tipc-discussion
