REST Authentication statlessness

I don't think 'statlessness' is a word but it will do :)

I'm attempting to create authentication for a REST service (PHP). I'm trying to make the service as stateless as possible. I read here(tip #4) that you shouldn't use $_SESSION which makes sen开发者_C百科se but it suggests using cookies as an alternative. I may have misunderstood what 'stateless' is but I can't see how a cookie is acceptable, I figured tokens was the way to go.

Can anyone explain how a cookie would acceptable in a stateless rest application and a session not?

---

$_SESSION is on the server, but cookies are persisted on the client and are attached to every request. So if you have multiple servers for your application a persisted state in a cookie still works, but not a persisted state in $_SESSION.

In conclusion: the server side must be stateless, but cookies are part of every request and therefore no "magic" state. The idea is that every equal request produces the same result.