A typical RESTful API:
PUT new data to resource x/y/z
An asynchronous non RESTful API:
POST job information for resource x/y/z
GET status of job for resource x/y/z until status is complete.
GET results of job for resource x/y/z
It's all just relative though. If the resource is the job itself, then you have CRUD over REST for the job resource. The queue processing the job is a RESTful consumer as well, updating the job with information about the resulting new resource.
That is all RESTful. Whether or not its useful is a different question.
I think you left the realm of REST and reached out to the application level in order to make an non-existing case.
Your second example is only asynchronous in so far as you are oblivious to the completion of of the request, but that hardly makes it non-Restful. To me both of your examples are REST by definition.
