Do we have a formula to calculate the converging time of gossip?

[Heng Chang]

Hi, Do we have a formula to calculate the converging time (how many rounds that all the nodes receive a gossip message) for gossip protocol?

I guess the Serf Convergence Simulator(https://www.serf.io/docs/internals/simulator.html) is based on some formulas, if so, can anyone guide me for these formulas or give some references?

I found a formula without any deducing process in the following link(http://www.infoq.com/cn/articles/principle-and-impleme-of-de-centering-system-in-serf) .

Based on it, I deduced a formula T= 2ln(N+1)/[k(1-p1)(1-p2)], where N is the total number of nodes and should be big enough, k is the fanout, p1 is the packet loss rate and p2 is the node failure rate.

Actually, I compared this formula with Serf Convergence Simulator and it seems that Serf Convergence Simulator has a similar formula like T= (2ln(N+1)+10)/[k(1-p1)(1-p2)];

I am not sure about my math and the formula. Can anyone give some guidelines or comments?

Thanks and Best Regards,

[Armon Dadgar]

Hey Heng,

Here is the math used by the simulator https://github.com/hashicorp/serf/blob/master/website/source/assets/javascripts/_simulator.js#L137

For the most part, you can use the formulas for epidemic gossip, and plugin the Serf defaults (200msec between rounds, fanout of 3, 7x rebroadcast).

Hope that helps!

Best Regards,

Armon Dadgar

--
This mailing list is governed under the HashiCorp Community Guidelines - https://www.hashicorp.com/community-guidelines.html. Behavior in violation of those guidelines may result in your removal from this mailing list.
 
GitHub Issues: https://github.com/hashicorp/serf/issues
IRC: #serfdom on Freenode
---
You received this message because you are subscribed to the Google Groups "Serf" group.
To unsubscribe from this group and stop receiving emails from it, send an email to serfdom+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/serfdom/b2908a3c-90f4-4059-b46a-1c3a0c38b722%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Heng Chang]

Hi, Armon, Thanks for your help.

According to your Simulator math, I deduced a formula T= [2ln(N+1)+2ln(p/(1-p))/[k(1-p1)(1-p2)], where N is the total number of nodes, k is the fanout, p1 is the packet loss rate, p2 is the node failure rate and p=n/N is the Converge rate(n is the total number of the nodes which have gotten the gossip).

If assume p=0.99, then T=[2ln(N+1)+9.19]/[k(1-p1)(1-p2)];

If aasume p=(N-1)/N, all(more thant N-1) nodes will get the gossip, then T=2ln(N*N-1);

Still, not very sure about my math and the formula:)

 Moreover, according to the memberlist source code, as my understanding, each node will send a gossip for at most RetransmitMult*Log10(N+1)=[RetransmitMult*ln(N+1)/ln10] times. Here lnx means the natural logarithm of x.

I wonder how do you decide to choose RetransmitMult?  

Thanks and Best Regards,

在 2017年8月5日星期六 UTC+8上午12:24:03，Armon Dadgar写道：

[Armon Dadgar]

Hey Heng,

The choice of RetransmitMult is mostly a heuristic, and we played around with different values.

The tradeoff is between bandwidth and reliable delivery, but given the small message sizes we opted for higher confidence of delivery.

Best Regards,

Armon Dadgar

To view this discussion on the web visit https://groups.google.com/d/msgid/serfdom/70857773-e645-4d89-8511-dc2844e6d9d8%40googlegroups.com.

[Heng Chang]

Hi, Armon,

one more question is that, why not sending multi UDP packets when the total size of the gossip broadcasts queue is larger than 1400 bytes of the UDP MTU?  

As my understanding, sending only one UDP packet in this situation will leave some messages unsent in the queue for a round. If the cluster is big enough, I think this will be a common situation, then the converge time will be longer or even much longer than we expected especially for the User data messages.    

在 2017年8月8日星期二 UTC+8上午12:28:58，Armon Dadgar写道：

[Armon Dadgar]

Heng,

It was an early design decision to make the bandwidth use more predictable. Either messages need to be queued or you need to use an unbounded number of messages. In practice the message rate hasn't been a concern for most users. Messages are queued and prioritized as last in first out (LIFO), so the systems remains timely.

Hope that helps!

Best Regards,

Armon Dadgar

Sent from Outlook Mobile

---

From: ser...@googlegroups.com <ser...@googlegroups.com> on behalf of Heng Chang <scutp...@gmail.com>
Sent: Tuesday, August 8, 2017 2:31:54 AM
To: Serf
Cc: scutp...@gmail.com
Subject: Re: [serf] Do we have a formula to calculate the converging time of gossip?

 

To view this discussion on the web visit https://groups.google.com/d/msgid/serfdom/3a291914-2a95-4409-a178-28f152f45450%40googlegroups.com.

[Heng Chang]

Hi, I see, thanks a lot!

在 2017年8月9日星期三 UTC+8上午2:44:37，Armon Dadgar写道：