Throttling in a cloud environment?

Hello colleagues,
I am facing an issue I can not find resolution to:
In my application I am using throttling to limit access to a procedure in the database. The reason I'm doing it is because in certain cases the procedure can take long time to process, and users tend to repeat the invocation, thus overloading the server. So I have implemented a per-user custom throttling, that allows the user to repeat the request, but if the lock is not released within a couple of seconds an error is thrown, notifying the user to wait until the previous execution completes.

That works excellent when using a single JVM, but I am not sure how to make this work in a cloud environment. Is there any «cloud-ready» throttling implementation? How does one do synchronisation in a cloud/distributed environment?

For reasons beyond my control I can not change the Database Procedure and I have to implement this on top.

Please advise.