search

Intersubjective / riblt-rust

Rust port of RIBLT library by yang1996
MIT License
15 stars 1 forks source link

Deterministic mapping #2

Open automainint opened 2 months ago

automainint commented 2 months ago

Coding doesn't seem to work if mapping is not deterministic. Corresponding tests code is available in the determinism branch.

We have to ensure that the method RandomMapping::next_index is deterministic. It may not be deterministic since it has floating-point arithmetic and sqrt function.

adamierymenko commented 2 months ago

Is this really nondeterministic? Looking at this it looks like the chance of it rounding wrong is far lower than the chance of a hash collision. But someone should prove this.

I'm more concerned about performance. Is there perhaps a way to do what this is doing that is both faster and provably deterministic?

automainint commented 2 months ago

Is this really nondeterministic? Looking at this it looks like the chance of it rounding wrong is far lower than the chance of a hash collision. But someone should prove this.

I'm more concerned about performance. Is there perhaps a way to do what this is doing that is both faster and provably deterministic?

I did some research. Seems that basic float arithmetic and sqrt should be deterministic. RandomX uses those operations for it's hash algorithm as well. I think it's good enough to just add some tests to make sure it works as expected on current platform.

It would be also a good idea to make sure that compiler won't break determinism by rearranging something or using some different modes. I don't know how to do this is Rust (RandomX uses asm).

Is there perhaps a way to do what this is doing that is both faster and provably deterministic?

This will require more fundamental redesign of the algorithm. I myself don't understand it deep enough. Maybe authors of the original paper can come up with something that is both fast and don't use float calculations.