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

[Chris Gray]

On 5 Feb 2004, Tom Lord wrote:
>
>> From: Chris Gray <address@hidden>
>
>> 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.
>
> For dumb-servers, the tentative plan is to allow an explicit
> management command such as `tla archive-cache-delta' (similar to
> `cacherev').

Okay, I could be happy with that.

> Regarding the DoS attack -- I don't see any obvious new risk here
> unless you are imagining a poor smart-server implementation.

Well there's two possibilities that I see: either the server caches
all the summary deltas that it creates or it doesn't.  In the first
case, the attack makes archive size become something like O(n^2),
which could be bad.  On the other hand, all patching would then be
O(1), which would be nice.  If the server doesn't cache all the
summary deltas it creates, then there is surely some pattern of
requests that would make the server do nothing but create deltas all
day. 

Just to compare with what I'm proposing, in a skiplist, you expect
that the archive size would grow at about an O(n log n) rate and that
patching would be O(log n).  On an archive with 1,000 patches, n log n
sounds a lot nicer to me than n^2.

Cheers,
Chris