[Gnu-arch-users] Re: RFC: arch protocol, smart server, and tla implementation prototypes

[Chris Gray]

On 4 Feb 2004, Tom Lord wrote:
>
>> From: Chris Gray <address@hidden>
>
>> I will probably get flamed by some for saying this, but skiplists
>> [1] do a pretty good job of this without any of that bogosity.
>
> What's being described is a dynamically optimized (in response to
> demand) generalization of skip-deltas.  A caching/composing-server
> would need a heuristic to decide which which deltas to compute and
> cache.  The static algorithms typically described for skip-delta
> approaches are one possible heuristic --- if you program a
> caching/composing-server with that heuristic: you've got classic
> skip-deltas.   Other heuristics may be better in practice, or not --
> we don't know yet.
>
> Speculatively: most likely other heuristics _would_ be better in
> practice, at least where it matters.  If Linus says, for example,
> "here is 2.7" -- and many, many people run `update' for the first
> time since "here is 2.6" -- then a more dynamic heuristic can
> optimize all of those updates perfectly while a static skip-delta
> approach would only optimize them perfectly, sometimes, by
> coincidence.

This is true.  I see a couple of problems with that though.  The first
is that it relies on a smart server, whereas skiplists (or probably
any static heuristic) don't need to.  The second is the rather obvious
DoS that would result.  

Cheers,
Chris