4 ms·
Thank you! I'll rework this paragraph to be correct, I wanted to make an observation that the given data (two attempts to implement key-value storages with keep
by rystsov 10y ago
Thank you! I'll rework this paragraph to be correct, I wanted to make an observation that the given data (two attempts to implement key-value storages with keeping the length of a program as short as possible) favour Gryadka but of course isn't wrong to make strong statements based just on one data point.
- jerf 10y agoI would suggest just dropping Kolmogorov in general, and just referencing the human idea that shorter is generally going to be simpler. I wouldn't have a problem sticking with you through that. Sure, I can feed that to my pedant mill as with anything else, but since it's not really the core idea I'll roll with you on it.
- ReidZB 10y agoAgreed. The section basically boils down to "despite maybe looking simpler, Single-Decree Paxos is still tricky." I don't think something particular and formal like Kolmogorov complexity even fits the tone there.
- throwaway91111 10y agoRight. There's no strict value to higher or lower complexity in the Kolmogorov sense, so you might as well assign the value to something more tangible (like pseudocode terseness or something)
- joe_the_user 10y agoYeah, The problem isn't just the incomputable quality of Kolmogorov complexity but that fact that Kolmogorov complexity applies only to finite strings or things that can be meaningfully mapped to them. Especially, Kolmogorov doesn't apply directly to abstract algorithms or programs with multiple implementations.
- mafribe 10y agoThe concept of Kolmogorov complexity can be extended to infinite strings, see e.g. L. Staiger's _The Kolmogorov complexity of infinite words_ (https://www.sciencedirect.com/science/article/pii/S0304397507003180 https://www.sciencedirect.com/science/article/pii/S030439750...).