<br><br><div class="gmail_quote">On Sat, Mar 29, 2008 at 1:05 PM, Benjamin M. Schwartz <<a href="mailto:bmschwar@fas.harvard.edu" target="_blank">bmschwar@fas.harvard.edu</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

<div>C. Scott Ananian wrote:<br>
| On Sat, Mar 29, 2008 at 1:47 AM, Benjamin M. Schwartz<br>
| <<a href="mailto:bmschwar@fas.harvard.edu" target="_blank">bmschwar@fas.harvard.edu</a>> wrote:<br>
|>  We will have an open discussion of how to build a framework that will<br>
ease the<br>
|>  creation of reliable collaborative activities.  I will also outline a<br>
proposal<br>
|>  for "Collisionless", a particular message-based API that encompasses both<br>
|>  real-time and offline collaboration.  The key idea of Collisionless is<br>
to break<br>
|>  down high-level tasks into a sequence of messages whose significance<br>
does not<br>
|>  depend on the order in which they are received.<br>
|<br>
| Hmm.  I've always thought of a high-level framework here as based on a<br>
| shared undo/redo list, since most mature applications support<br>
| undo/redo.  The idea is that we provide the necessary distributed<br>
| consensus algorithms to allow all participants to agree on the order<br>
| of the entries in their undo/redo list; anyone who had actions applied<br>
| in the wrong order performs undos, then redos to adjust their order.<br>
| When you present your proposal, I'd love to hear a comparison to this<br>
| approach.<br>
<br>
</div>That is a very interesting perspective.  I will definitely think hard<br>
about that and try to come up with a sensible comparison.<br>
<br>
Offhand, I think the Collisionless idea is like a design where each<br>
person's Undo/Redo list can be in a different order, and yet always reach<br>
the same final state, as long as they contain the same total set of edits.<br>
<br>
--Ben<br>
<div><div></div><div><br>
</div></div></blockquote><div><br>On any data structure with internal order (ie, anything much more complex than a set), it is impossible to have an arbitrary set of edits result in the same final state independently of order. Obviously, from both the name "collisionless" and from this logic, you must add constraints: a given set of edits is "collisionless" if you can apply them in any order; in the example of a text file, collisionless essentially means that they edit different portions of a file. When there is a dispute about the order of "collisionfull" edits, some explicit merge algorithm is needed - either one edit wins and the other loses, or you arbitrarily assume an order, or you ask for user intervention.<br>

<br>I would simply pose the case of source control - the one I'm interested in for Develop. Even if two people edit entirely different files, it is not 100% safe to have an automatic merge of their code - say both fixed the same bug by incrementing the same variable, but now it gets incremented twice. Honestly, in a loose kind of environment, as most XO coding will be, "fine, we'll catch that in testing" is an OK answer to that, especially if you have automatic tests. But in order to debug that once you catch it, you need tools for seeing who did what when, ones which highlight any automatic merges as possible sources of problems.<br>
<br>I know, source control is a special case, and you don't want to contort your framework for this special case. My main point here is that the framework will be most useful if:<br>- it allows its client app to decide what to do in the case of "collisions"<br>
- it notifies  the client app even of "crossovers" that aren't "collisions"<br>- it provides some support for keeping track of who did what, even when there aren't crossovers or collisions<br><br>
In other words, do your magic, please, but tell me about it if I care. It is easy to think of non-source-control use cases for all of the three cases above. This is not to say that a totally black-box solution wouldn't be useful for many, just that a more open solution would be more so for more.<br>
</div></div><br>Jameson<br>