Random with seed based on the previous block hash. That's not truly random but as you said true randomness would not allow network agreement.