Data consistency algorithm

Question

I am developing 2-4 players networks game. At the heart of the model there is a data structure that acts like a google-docs spreadsheet that everybody can edit in any time. For simplicity, each of the spreadsheet cells can contain only one letter.

Some abilities and requirements: 1. All players can edit a spreadsheet cell in any time. (that's means that there must not be a "locked cell") 2. All network transactions are reliable (but can arrive out of order)

I am having an hard time developing an algorithm for handling the shared spreadsheet-like data structure. Does someone familiour with a similar problem that have a solution? or suggest a simple way to solve the problem?

Thank you.

Answer 1

I think you should try to define some criteria for the algorithm you are looking for. You may want a guaranteed response time. Or you might prefer absolute data consistency. It seems unlikely to achieve both at the same time.

The subject you are talking about is called Operational Transformation: http://en.wikipedia.org/wiki/Operational_transformation

Some open source software do amazing things in this field, like http://sharejs.org/ or http://etherpad.org/