This has been bugging me for a while now. I'm not as worried about it as I was before though. Here are some thoughts:
Lars says there are ways around the problem:
Of course there are ways around. You need to parallelize. In an auction contract, for example, you can have several UTxO's instead of just one.
This seems fine to me. Of course there is still a chance of collision. A collision isn't the end of the world, but you could make as many UTxOs as you want to minimize the worry. You can also do things off-chain to pseudo-randomly choose a UTxO (with the modulo of your hashed redeemer, for example).
Back of napkin estimates
If you look at something like Uniswap, which has on the order of ~100K transactions/day and ~50 Liquidity pools. Cardano has 4320 blocks/day, so that would be an average of around .5 tx/block/lp (obviously some pools are much more popular). But having somewhere between 10-100 UTxO/pool should be plenty.
How does it work?
EDIT: This actually still has problems. I can't think of how you would determine the rates without including all the UTxOs in a txn--which defeats the purpose. Hmm, still need to think things through.
For a Uniswap, the way it could work is the sum of all the datums on liquidity pool NFT UTxOs in a pool equal the total liquidity for that pool. Anyone adding or removing from the pool can modify any number of the UTxOs, but for the sake of fees they would tend to modify the minimum number necessary to add/remove from the pool. For pools with a lot of collisions, there might even be a way to incentivize participants to open new pools or even add more UTxOs to existing pools perhaps? The factory token would just need to keep track of how many liquidity NFTs are floating around for each pool.
