Non-blocking processing of federated transactions may be implemented for distributed data partitions. A transaction may be received that specifies keys at data nodes to lock in order to perform the transaction. Lock requests are generated and sent to the data nodes which identify sibling keys to be locked at other data nodes for the transaction. In response to receiving the lock requests, data nodes may send to lock queues indicating other lock requests for the keys at the data node. An evaluation of the lock queues based, at least in part, on an ordering of the lock requests in the lock queues may be performed to identify a particular transaction to commit. Once identified, a request to commit the identified transaction may be sent to the particular data nodes indicated by the sibling keys in a lock request for the identified transaction.