3 ms·
If you generate randomly then, due to the birthday paradox, after generating sqrt(N) values you have a reasonable chance of collision. The birthday paradox is
by tomerv 5y ago
If you generate randomly then, due to the birthday paradox, after generating sqrt(N) values you have a reasonable chance of collision.
The birthday paradox is named after the non-intuitive fact that with just 32 people in a room you have > 50% of 2 people having a birthday on the same day of the year.
- adwn 5y ago> 32 people Slight correction: only 23 people, actually. So in every second football ("soccer") game, you have two people on the field with the same birthday.
- doo_daa 5y agoI think it's 23 people in a room. The canonical example is people on a football (soccer) pitch. With 11 per side plus the referee there's a 50% chance that two will share the same birthday.
- ratorx 5y agoDoes birthday paradox apply here? It’s about any pair of people having the same birthday, whereas in this case you need someone else with a specific birthday. For example, if you generate 2 numbers and they are the same, but are different to the capnproto number, that’s a collision but doesn’t actually matter. EDIT: It does apply, I misunderstood what the number was being used for.
- elcritch 5y agoIt does apply, according to https://www.johndcook.com/blog/2017/01/10/probability-of-secure-hash-collisions/ https://www.johndcook.com/blog/2017/01/10/probability-of-sec...
- ratorx 5y agoYou’re right, I misunderstood what the magic number was being used for.
- lozenge 5y agoBut if my application only uses 100 schemas, I only care about a collision if it's with one of those 100.
- gpderetta 5y agoYou have a collision if any two schemas share the id, not if a specific schema collides with any of the others. So it is exactly like the birthday paradox.
- heavenlyblue 5y agoYeah, but that collision probably doesn’t matter because there’s a bunch of other variables that need to come together for it to be an issue at all.
- gpderetta 5y agoIf the schema id is the message id, in principle it could be an issue as the protocol on the wite would be ambiguous. Then again, you should be able to detect any collisions when you register a schema with the schema repo and deal with it at that time.
- deleted 5y ago[deleted]