Suppose you are developing some software. The requirement is that, when the software starts up, it is given two different versions of an file, and it must use the latest version.<\/p>\n
That’s easy! You simply store a generation number with the object and increase it every time the object is modified. A relatively small number amount of bytes can handle a large number of changes.<\/p>\n
According to my calculations, a 64-bit generation number easily cover 10 version changes every second for the entire history of the Universe.<\/p>\n
\n
Oohh! I’ve just had a product idea! A font and template for Excel just for these sorts of calculations. It makes the spreadsheet look like the cells have actually been written on the back of an envelope!<\/p>\n<\/div>\n
Slightly Harder Version of the Problem<\/h3>\n
However, what if the files might<\/em> have been branched in the meantime? So a copy of the file might<\/em> have been edited while the main file was also been edited. <\/p>\nThere are three possible scenarios:<\/p>\n
\n- Neither file was touched, in which case they are both identical.<\/li>\n
- One file is derived directly from the other file, in which case the later file should be used.<\/li>\n
- Both files were edited, in which case a more sophisticated merge needs to take place.<\/li>\n<\/ul>\n
For example: When a PDA is reconnected to a PC, and the files are resynchronised, the system needs to work out which files should be kept, which should be overwritten and which should be flagged as being in conflict.<\/p>\n
Overly-Simplistic Solution<\/h3>\n
If storage space was no object, this would be easy to solve. You could store a complete version history of the object in the version number – perhaps using a code for each device.<\/p>\n
A version number might look like this PC.PDA.PDA.PDA<\/code>, which means the file was created on the PC, and edited three times on the PDA. When the file is compared against PC.PDA.PDA.PDA.PC.PC<\/code>, the system can see that the latter is more up to date. Meanwhile, PC.PDA.PDA.PC.PC.PC<\/code> would be highlighted as a conflicting version.<\/p>\nYou could make this system even more robust with timestamps and other distinguishing marks.<\/p>\n
Hard Problem<\/h3>\n
When the system’s architect sees your plans above, a new design constraint is quickly added. The architect limits you to a bounded storage budget. <\/p>\n
On the other hand, the architect will accept a probabilitic solution – one that will probably<\/em> detect which one is the latest. If it helps, it may be less accurate (i.e. lower probability of a correct answer) after a massive number of off-line changes. In comparison, when there has only been one or two changes off-line, when it should be highly accurate.<\/p>\nThere’s room to negotiate how much space you need in return for how accurate you can get, but let’s say, in the first draft, 32 bytes of storage have been put aside for this.<\/p>\n
A Poor Solution<\/h3>\n
Here’s one solution:<\/p>\n
You treat the 32 bytes as a pool of 256 flags, all initialised to 0 as the file is created.<\/p>\n
Each time the file is modified, a random flag is set to 1.<\/p>\n
When comparing two files, if one file contains all the set flags of the other file, and more, then it is later.<\/p>\n
This solution is very limited – it only handles 256 changes. The desired behaviour starts to collapse completely as the number of changes approaches 256. <\/p>\n
Can you do better?<\/h3>\n
So my question is, what would be a good algorithm to use here, to handle more than 256 changes, while still retaining the right stochastic profile?<\/p>\n","protected":false},"excerpt":{"rendered":"
Here’s a little challenge for the software developers.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_s2mail":"","footnotes":""},"categories":[33,34],"tags":[],"class_list":["post-108","post","type-post","status-publish","format-standard","hentry","category-puzzle-solving","category-software-development"],"_links":{"self":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/comments?post=108"}],"version-history":[{"count":0,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/108\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/media?parent=108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/categories?post=108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/tags?post=108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}