It's not state what causes problems in scalability but keeping up with state.
I don't know if you are to design a REST interface, which is about state transfer, not statelesness. Statelesness would mean, that doing the same action twice has the same result.
This doesn't even apply to HTTP. If you do a DELETE request twice, the second one is pretty much supposed to fail.
In servers, the problem with state is usually its mutability:
- getting half-changed data (eg, if a Knight in chess moves, both coordinates change. If part of the system would get data with only one of the coordinates changed, there'd be potential trouble)
- data changing between transfer: suppose A calls B, and both use C. A is assuming C has a certain state, and expects B to behave accordingly. Yet in the meanwhile, C has changed, and B is acting differently. Bugs happen.
Also, there's a problem with concurrency:
- parallel components getting different state and thinking theirs is right: this is called conflict. An example would be, when in a realtime game, you hit an opponent, an opponent also hits you, and both shots are fatal. Each of them would think the other one is dead and they've won
And finally, there's a problem with storage&retrieval and failure:
- dying components: suppose there's a webshop, and the user has a basket. If the basket is maintained by a single compoennt, it could die if there are too many customers. If it is managed by 10 components, each of them managing a subset of customers, what happens if the component which was managing the current user's state dies?
So, state is normal. It's part of life. Computers are about interactions: a non-interactive computer is called book or newspaper, or rather, a poster (as a book has both open and closed states). Interaction changes state. While we try to minimize maintenance of state, we can't avoid it by nature.