4 ms·

That makes the problem harder, but not impossible.

by adastra22 2y ago

lmm 2y ago
It makes an incrementing message ID impossible.
- adastra22 2y ago
  Only if you're not ok with eventual consistency and renumbering in the case of discovered conflicts or net splits.
toast0 2y ago
I'm pretty sure this is actually impossible in a distributed system with independent operation, and if it were possible, it would be terrible UI anyway. Problem one is if you want to order events chronologically, you need to precisely decide what the time of the event means. Probably not the time the client hit send, because you can only measure that on the client and client clocks are at best approximately accurate. You could consider the time the server received it, and assume your server times are accurate, but that's still problematic because even in a well functioning system, if a user sends message A to server.wdc around the same time as a user sends message B to server.lax, users connected to server.wdc will get A then B, and users connected to server.lax will get B then A, and this leads to problem two: Problem two is messages generally display in order of receipt. If you get a message that slots in earlier in the thread, you may need to scroll up to see it. In a busy theead, it's going to be hard to read all the messages because of the back and forth. If you send a message, it may need to be reordered too. If you go back to the thread later, new messages may be in different places. This is more disorienting IMHO than different message orders for different viewers. Problem two gets even worse when you don't just have distance between servers, but also some network or other operational issues. If a server accepts a message, but is unable to forward it immediately, you probably want it to forward it whenever it can... if there's a significant delay, now the message is again going to be displayed in a place where it's difficult to see. You can kind solve this by forcing messages to a group to go through a single queue which forces an ordering, but that makes accepting messages for a group a lot more difficult.
- j16sdiz 2y ago
  > This is more disorienting IMHO than different message orders for different viewers. the parent post is arguing this is less disorienting, and I agree.
  - toast0 2y ago
    I feel like when an important message comes in out of sequence, but you had already sent a response to the chat with what was visible at the time, it will be very confusing when that gets reordered. Ex: A@T0: User X is abusing our service, we should send them a sternly written letter. B@T60: Yes, I'll do it right away. C@T2 (received later): No, we should just shadowban them. When B sent their message, their intent was clear to them. But when they review their message after C's message is received, if the display ordering is changed, the meaning of the communication has changed, and how can B show that sending the warning was reasonable when they clearly said they were going to shadowban the user. (Maybe this group should use something else with a guaranteed ordering to track abuse and response, but that's a different question) If C's message is displayed earlier than B's in some cases and not others, that makes for a confusing situation, but each person can look at their messages and easily see what they saw when they argue about a breakdown in communication in the aftermath.
- adastra22 2y ago
  There are relatively straightforward decentralized consensus algorithms for ordering events if we assume cooperation. If we assume malicious peers, then we're in the space of the byzantine generals problem, but there are solutions to that too. Now there's some property that you have to give up, for example an immutable ordering. You might think the message came in one order, then reconnect with the network and discover the order was flipped. So long as the UI can handle that an update, there are consensus algorithms that will deliver a consistent view even in the edge cases. You don't need a single timestamping queue.
- aeonik 2y ago
  As long as the speed of light remains constant for all observers, who cares if everyone agrees on simultaneity? Distributed systems don't need to know what time it is, just what happened. Well known systems are implemented this way, and the UI is great, people barely even notice.

That makes the problem harder, but not impossible.

lmm 2y ago

It makes an incrementing message ID impossible.

adastra22 2y ago
Only if you're not ok with eventual consistency and renumbering in the case of discovered conflicts or net splits.

toast0 2y ago

I'm pretty sure this is actually impossible in a distributed system with independent operation, and if it were possible, it would be terrible UI anyway. Problem one is if you want to order events chronologically, you need to precisely decide what the time of the event means. Probably not the time the client hit send, because you can only measure that on the client and client clocks are at best approximately accurate. You could consider the time the server received it, and assume your server times are accurate, but that's still problematic because even in a well functioning system, if a user sends message A to server.wdc around the same time as a user sends message B to server.lax, users connected to server.wdc will get A then B, and users connected to server.lax will get B then A, and this leads to problem two: Problem two is messages generally display in order of receipt. If you get a message that slots in earlier in the thread, you may need to scroll up to see it. In a busy theead, it's going to be hard to read all the messages because of the back and forth. If you send a message, it may need to be reordered too. If you go back to the thread later, new messages may be in different places. This is more disorienting IMHO than different message orders for different viewers. Problem two gets even worse when you don't just have distance between servers, but also some network or other operational issues. If a server accepts a message, but is unable to forward it immediately, you probably want it to forward it whenever it can... if there's a significant delay, now the message is again going to be displayed in a place where it's difficult to see. You can kind solve this by forcing messages to a group to go through a single queue which forces an ordering, but that makes accepting messages for a group a lot more difficult.

j16sdiz 2y ago
> This is more disorienting IMHO than different message orders for different viewers. the parent post is arguing this is less disorienting, and I agree.
- toast0 2y ago
  I feel like when an important message comes in out of sequence, but you had already sent a response to the chat with what was visible at the time, it will be very confusing when that gets reordered. Ex: A@T0: User X is abusing our service, we should send them a sternly written letter. B@T60: Yes, I'll do it right away. C@T2 (received later): No, we should just shadowban them. When B sent their message, their intent was clear to them. But when they review their message after C's message is received, if the display ordering is changed, the meaning of the communication has changed, and how can B show that sending the warning was reasonable when they clearly said they were going to shadowban the user. (Maybe this group should use something else with a guaranteed ordering to track abuse and response, but that's a different question) If C's message is displayed earlier than B's in some cases and not others, that makes for a confusing situation, but each person can look at their messages and easily see what they saw when they argue about a breakdown in communication in the aftermath.
adastra22 2y ago
There are relatively straightforward decentralized consensus algorithms for ordering events if we assume cooperation. If we assume malicious peers, then we're in the space of the byzantine generals problem, but there are solutions to that too. Now there's some property that you have to give up, for example an immutable ordering. You might think the message came in one order, then reconnect with the network and discover the order was flipped. So long as the UI can handle that an update, there are consensus algorithms that will deliver a consistent view even in the edge cases. You don't need a single timestamping queue.
aeonik 2y ago
As long as the speed of light remains constant for all observers, who cares if everyone agrees on simultaneity? Distributed systems don't need to know what time it is, just what happened. Well known systems are implemented this way, and the UI is great, people barely even notice.