Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cosmologically Unique IDs

jasonfantl.com

Post reply on HN
Print view View original

151–159 of 159 posts

Re: Cosmologically Unique IDs

#151

Post by Dylan16807 »

kmoser wrote: post #142
Dylan16807 wrote: post #121

Earlier quoted context omitted.

No, not every permutation. An atom gets to be in one larger object (recursively). Definitely no multiples. What would that even mean, also you would need unbounded space for multiples of just two atoms.

> Definitely no multiples. What would that even mean, also you would need unbounded space for multiples of just two atoms. I have a list and I want to assign a unique ID to each list item. Each list item itself contains one or more items: 1. My umbrella [ID "a"] and my sunglasses [ID "b"] 2. My umbrella ["a"], my sunglasses ["b"], and my umbrella ["a"] List item 2 contains two references to my umbrella [ID "a"].

So in a physical sense of identifying things that's nonsense. And again if you allow that then lists of just one or two atoms can take up infinite storage space. That's a super obvious reject. It makes no sense to even try to accommodate it in an ID system.

Re: Cosmologically Unique IDs

#153

Post by zeckalpha »

lisper wrote: post #7

This analysis is not quite fair. It takes into account locality (i.e. the speed of light) when designing UUID schemes but not when computing the odds of a collision. Collisions only matter if the colliding UUIDs actually come into causal contact with each other after being generated. So just as you have to take locality into account when designing UUID trees, you also have to take it into account when computing the o…

Don't forget that today's observable universe includes places that will never be able to see us because of the expansion of the universe being faster than the speed of light. There's a smaller sphere for the portion of the universe that we can influence.

Re: Cosmologically Unique IDs

#154

Post by kbelder »

exfalso wrote: post #128
lisper wrote: post #7

This analysis is not quite fair. It takes into account locality (i.e. the speed of light) when designing UUID schemes but not when computing the odds of a collision. Collisions only matter if the colliding UUIDs actually come into causal contact with each other after being generated. So just as you have to take locality into account when designing UUID trees, you also have to take it into account when computing the o…

There's a fun hypothesis I've read about somewhere, goes something like this: As the universe expands the gap between galaxies widens until they start "disappearing" as no information can travel anymore between them. Therefore, if we assume that intelligent lifeforms exist out there, it is likely that these will slowly converge to the place in the universe with the highest mass density for survival. IIRC we even know…

Assuming these are advanced enough aliens, they'll also be bringing with them all the mass they can, to accentuate the effect? I'm imagining things like Niven's ringworld star propulsion.

Re: Cosmologically Unique IDs

#155

Post by kbelder »

kmoser wrote: post #101

> A more reasonable upper limit might be to assume that every atom in the observable universe will get one ID (we assume atoms won’t be assigned multiple IDs throughout time, which is a concession). There are an estimated atoms in the universe. Using the same equation as above, we find that we need 532 bits to avoid (probabilistically) a collision up to that point. This doesn't take into account that you will inevita…

Wouldn't the minimum discrete unit be something that is capable of recording the ID? Or, if not, space somewhere would need to identify that that atom has this ID, which would take at least as much space.

In other words, the act of 'assignment' presupposes some mechanism of assignment, and at a certain level of granularity the information needed for that mechanism to function is greater than the information the system can store.

It would be like assigning each byte in a stick of ram a 32 bit random access ID, and trying to store the assignments in the same memory space. Memory addressing only works because we assume a linear, unchanging order.

Re: Cosmologically Unique IDs

#156

Post by kmoser »

kbelder wrote: post #155
kmoser wrote: post #101

> A more reasonable upper limit might be to assume that every atom in the observable universe will get one ID (we assume atoms won’t be assigned multiple IDs throughout time, which is a concession). There are an estimated atoms in the universe. Using the same equation as above, we find that we need 532 bits to avoid (probabilistically) a collision up to that point. This doesn't take into account that you will inevita…

Wouldn't the minimum discrete unit be something that is capable of recording the ID? Or, if not, space somewhere would need to identify that that atom has this ID, which would take at least as much space. In other words, the act of 'assignment' presupposes some mechanism of assignment, and at a certain level of granularity the information needed for that mechanism to function is greater than the information the syste…

If we're talking reality, sure. But you can also consider it a Gedankenexperiment.

Re: Cosmologically Unique IDs

#157

Post by linuxhansl »

nextaccountic wrote: post #119
linuxhansl wrote: post #92

Heh. I once had to make an argument that 256 bit randomly assigned identifiers are good enough without explicit collision checking. People wanted me to add complex and expensive collision checks. My argument was the 2^256 actually approaches the number of atom in the observable universe (within 1 to 3 orders of magnitude), and that collisions are so unlikely that we'll have millions of datacenter meltdowns first (all…

If the mechanism for generating those 256 random bits is distributed and untrusted parties generate ids, then you need collision detection because they may be malicious If it's not distributed you can just have a counter If it's distributed but coordinated by a single party (say, it's your servers), you can do sharding on incremented counters. Like, every server are assigned a region of ids

In this case it was distributed without our data centers (10k's machines or so at that time spread around the planet), but the code to generate ids was 100% under our control. Rather than inventing some distributed generation (or collision detection), a stateless approach with random numbers just seemed the right choice.

Re: Cosmologically Unique IDs

#158

Post by notepad0x90 »

nkrisc wrote: post #131
notepad0x90 wrote: post #130

Use a deck of cards for representation. 52 digits where 'K♠' for king-of-spades would be one character in Unicode. it isn't just cosmological unique, it's easier to read, harder to edit manually, and easier for our pattern recognition to keep track of. And best feature: anyone can generate a random id of such representation by getting a deck of cards and shuffling it properly. Playing cards are ubiquitous. I can see…

> shuffling it properly. I think you glossed over the big weakness in the idea.

is it harder than rolling a dice?

Re: Cosmologically Unique IDs

#159

Post by CableNinja »

UltraSane wrote: post #77
buzzerbetrayed wrote: post #41

Earlier quoted context omitted.

Getting the entire universe to agree on a single clock for creating timestamps sounds absurdly difficult. Probably impossible?

Neutron star spins collectively can be used as a pretty accurate clock.

How? You are here on earth, looking at a neutron star. It pulses about N times a minute. I am 5ly away, looking at the same neutron star. Yes, i see the pulses happening at about N times per second, but the pulse delay you see at time T(a) is not the same pulse delay i see at time T(a), it would be another 5 years before i see the same pulse you saw.
Post reply on HN