6

This is a deeper question than this question.

When a chat message is sent in a decentralized system, there are multiple events happening in a row. If a message is sent through a routing server, such as in Facebook Messenger or Slack or most other messaging systems, these things happen in this order:

  1. Message is generated (the user presses "send")
  2. Message is sent to a server.
  3. Message is forwarded by the server to the recipient.
  4. Message is seen by the recipient.

In addition, these things happen, interleaved with the above:

  1. Sender learns from the server that the server has received the message.
  2. Sender learns from the server that the recipient has recieved the message.
  3. Sender learns from the server that the recipient has seen the message.

There's a lot of uncertainty in the ordering of these events, and there might be minutes, hours or even days between them.

Messenger gives the user some feedback by showing

  • a blue cicle when 1 has happened (but not 7)
  • a blue circle with a blue check when 7 has happened
  • a blue dot with a white check when 8 has happened
  • the profile picture of the recipient when 9 has happened

In addition, the ordering of multiple messages on multiple devices is uncertain. We can use techniques like vector clocks to figure out a partial ordering, but a total ordering is impossible to come by. It gets even harder when users' clocks are set incorrectly, or when messages are sent but take a hours to reach a server, maybe because the user has lost cell tower coverage.

There are two parts to this question:

When do we timestamp messages?

  • When they're generated on a local device, meaning the time might be very incorrect because the local clock is incorrectly set.
  • When the message reaches the first server, which means that it could be off by hours or days from when the message was actually sent.
  • When the message is received by each recipient, meaning that it could differ from device to device.
  • Not at all, meaning there are no timestamps for messages, which makes it hard to see if a message was sent weeks ago or just now, but also that this problem becomes much easier.

Second, in what order should the messages be shown?

  • In the order of the timestamps, however they are decided.
  • In the order of the vector clocks, which guarantees that some things happened before other things. Vector clock ties would be resolved by timestamps.

Ordering messages by timestamps means messages can sneak into the chat history minutes or weeks later, if the timestamp is generated on the user's device or the message is stuck in some server somewhere. Ordering things by vector clocks means that the order messages are shown on screen might not agree with their timestamps.

I want your thoughts from a user experience point of view. There are other important views, such as security, performance and mathematical correctness, but I do not want feedback from those perspectives at this time.

Improve this question

2 Answers 2

Reset to default
2

I strongly recommend two things to preserve user sanity:

  1. Always show messages in the same order to all participants in a conversation.

  2. Never attempt to filter messages in a way that can filter them differently to different participants in a conversation.

That said, I'd recommend the order be the order in which the messages were received by a central server, if possible. You can annotate the messages with the time they were sent, if desired.

The primary reason for these rules is to prevent intentional or accidental situations in which participants understand the flow of a conversation differently.

Improve this answer
8
  • I agree with the saneness argument, which rules out using the receive time as the order. Since it's a decentralized system, there is no central server, so messages cannot be totally ordered from a central place.
    – Filip Haglund
    Jun 22, 2017 at 22:27
  • @FilipHaglund Then you will find that misunderstandings are frequent and conversations are hard to follow. When two people are talking and a third person interjects a "yes" or an "I agree", it's vital that they see their interjection in precisely the same place everyone else does. You may need to add some pseudo-centralization to make this work, including possibly negotiating the ordering with a distributed agreement protocol or appending metadata to the messages sufficient to permit agreement on ordering.
    – David Schwartz
    Jun 22, 2017 at 22:31
  • For example, you can have each message include a unique ID of the message it follows in the sender's ordering. You can then resolve disputes (two messages that follow the same message) deterministically, say by sorting the messages in send timestamp order and then ID order (if there's a timestamp tie). (Have an expert in distributed systems design this functionality right from the beginning!)
    – David Schwartz
    Jun 22, 2017 at 22:34
  • I can generate a total ordering that is the same everywhere, using the vector clocks and message id's, but that means messages might not arrive in the same order everywhere, so some messages might be inserted into the history after the fact, even maliciously, to change the meaning of a conversation.
    – Filip Haglund
    Jun 22, 2017 at 22:34
  • @FilipHaglund You can do that temporarily, and then have the clients negotiate a re-ordering. It will take some effort to get this right.
    – David Schwartz
    Jun 22, 2017 at 22:35
2

The de-facto source of truth timestamp is the server's UTC time.

Problem is, client devices are not always online - sometimes a mobile will have neither WiFi nor Network so requests are queued up. Also, clients can temper with their device time.

From experience, there is no way to ensure clients aren't tempering with their device time, whilst it is offline. But this is the best we could come up with, for a system that was dependent on accurate user event timing (users report starting and ending work):

  • When a user perform an action, it is timestamped using the client device clock.
  • An attempt is then made to dispatch to the server, with another (request) timestamp (client) added with each attempt.
  • If the device is online and the server gets it, the server works out the delta between the request and original timestamp, and deduct it from the server UTC.

A complete overkill for most scenarios, if you ask me, but I hope this helps.

Improve this answer
6
  • I am sorry, I didn't understand the last point: If the device is online and the server gest it, the server works out the delta between the request and original timestamp, and deduct it from the server UTC.. What does the server do? Does it compute another timestamp from the user performed action timestamp (first point) and request timestamp (second point)?
    – tonix
    Jul 2, 2019 at 10:20
  • 1
    Yes, it does deltaT = requestTS - actionTS to find the time delta between the action and the actual request time that has made it to the server. Then the server computes: actionTS = currentUtcTS - delta. Does it make sense?
    – Izhaki
    Jul 2, 2019 at 12:21
  • Yes, however, both requestTS and actionTS can be spoofed by an unpleasant user as they are generated client side, leading to a wrong actionTS as it is computed using a wrong delta. How would you deal with such cases? I mean, you are doing this only in order to convert the time into UTC, right? We are assuming that you the timestamps sent by your users.
    – tonix
    Jul 2, 2019 at 12:29
  • 1
    As I said, there is no way to ensure that. At least I'm not familiar of one.
    – Izhaki
    Jul 2, 2019 at 14:07
  • 1
    Yes. If the user modify their timestamp whilst offline, I know no of a strategy to solve this issue.
    – Izhaki
    Jul 2, 2019 at 14:25

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.