Can we make a denial-of-service attacker pay more than the server and honest clients? Consider a model where a server sees a stream of jobs sent by either honest clients or an adversary. The server sets a price for servicing each job with the aid of an estimator, which provides approximate statistical information about the distribution of previously occurring good jobs. We describe and analyze pricing algorithms for the server under different models of synchrony, with total cost parameterized by the accuracy of the estimator. Given a reasonably accurate estimator, the algorithm's cost provably grows more slowly than the attacker's cost, as the attacker's cost grows large. Additionally, we prove a lower bound, showing that our pricing algorithm yields asymptotically tight results when the estimator is accurate within constant factors.

Abstract. Contention resolution addresses the problem of coordinating access to a shared communication channel. Time is discretized into synchronized slots, and a packet transmission can be made in any slot. A packet succeeds if it is the only packet transmitted during that slot. If two or more packets are sent in the same slot, then these packets collide and fail. Listening on the channel during a slot provides ternary feedback, indicating whether that slot had (0) silence, (1) a successful transmission, or (2+) noise. No other feedback or exchange of information is available to packets. Packets are (adversarially) injected into the system over time. A packet departs the system once it succeeds. The goal is to ensure all packets succeed, while optimizing throughput, which entails optimizing the fraction of successful slots. Most prior contention resolution algorithms with constant throughput require a short feedback loop, in the sense that a packet’s sending probability in slot [Formula: see text] is fully determined by its internal state at slot [Formula: see text] and the channel feedback at slot [Formula: see text]. This paper answers the question of whether these short feedback loops are necessary; that is, how often must listening and updating occur in order to achieve constant throughput? A shared channel can also suffer random or adversarial noise (modeled as jamming), even when no packets are actually sent. How does noise affect our goal of long feedback loops/energy efficiency? Tying these questions together, we ask the following: What does a contention-resolution algorithm have to sacrifice to reduce channel accesses? Must we give up on constant throughput? What about robustness to noise? Here, we show that we need not concede anything by presenting an algorithm with the following guarantees. Suppose there are [Formula: see text] packets arriving over time and [Formula: see text] jammed slots, where the input is determined by an adaptive adversary. With high probability in [Formula: see text], our algorithm guarantees [Formula: see text] throughput and [Formula: see text] channel accesses (sends or listens) per packet. We also have analogous guarantees when the input stream is infinite—we prove implicit throughput bounds of [Formula: see text] for all time slots [Formula: see text], and this translates to [Formula: see text] guaranteed throughput for any slot [Formula: see text] where the implicit throughput is sufficiently small in [Formula: see text]. As a special case, these throughput results give rise to adversarial-queuing theory guarantees.

Contention resolution addresses the problem of coordinating access to a shared communication channel. Time is discretized into synchronized slots, and a packet transmission can be made in any slot. A packet is successfully sent if no other packet is also transmitted during that slot. If two or more packets are sent in the same slot, then these packets collide and fail. Listening on the channel during a slot provides ternary feedback, indicating whether that slot had (0) silence, (1) a successful transmission, or (2+) noise. No other feedback or exchange of information is available to packets. Packets are (adversarially) injected into the system over time. A packet departs the system once it is successfully sent. The goal is to send all packets while optimizing throughput, which is roughly the fraction of successful slots.

Backoff algorithms are used in many distributed systems where multiple devices contend for a shared resource. For the classic balls-into-bins problem, the number of singletons—those bins with a single ball—is important to the analysis of several backoff algorithms; however, existing analyses employ advanced probabilistic tools. Here, we show that standard Chernoff bounds can be used instead, and the simplicity of this approach is illustrated by re-analyzing some well-known backoff algorithms.

A Sybil attack occurs when an adversary pretends to be multiple identities (IDs). Limiting the number of Sybil (bad) IDs to a minority is critical to the use of well-established tools for tolerating malicious behavior, such as Byzantine agreement and secure multiparty computation. A popular technique for enforcing a Sybil minority is resource burning: verifiable consumption of a network resource, such as computational power, bandwidth, or memory. Unfortunately, typical defenses based on resource burning require non-Sybil (good) IDs to consume at least as many resources as the adversary. Additionally, they have a high cost, even when the system membership is relatively stable. Here, we present a new Sybil defense, ERGO, that guarantees (1) there is always a minority of Sybil IDs; and (2) when the system is under significant attack, the good IDs consume asymptotically less than the bad. In particular, for churn rate that can vary exponentially, the resource burning rate of ERGO is, where is the resource burning rate of the adversary, and is the join rate of good IDs. We empirically evaluate ERGO alongside prior Sybil defenses. Unlike other Sybil defense, ERGO can be combined with machine learning techniques for identifying Sybil IDs, in a way that maintains its theoretical guarantees. Based on our experiments comparing ERGO with two state-of-the-art Sybil defenses, we show that ERGO improves by up to 2 orders of magnitude without machine learning, and up to 3 orders of magnitude using machine learning.

