Can anyone point me towards discussion or best thinking on how relays could efficiently sync with one another? Nostr events are not strictly ordered, so in general clients use >=${timestamp} queries to get the new ones. This works when there aren’t many relays and propagation is global and instant, but in a decentralized system at scale it seems like a problem.

I’m thinking about the following scenario:

Alice posts ten events from her device D1 which are sent to relay R1. Then she logs into her device D2 and posts ten events to relay R2. How can relay R1 and R2 reconcile so that they both have all of Alice's posts? In the worst case they have to ask the other relay for all posts from Alice and then do set intersection to find the difference.

If Alice only has 10 events on each relay this is cheap, but if Alice has 1000 events and there are 100 million Alices and 10,000 relays then you have a problem. I feel like this scenario could show up in many forms in a network of relays trying to stay in sync. It could happen when spinning up a new relay, when one relay has downtime, if a client publishes a message while offline, when a user's devices have different sets of relays, etc.