  To defend against denial-of-service (DoS) attacks, we employ a technique
called resource burning (RB). RB is the verifiable expenditure of a resource,
such as computational power, required from clients before receiving service
from the server. To the best of our knowledge, we present the first DoS defense
algorithms where the algorithmic cost -- the cost to both the server and the
honest clients -- is bounded as a function of the attacker's cost.
  We model an omniscient, Byzantine attacker, and a server with access to an
estimator that estimates the number of jobs from honest clients in any time
interval. We examine two communication models: an idealized zero-latency model
and a partially synchronous model. Notably, our algorithms for both models have
asymptotically lower costs than the attacker's, as the attacker's costs grow
large. Both algorithms use a simple rule to set required RB fees per job. We
assume no prior knowledge of the number of jobs, the adversary's costs, or even
the estimator's accuracy. However, these quantities parameterize the
algorithms' costs.
  We also prove a lower bound on the cost of any randomized algorithm. This
lower bound shows that our algorithms achieve asymptotically tight costs as the
number of jobs grows unbounded, whenever the estimator output is accurate to
within a constant factor.
