Actually, my thinking here has evolved somewhat. The ordering actually doesn’t need to be on-chain at all, which frees us up to provide huge amounts of regions to each parachain.
The on-chain behavior should be that when a parachain candidate is posted to the relay-chain, it is accompanied by the region that it will be part of, and then the on-chain logic will check that region and ensure that it is both assigned to the parachain and is in surplus. And it will check that the block is backed by the validators assigned to the core the region occupies. Each region should have a UUID to make this light.
Then, the Regions pallet only needs to store a simple mapping Regions: RegionId -> Region. The RegionID can be determined in a variety of ways, but the simplest is probably to determine it at creation time Hash(parent_hash ++ region_index) where parent_hash is the parent block hash of the current relay-chain block and region_index refers to the number of regions which have been created in this block.
We have a choice of who determines which region each parachain block is assigned to. Option 1 is to have relay-chain validators (in particular, the relay-chain block author, which packs backable candidates into the block) figure this out. Option 2 is to alter the CandidateReceipt format to explicitly commit to the region ID.
Long-term, I lean towards Option 2, because it opens up more avenues for “region-aware collation protocols” (Cumulus Consensus Modules) and collators don’t have to guess what validators will do.
Short-term, some variation of Option 1 will be easier to implement, but likely won’t scale to large quantities of regions, especially if they change hands often.