In the contention-resolution problem, multiple players contend for access to a shared resource. Contention resolution is used in wireless networks, where messages must be transmitted on a shared communication channel. When two or more messages are transmitted at the same time, a collision occurs, and none of the transmissions succeed. Much of the theoretical work on contention resolution has focused on efficiently resolving collisions in order to obtain throughput guarantees.

A common tool to defend against Sybil attacks is proof-of-work, whereby computational puzzles are used to limit the number of Sybil participants. Unfortunately, current Sybil defenses require significant computational effort to offset an attack. In particular, good participants must spend computationally at a rate that is proportional to the spending rate of an attacker. In this paper, we present the first Sybil defense algorithm which is asymmetric in the sense that good participants spend at a rate that is asymptotically less than an attacker. In particular, if T is the rate of the attacker's spending, and J is the rate of joining good participants, then our algorithm spends at a rate f O(√(TJ) + J). We provide empirical evidence that our algorithm can be significantly more efficient than previous defenses under various attack scenarios. Additionally, we prove a lower bound showing that our algorithm's spending rate is asymptotically optimal among a large family of algorithms.

Randomized exponential backoff is a widely deployed technique for coordinating access to a shared resource. A good backoff protocol should, arguably, satisfy three natural properties: (1) it should provide constant throughput, wasting as little time as possible; (2) it should require few failed access attempts, minimizing the amount of wasted effort; and (3) it should be robust, continuing to work efficiently even if some of the access attempts fail for spurious reasons. Unfortunately, exponential backoff has some well-known limitations in two of these areas: it can suffer subconstant throughput under bursty traffic, and it is not robust to adversarial disruption. The goal of this article is to “fix” exponential backoff by making it scalable, particularly focusing on the case where processes arrive in an online, worst-case fashion. We present a relatively simple backoff protocol, R e -B ackoff , that has, at its heart, a version of exponential backoff. It guarantees expected constant throughput with dynamic process arrivals and requires only an expected polylogarithmic number of access attempts per process. R e -B ackoff is also robust to periods where the shared resource is unavailable for a period of time. If it is unavailable for D time slots, R e -B ackoff provides the following guarantees. For n packets, the expected number of access attempts for successfully sending a packet is O (log 2 ( n + D )). For the case of an infinite number of packets, we provide a similar result in terms of the maximum number of processes that are ever in the system concurrently.

A popular technique for tolerating malicious faults in open distributed systems is to establish small groups of participants, each of which has a non-faulty majority. These groups are used as building blocks to design attack-resistant algorithms. Despite over a decade of active research, current constructions require group sizes of O(log n), where n is the number of participants in the system. This group size is important since communication and state costs scale polynomially with this parameter. Given the stubbornness of this logarithmic barrier, a natural question is whether better bounds are possible. Here, we consider an attacker that controls a constant fraction of the total computational resources in the system. By leveraging proof-of-work (PoW), we demonstrate how to reduce the group size exponentially to O(log log n) while maintaining strong security guarantees. This reduction in group size yields a significant improvement in communication and state costs.

For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices seek access to a shared resource. Despite this history, the performance of standard exponential backoff is poor under worst-case scheduling of demands on the resource: (i) subconstant throughput can occur under plausible scenarios, and (ii) each of $N$ devices requires $\Omega(\log N)$ access attempts before obtaining the resource. In this paper, we address these shortcomings by offering a new backoff protocol for a shared communication channel that guarantees expected constant throughput with only $O(\log(\log^* N))$ channel accesses in expectation, even when packet arrivals are scheduled by an adversary. Central to this result are new algorithms for approximate counting and leader election with the same performance guarantees.

Randomized binary exponential backoff (BEB) is a popular algorithm for coordinating access to a shared channel. With an operational history exceeding four decades, BEB is currently an important component of several wireless standards. Despite this track record, prior theoretical results indicate that under bursty traffic (1) BEB yields poor makespan and (2) superior algorithms are possible. To date, the degree to which these findings manifest in practice has not been resolved.

Randomized exponential backoff is a widely deployed technique for coordinating access to a shared resource. A good backoff protocol should, arguably, satisfy three natural properties: (i) it should provide constant throughput, wasting as little time as possible; (ii) it should require few failed access attempts, minimizing the amount of wasted effort; and (iii) it should be robust, continuing to work efficiently even if some of the access attempts fail for spurious reasons. Unfortunately, exponential backoff has some well-known limitations in two of these areas: it provides poor (sub-constant) throughput (in the worst case), and is not robust (to adversarial disruption). The goal of this paper is to “fix” exponential backoff by making it scalable, particularly focusing on the case where processes arrive in an on-line, worst-case fashion. We present a relatively simple backoff protocol, Re-Backoff, that has, at its heart, a version of exponential backoff. It guarantees expected constant throughput with dynamic process arrivals and requires only an expected polylogarithmic number of access attempts per process. Re-Backoff is also robust to periods where the shared resource is unavailable for a period of time. If it is unavailable for D time slots, Re-Backoff provides the following guarantees. When the number of packets is a finite n, the average expected number of access attempts for successfully sending a packet is O(log2(n + D)). In the infinite case, the average expected number of access attempts for successfully sending a packet is O(log2(η + D)) where η is the maximum number of processes that are ever in the system concurrently.

