"Agreement" of time is probably nonsense, yeah. I realized after posting so I edited in the parenthetical, but as [3] notes, locality probably makes this less of a real issue.

Apparently with the birthday paradox 32 bit random IDs only allow some tens of thousands per second before collision chance passes 50%. Maybe that's acceptable?

[3]: https://news.ycombinator.com/item?id=47065241

The temperature of the cosmic microwave background can be used as a universal clock.

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