[messaging] Message order in group chat (attempt at summary)

[Michael Rogers]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 29/04/14 13:54, Ximin Luo wrote:
>> In a word, Usenet. This has the nice property that if a subset
>> of the members are connected to each other but disconnected from
>> the other members, they can carry on the conversation and see
>> each other's messages, without having to wait for the other
>> members.
>> 
>> However, it definitely requires a threaded rather than linear
>> UI.
>> 
> 
> A threaded UI is only necessary if you implement "in-reply-to" 
> pointers, since this generates a tree structure. By contrast, 
> "latest-messages-seen" pointers generate a DAG structure, and *are 
> able* to model a linear chat system.  But the algorithm Ben
> mentioned (auto-re-sending older messages not yet acknowledged by
> others) can be implemented for both structures.

Sorry, I should've been clearer. The thing that requires a threaded UI
is not Ben's idea, but carrying on conversations among subsets of the
members during a partition - such conversations aren't semantically
linear, so it doesn't make sense to shoehorn then into a linear UI.

I agree that Ben's idea could be used to sync both semantically linear
and semantically threaded conversations.

> I agree that trees of threads are "simpler" to think about, than
> DAGs and merge algorithms, but they have several downsides. The 
> concurrency in a tree is pointless, because one is never able to
> see the merged effects of any concurrency - you only see a linear
> history and ignore other forks. In a DAG however, each message
> automatically merges all seen forks, and the concurrency here is
> actually visible.

I think it would be useful to distinguish between the representational
structure of the conversation and the semantic structure. A threaded
conversation is semantically a tree; a linear conversation without
simultaneous speaking is semantically a chain. I'm not sure how to
describe the semantic structure of a linear conversation with
simultaneous speaking.

The question of whether we use a DAG, a tree or some other structure
to represent a conversation should be separated from the question of
whether we're trying to represent a semantically threaded or linear
conversation.

I've previously suggested using tree of pointers to represent a linear
conversation with simultaneous speaking; each node points to the
deepest node received by its sender, and nodes of equal depth are
considered simultaneous. In theory such a representation allows
subsets of the members to carry on branches of the conversation during
a partition, but semantically the result of squashing the branches
back together and treating them as one conversation with lots of
simultaneous speaking would be nonsense.

I have a hunch that for linear conversations, something like the CAP
theorem holds: if there's a partition, either the conversation has to
pause or you have to give up consistency. Threaded conversations can
be partition tolerant because they can sacrifice global availability
and global consistency - branches of the conversation can continue
with only local availability and local consistency, and if necessary
global consistency can be reestablished later.

> For example, if you have a transcript consistency verification,
> you generally need n messages (one from everyone) to confirm this.
> With a tree structure, you would need to do this in every single
> branch. With a DAG structure, you can do this for all branches at
> once, using a merge algorithm.

Yes, I agree that DAGs may be useful in representing conversations
that are semantically trees or chains. However, if my hunch about
partition tolerance is right, DAGs may have the downside of requiring
more global information than trees, when representing conversations
that are semantically trees.

Cheers,
Michael
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQEcBAEBCAAGBQJTYXIkAAoJEBEET9GfxSfMVvkIAKzk916YDwVb5B3vsZoWHkLU
Oas87CK/GhhjCOmNYYq4WwPQt/JBgo7+M22zkaLV7aAg8Ud4+Ub8zJX6XP4pWlHK
z7PgqlkR79R47gM40Lqhw9IFFVkc4bOp/92CvgwrpO2jj0ScYHBOoTq8aRx48hF/
+8g8kg2mdOGXbgzPf3ozuArr5+/QzMtFdiVt9qQggwOmbzE1X2DU7/iVogom05UL
tuTVqYawt7dSrnGecwveWbyz1xuCsuRwgAV17DNpmXXAP2+7nD6V0N0icmPyNsdZ
ARMJ+VjZkSooMGOy1+uYDwyGlGOX0fymHBPiMcn0XxNsA0xavxf0+QKn7EM7d0A=
=3D47
-----END PGP SIGNATURE-----