Non-determinism

btober btober at seaworthysys.com
Thu Apr 18 03:48:02 EST 2002


So, when thealgorithm thinks that a block of code in the source file A
is the same as some block of code in target file file B, on account of
the check-sums being the same, when in fact the two blocks of code are
different (as the documentation explicitely states is an, al beit
remote, possibility), so that you're expecting to end up with B as a
copy of A and it isn't, then how can the algothrim be considered
deterministic?

Note that the resulting difference in the final state of  files A and B
is not due to transmission or hardware errors in this case. A and B
started out different (similar, but different), and ended up different
because the checksum computed to the same value for different blocks of
code so the algorthim couldn't tell they were different. This is
deterministic?

And don't ask me to produce an example, because I do understand
"astronomical". But if you had a heart pacemaker whose operation
depended on appropriate updates to a control data file, would you trust
rsync to send that file update to the pacemaker?

----- Original Message -----
From: Martin Pool <mbp at samba.org>
To: Berend Tober <btober at computer.org>
Subject: Re: Non-determinism


> On 17 Apr 2002, Berend Tober <btober at computer.org> wrote:
>
>
> > So while the software algorithm of ftp and cp are deterministic,
> > there must be some quantifiable probablity of failure
> > non-the-less. The difference with rsync is that not only are the
> > same effects of data corruption at work as with ftp and cp, but the
> > algorithm itself introduces non- determinism.
>
> You are using the word "non-deterministic" in a way at odds with its
> usual meaning in computer science.
>
> > 1 definition found
>
> > From The Free On-line Dictionary of Computing (13 Mar 01) [foldoc]:
>
> >   deterministic
>
> >      1. <probability> Describes a system whose time evolution can
> >      be predicted exactly.
>
> >      Contrast {probabilistic}.
>
> The execution and output of the rsync algorithm can be exactly
> predicted from its input.  It is a deterministic algorithm.
> ...
> What part of "astronomical" don't you understand?
>






More information about the rsync mailing list