With my latest thinking (not sure how much it differs from Vlad’s), sharding is actually not too hard. What you basically do is you have many betting cycles running in parallel, each with an ongoing randomly selected sub-quorum and each only dealing with transactions that declare themselves as only hitting a particular address range (eg. 0x0800…0x087f). Each betting cycle tries to confirm both the sub-blocks at that height and the state roots of the address ranges. All of these sub-quora are randomly selected from the global quorum, so attackers who can afford to take over a few percent of the global quorum can’t “target” any specific sub-quorum to corrupt, and shuffling is frequent.
Then, you have a second betting cycle at the top level containing the global quorum which tries to confirm the global state root; validators at the top level don’t validate every transaction; rather, they trust the results of the lower-level betting cycles (unless they have a specific reason not to, eg. they learn about some kind of exotic cryptoeconomic bribe attack that is going on and causing sub-quora to be byzantine). Note that you can stack this scheme on top of itself in an N-ary tree structure if you want if the number of sub-quora itself gets extremely large (eg. think 1m TPS with 1m validators and 100k sub-quora) so no single node actually needs to keep track of more than a fairly small number of sub-quora.
Re the deadlock/stalling problem, are you essentially talking about the kind of bivalence arguments you get from FLP impossibility?