You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by Apache subversion Wiki <co...@subversion.apache.org> on 2012/11/29 05:15:10 UTC
[Subversion Wiki] Update of "FS2/Theory" by brane
Dear Wiki user,
You have subscribed to a wiki page or wiki category on "Subversion Wiki" for change notification.
The "FS2/Theory" page has been changed by brane:
http://wiki.apache.org/subversion/FS2/Theory
Comment:
Begin writing up configuration space theory.
New page:
= Configuration Spaces and Histories =
Before we dive into versioned filesystem design and implementation details, let's first take a look at the concepts we're talking about. We'll begin by discussing what a configuration management system actually operates on.
''N.B.'': Although the following text uses mathematical concepts and notation, it's not intended to be a rigorous dissertation on configuration theory. We'll often make statements and draw conclusions without providing proof. Therefore, dear reader, you can either trust we're right, or do your own homework to prove (or disprove) our assertions. We will, however, try to conscientiously flagโ all leaps of faith in the text.
'''Definition:''' A ''data configuration'' is a unique pattern of data that can be represented as exactly one distinct sequence of binary digits.
* The representation of the ''empty configuration'' {} is the zero-length sequence.
* The ''size'' , โcโ, of a configuration c is the length of its representative sequence of binary digits.
'''Definition:''' A ''data configuration space'' is a [[http://en.wikipedia.org/wiki/Metric_space|metric space]] (๐น, ๐น) where:
* ๐น is the set of all data configurations;
* ๐น: ๐น ร ๐น โถ โ is a metric on ๐น.
'''Definition:''' A ''configuration history'' is a sequence of elements of the data configuration space.
== Defining the Metric ==
We'll now show that we can indeed define a metric for ๐น. One example is the ''[[http://en.wikipedia.org/wiki/Levenshtein_distance|Levenshtein distance]'',
๐: ๐น ร ๐น โถ โ^0^
applied to the binary-digit sequence representation of data configurations. It is easy to showโ that ๐ has all the required properties of a metric. In addition, it has the following properties:
* The minimum distance between any two distinct configurations isโ 1.
* The maximum distance between any two distinct configurations isโ the greater of their sizes: โa,b โ ๐น: ๐(a, b) โค max(โaโ, โbโ) .
* And it followsโ from this that: โc โ ๐น: ๐({}, c) = โcโ .