2
$\begingroup$

I have a group with n members. These are distributed members. It is basically a group chat. A new member is added to the group and the existing members are informed about this.

Now I want the new member to obtain some information about the group that the existing members all know. This could be the name of the group. There is no centralised place where this information can be obtained. Also, messages sent in the group will go to every member of the group.

My current implementation is that all the existing members send the information to the new member, but this is causing everyone to receive many messages. I would like the number of messages to be as low as possible, which I guess would mean that one message should be enough.

I cannot just make the member with the lowest ID be the one to send the message, as that person might not be online.

So, is this problem, a problem with a known solution? And what might that be?

I hope the explanation makes sense.

$\endgroup$
13
  • 3
    $\begingroup$ The model doesn't have enough details to answer the question correctly. One suggestion is that every member of the group draws a random number from $1$ to, let's say $n^2$. Then they wait for that many seconds before they send a message. They don't send a message if someone else already sent one. $\endgroup$
    – Pål GD
    Nov 25, 2022 at 10:28
  • 1
    $\begingroup$ "the existing members are informed about this": how, if there is no centralized place ? $\endgroup$
    – user16034
    Nov 25, 2022 at 10:51
  • $\begingroup$ Can't you get the lowest ID of the online persons ? $\endgroup$
    – user16034
    Nov 25, 2022 at 10:52
  • $\begingroup$ @YvesDaoust No users knows who is online. $\endgroup$
    – Kobski
    Nov 25, 2022 at 11:13
  • 1
    $\begingroup$ So the server can arrange these transfers. Or the server could act as a group member. $\endgroup$
    – user16034
    Nov 25, 2022 at 12:38

1 Answer 1

2
$\begingroup$

Let's say that the expected time a message takes in transit is $t$, and typically $ t \leq 100\;\text{ms}$.

Your group has $n$ members. When a new member enters the group, each existing member draws an integer $w_i$ at random from $[1, q \cdot n]$ for some $q \geq 1$. Then each member waits for $t \cdot w_i \; \text{ms}$. If no message has been sent to the group, then that member sends a message.

According to the answer by Raskolnikov on maths.sx, the probability that more than one member will be chosen to send a message is $$ 1- \frac{1}{ q (e^{1/q} - 1) }, $$ which interestingly does not depend on $n$.

If you choose $q$ to be large (e.g. 100), then the probability that two members will be chosen to send the message is very small (<0.5%), but the waiting time will be larger. If you choose $q$ to be small (e.g. 5), the probability will be larger, but still less than 10%, and the waiting time will be much smaller.

Ps., compute the probability of a collision using

def prob_coll(q):
    return 1 - (1 / (q * (math.e ** (1 / q) - 1)))
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.