Routing messages using unreliable routing data. A method includes receiving a message from a computer readable communication medium. Characteristic properties of the message are calculated so as to determine state requirements for a service instance at a service for processing of the message. An attempt is made to acquire an appropriate service instance that satisfies the state requirements for processing the message. A determination is made that attempting to acquire an appropriate service instance that satisfies the state requirements for processing the message is not successful at acquiring an appropriate service instance. As a result, the message is redirected using an unreliable local cache of routing information and without coordination between processing nodes.