People have proposed requiring the client system to do work as a way of limiting/mitigating DOS attacks, and others have countered that it isn't fair to small devices (eg, phones) as there may be 1-3 orders of magnitude difference in computing power between clients. Thus a followon proposal is many schemes which just force a client to WAIT when the server is under load. I've heard of some rather complicated schemes to do so.
There is a VERY easy way to do this, however:
The server, on startup, creates a random key.
When it gets a request from a client, and it wants the client to wait, it sends back a message saying "Wait x seconds + resend with this cookie". The cookie being E(K, time its allowed, IP). Now the client waits and resends the request with the cookie.
Voila, the clients wait for the specificed time, without the server having to store any per-client state or worry about any delay queue being filled. It requires only ONE encryption operation to create and one to verify, which on a modern CPU is only about a few hundred clock cycles.
So if your DOS-mitigation technique involves having new clients wait, this is all you need.