Why are tokens considered stateless?

So I have kind of an issue to understand why "tokens" have so much hype in the differents new web technologies for authentification.

I understand it's meant to improve the controls you can "loose" when using cookies and session. But a lot of people are talking about the fact that it sticks to the Restful "ideology" by allowing a client-server communication to be Stateless.

But... does it ? I mean, a stateless communication means that the server doesn't have to store any informations on the client for auth, and that requests are 100% independant from one to another.

In the case of tokens :

• 
  

  Server obviously needs to store those ( just as the client in most cases of applications if you want to keep token over restart) so, both client and server does have a states.

  
  


• 
  

  Client need to poll "/get token" in order to be able to request anything else, and the result of this request shut the result of any further requests in. So in other words, if I was designing a state diagram, my diagram would consist of more than one state.

  
  

So to me, tokens are nothing close to what we could call a "stateless" communication (which is a necessary condition for a architecture to be Restful).

By the way, I think HTTP credentials are closer to achieve a stateless communication, because basically, even if the server still have a state by storing the credentials, the auth+request process rely on only one single request, (as credentials are full part of the very first request of an HTTP "conversation").

One other point HTTP credentials hit better than tokens is the "Client/server roles" in Restful API. This point states that a RESTFul communication split client and server, meaning inter alia that the client doesn't have to deal with data storage. But in the case of token, they definitly needs to be stocked, at least temporarily (and even more if (for exemple) you want the browser to keep the token after a restart by using cookies or localstorage). In contrast, HTTP cred can be filled in by the user at every request of a conversation making the client non-data-storing just as it should be in Restful representation.

Also I wanted to point out that according to Rest architecture, any information held by the client should on it's own be enough for the client to decide weither or not he should delete/modify it, which is not the case with 99% of tokens system that doesn't make the client store tokens' timeout date (where cookies does).

So in conclusion, a lot of people are blaming HTTP creds or session for violating the Restfulness of an architecture. But tokens systems doesn't solve the issue at all, does it ?