For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices seek access to a shared resource. Surprisingly, despite this history, the performance of standard backoff is poor under worst-case scheduling of demands on the resource: (i) subconstant throughput can occur under plausible scenarios, and (ii) each of N devices requires Omega(log N) access attempts before obtaining the resource.

We consider the problem of broadcasting a message from a sender to n ≥ 1 receivers in a time-slotted, single-hop, wireless network with a single communication channel. Sending and listening dominate the energy usage of small wireless devices and this is abstracted as a unit cost per time slot. A jamming adversary exists who can disrupt the channel at unit cost per time slot, and aims to prevent the transmission of the message. Let T be the number of slots jammed by the adversary. Our goal is to design algorithms whose cost is resource-competitive, that is, whose per-device cost is a function, preferably o(T), of the adversary's cost. Devices must work with limited knowledge. The values n, T, and the adversary's jamming strategy are unknown.

There are several analytical results on distributed hash tables (DHTs) that can tolerate Byzantine faults. Unfortunately, in such systems, operations such as data retrieval and message sending incur significant communication costs. For example, a simple scheme used in many Byzantine fault-tolerant DHT constructions ofnnodes requiresO(log3n) messages; this is likely impractical for real-world applications. The previous best known message complexity isO(log2n) in expectation. However, the corresponding protocol suffers from prohibitive costs owing to hidden constants in the asymptotic notation and setup costs. In this paper, we focus on reducing the communication costs against a computationally bounded adversary. We employ threshold cryptography and distributed key generation to define two protocols, both of which are more efficient than existing solutions. In comparison, our first protocol is deterministic withO(log2n) message complexity, and our second protocol is randomized with expectedO(logn) message complexity. Furthermore, both the hidden constants and setup costs for our protocols are small, and no trusted third party is required. Finally, we present results from microbenchmarks conducted over PlanetLab showing that our protocols are practical for deployment under significant levels of churn and adversarial behavior.

Consider a time-slotted, single-hop, wireless sensor network consisting of n correct devices and and f•n Byzantine devices where f≥0 is any constant; the Byzantine devices may or may not outnumber the correct ones. There exists a trusted sender Alice who wishes to deliver a message m over a single channel to the correct devices. There is also an evil user Carol who controls the Byzantine devices and uses them to disrupt the communication channel. For a constant k≥2, the correct and Byzantine devices each possess a meager energy budget of O(n1/k), Alice and Carol each possess a limited budget of Õ(n1/k), and sending or listening in a slot incurs unit cost. This setup captures the inherent challenges of guaranteeing communication despite scarce resources and attacks on the network. Given this Alice versus Carol scenario, we ask: Is communication of m feasible and, if so, at what cost?

Imagine that Alice wants to send a message m to Bob, and that Carol wants to prevent this. Assume there is a communication channel between Alice and Bob, but that Carol is capable of blocking this channel. Furthermore, there is a cost of S dollars to send on the channel, L dollars to listen on the channel and J to block the channel. How much will Alice and Bob need to spend in order to guarantee transmission of m?

There are several analytical results on distributed hash tables (DHTs) that can tolerate Byzantine faults. Unfortunately, in such systems, operations such as data retrieval and message sending incur significant communication costs. For example, a simple scheme used in many Byzantine fault-tolerant DHT constructions of n nodes requires O(log3n) messages, this is likely impractical for real-world applications. The previous best known message complexity is O(log2n) in expectation, however, the corresponding protocol suffers from prohibitive costs owing to hidden constants in the asymptotic notation and setup costs. In this paper, we focus on reducing the communication costs against a computationally bounded adversary. We employ threshold cryptography and distributed key generation to define two protocols both of which are more efficient than existing solutions. In comparison, our first protocol is deterministic with O(log3n) message complexity and our second protocol is randomized with expected O(log n) message complexity. Further, both the hidden constants and setup costs for our protocols are small and no trusted third party is required. Finally, we present results from micro benchmarks conducted over PlanetLab showing that our protocols are practical for deployment under significant levels of churn and adversarial behaviour.

We address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem that we call the Bad Santa problem. Our results on this problem apply for any situation where: 1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and 2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a Θ(√n) expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log* n) times (i.e. in O(log* n) rounds each consisting of the n time slots), then listening to O(log* n) expected number of time slots suffices. We show that this is near optimal.