Seems to me, without having done any kind of exhaustive analysis, that in any system of multiple sources to multiple destinations; there is only one universal frame of reference: time. (Ignoring relativity :)

Any counters you employed; would need to be synchronised; and thus leave windows of opportunity for clashes and mismatches.

You say "But using only timestamps will sooner or later result in a collision."; but unless Alice (or Bob) are in the habit of typing messages on two different devices simultaneously, there is no scope for timestamp collisions originating from one individual.

Unless that one account could be legitimately used by a group of persons; in which case, each device should add it's device number to the timestamp to ensure uniqueness.

Of course, neither timestamps alone, nor timestamps + deviceId, give any mechanism for recipients to detect they have missed a communication.

I only see three possible approaches to that

1. Guaranteed delivery; a la tcp .v. ucp:

   If sent messages required positive acknowledgements; and acknowledgements also require positive acknowledgements (look up "triple-handshake"), messages would be resent by their originator until it received an ack; and recipients would discard or disregard receipts until they received acks to their acks.

   And yes. It's recursive, so needs a bailout and start again clause.

2. Swap (or augment) the deviceId with a device counter:

   If each sender (device) maintains a monotonically increasing count of outbound comms with every recipient device; then when a recipient receives a message from a given sender, it can check to see if it missed anything since the last message it received from that sender.

   Of course, if the sender sends a message that fails to deliver; and never sends another; the recipient will never know it missed something.

3. Master senders and/or master receivers:

   If each group of devices chose and maintained an official server device. and all outbound and inbound comms were redirected through that device, it could maintain sender/receiver pair counts that could serve to uniquely identify communications; but the logistics are horrible.

   It would require regular handshakes between the current primary and all the other devices; and there would need to be an automated fail-over mechanism; and an automated fail-over-fail handover mechanism....

   In fact. I'm regretting ever mentioning a "third option" :)

All in all, treating every device to device communication as a separate id (deviceId+deviceId+count) seems to be the only sure way of detecting missed communications in a timely and guaranteed manner.

And the process of sharing and consolidating communications between groups of devices allocated to any given userid is a secondary process that happens on a "best endeavour" basis.

This allows for the user of a group of devices to eventually be aware of all communications and any missed ones; but it leaves a time window during which they may be unaware of the true state of the conversation.

That time window of incomplete information is potentially open-ended; but that will always be the case when any device could fail permanently at any given time.

Not much in the way of a useful answer there; but maybe food for thought.