-----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----- _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
