I know gas prices and nonce are used. But what if different clients use different ordering of transactions? How do thousands of nodes agree on exact transactions to be included in the next block? And how does a transaction get propagated through network at all? How can you have such consistency?
They take turns. By competing. Who is delegated the authority to publish a block is decided by a consensus mechanism. This mechanism for how to agree by majority consensus to a computer program, solving "How do nodes agree on which transactions to include in the block?", is what Satoshi Nakamoto invented in 2008. The invention solves a social problem, and that's the reason "blockchain" became so big so fast, socially. It is analogous to the invention of majority consensus in a democracy by having "blocks" of 4 years with political parties delegated authority for that period, another invention that became very big and impacts your everyday life.
How does a transaction get propagated through network at all?
To send a transaction to the blockchain you must access a node. In this prospect, you can :
- Run your own node using a client such as Geth or Parity.
- Trust a public node using a service such as Infura.
- Trust a wallet that does all the work for you.
After receiving your transaction, your node will propagate it to its peers who will propagate it to their peers and so on, based on a P2P protocol.
What if different clients use different ordering of transactions? How do thousands of nodes agree on exact transactions to be included in the next block?
Each miner builds their own block independently, that means minerA and minerB will not necessary include the same transactions in their respective block. However they will both privilege the transactions with the higher gas fees.
Once a miner finds the solution to the consensus algorithm, he broadcasts its candidate block to the other nodes which verify the validity of the solution and execute each transaction of the block. The new proposed block is added to the blockchain if the majority of miners agree.