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.
This paper presents a randomized algorithm for single-source shortest paths on directed graphs with real (both positive and negative) edge weights. Given an input graph with n vertices and m edges, the algorithm completes in Õ(mn8/9) time with high probability. For real-weighted graphs, this result constitutes the first asymptotic improvement over the classic O(mn)-time algorithm variously attributed to Shimbel, Bellman, Ford, and Moore.
A program is said to have a determinacy race if logically parallel parts of a program access the same memory location and one of the accesses is a write. These races are generally bugs in the program since they lead to non-deterministic program behavior — different schedules of the program can lead to different results. Most prior work on detecting these races focuses on a subclass of programs with series-parallel or nested parallelism. This paper presents a race-detection algorithm for detecting races in a more general class of programs, namely programs that include arbitrary ordering constraints in additional to the series-parallel constructs. The algorithm performs a serial execution of the program, augmented to detect races, in O(T1 + k2) time, where T1 is the sequential running time of the original program and k is the number of non series-parallel constraints. The main technical novelty of this paper is a new data structure, R-Sketch, for answering reachability queries in nearly series-parallel (SP) directed acyclic graphs (DAGs). Given as input a graph comprising an n-node series parallel graph and k additional non-SP edges, the total construction time of the data structure is O(n + k2), and each reachability query can be answered in O(1) time. The data structure is traversally incremental, meaning that it supports the insertion of nodes/edges, but only as they are discovered through a graph traversal.
Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. When previously allocated blocks cannot be moved, this problem is called the memory allocation problem. The competitive ratio for this problem has matching upper and lower bounds that are logarithmic in the number of requests and in the ratio of the largest to smallest requests. This article defines the storage reallocation problem, where previously allocated blocks can be moved, or reallocated , but at some cost. This cost is determined by the allocation/reallocation cost function . The objective is to minimize the storage footprint, that is, the largest memory address containing an allocated object, while simultaneously minimizing the reallocation costs. This article gives asymptotically optimal algorithms for storage reallocation, in which the storage footprint is at most (1+ ϵ) times optimal, and the reallocation cost is O ((1/ϵ)log (1/ϵ)) times the original allocation cost, that is, it is within a constant factor of optimal when ϵ is a constant. The algorithms are cost oblivious , which means they achieve these bounds with no knowledge of the allocation/reallocation cost function, as long as the cost function is subadditive.