You generally get around the "nothing at stake" problem by requiring validators (consensus-forming nodes) to submit a deposit that is subject to deletion upon proof of bad behavior. For example, if I get two conflicting messages signed by you in Ethereum's Casper network, I can present that data as proof to the Casper smart contract where you lose your deposit.
