First of all, thank you very much. It took quite some time to digest your advice :)

A "message - ACK - ACK-to-ACK" model represents a dialog very well. Combining sending messages with synchronisation attempts (Hi Bob, my version of dialog between us consists of 1239 messages, there's a new one attached: "..." - Hi Alice, now I have 1239 messages too, thanks!) takes care of the case when Bob had had one device with the message from Alice and the device is lost: they'll sync it next time any of them sends a message to the other.

To speed up the synchronisation process in common cases the ability to "suggest" messages may be useful. For example, when node Ak has just received a new message from Ai and it wants to forward it to another node Al, Ak can't be sure that Al doesn't have this message yet (maybe Al had been contacted by Ai, too); so Ak launches the synchronisation algorithm and suggests (sends the messageID) that the missing message (if any) may be the new one; if Al doesn't have a message with this ID, it requests the message and solves the problem, at least partially; if not, that's ~20 bytes wasted. I even thought that the node which has the most messages should always suggest last (nmax-nmin) messages known to it, but that sounds a bit too optimistic (I'll do some benchmarks though). "Suggested" messages might also be handy in case when (for some reason I need to think through) two nodes happen to have the same number of messages, but some of the messages differ.

So the protocol now looks like that:

  1. Alice wants to send Bob a message from her Ai and Bob's Bj is online.
  2. Ai → Bj: send the new count of the messages and the new message's messageID and body; retransmit until reply received.
    1. If message counts still differ after processing the new message, run the binary search sync, retransmitting each, well, cue until reply is received.
    2. When a node receives a message count equal to its own one, it sends a reply "sync done, thanks" (like FIN), which is retransmitted until confirmation reply (like FIN ACK) is received.
    3. "Sync done confirmed" ("FIN ACK") is sent each time a "sync done, thanks" is received. No reply (stop clause) and therefore no retransmission is required.
  3. Ai → other Ak and Bj → other Bl: similar, but
    1. The forwarded message contains a list of nodes which already have the message; nodes add themselves to it before forwarding it further and do not contact the nodes from the list while doing so.
    2. Ai and Bj may attach the message immideately, being the first to have it; others need to "suggest" it first.

Do these additions sound sane?

In reply to Re^2: [OT] Merging messages between users on different machines by Anonymous Monk
in thread [OT] Merging messages between users on different machines by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.