Transaction rate limiters for peer-to-peer systems

     We introduce _transaction rate limiters_, new mechanisms that limit
(probabilistically) the maximum number of transactions a user of a
peer-to-peer system can do in any given period.  They can be used to
limit the consumption of selfish users and the damage done by malicious
users.  They complement reputation systems, solving the _traitor
problem_.  We give simple distributed algorithms that work over time
frames as short as seconds and are very robust: they use no trusted
servers and continue to work even when attacked by a large fraction of
users colluding.  Our algorithms are based on a new primitive we have
devised, _probably-anonymous queries_, which guarantees anonymity with a
specified probability.