A distributed system may be modeled by objects that run concurrently, each with its own processor, and communicate by remote method calls. However objects may have to wait for response to external calls; which can lead to inefficient use of processor capacity or even to deadlock. This paper addresses this limitation by means of asynchronous method calls and conditional processor release points. Although at the cost of additional internal nondeterminism in the objects, this approach seems attractive in asynchronous or unreliable distributed environments. The concepts are illustrated by the small object-oriented language Creol and its operational semantics, which is defined using rewriting logic as a semantic framework. Thus, Creol specifications may be executed with Maude as a language interpreter, which allows an incremental development of the language constructs and their operational semantics supported by testing in Maude. However, for prototyping of highly non-deterministic systems, Maude’s deterministic engine may be a limitation to practical testing. To overcome this problem, a rewrite strategy based on a pseudo-random number generator is proposed, providing Maude with nondeterministic behavior.