Re: RFC: implementation of package pools
Kai Henningsen wrote:
>
> > > Try this, design a B-Tree structure that stores a set of words. The
> > > underlying hardware you are running on destroys 0.001% of all your
> > > 'pointers' in an unpredicable way. Design an algorithim to operate 100%
> > > correctly and a seperate one to operate 99% correctly, but allow a human
> > > to fix the tree structure if necessary. Which is longer? Which is slower?
> > > If you could use another datastructure besides a B-Tree could you get 100%
> > > reliability? (perhaps one that did not use 'pointers')
> >
> > use redundant data and error correcting codes, that will do it. a
>
> You don't seem to understand the theory behind error correcting codes:
> they *don't* get you 100%. *Nothing* gets you 100%.
>
Read the problem above more carefully. I'm claiming complete recovery
under the conditions he gives as assumptions (0.001% of pointers destroyed
randomly before the algorithm can operate). I can write such an algorithm,
but I believe that any CS Bsc here should be able to write, too. :I
--
Eray (exa) Ozkural
Comp. Sci. Dept., Bilkent University, Ankara
e-mail: erayo@cs.bilkent.edu.tr
www: http://www.cs.bilkent.edu.tr/~erayo
Reply to: