Jeremy T. Fineman

Jeremy T. Fineman

Auto-generated profile, based on publicly available information

Jeremy T. Fineman

Georgetown University, Washington, D.C., USA

Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
21 December 2015
Verified
Conference Paper
Open access
MBMichael A. Bender
Michael A. Bender
JFJeremy T. Fineman
Jeremy T. Fineman
SGSeth Gilbert
Seth Gilbert
MYMaxwell Young
Maxwell Young
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.

23 August 2014 in Algorithmica
Verified
Journal Article
Closed access
PDF file
MBMichael A. Bender
Michael A. Bender
MFMartin Farach-Colton
Martin Farach-Colton
SFSándor P. Fekete
Sándor P. Fekete
JFJeremy T. Fineman
Jeremy T. Fineman
SGSeth Gilbert
Seth Gilbert

5 November 2015
Verified
Book Chapter
Closed access
PDF file
MDMichael Dinitz
Michael Dinitz
JFJeremy Fineman
Jeremy Fineman
SGSeth Gilbert
Seth Gilbert
CNCalvin Newport
Calvin Newport

10 June 2024
Verified
Conference Paper
Open access
JFJeremy T. Fineman
Jeremy T. Fineman
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.

2 January 2018
Verified
Book Chapter
Open access
KAKunal Agrawal
Kunal Agrawal
JDJoseph Devietti
Joseph Devietti
JFJeremy T. Fineman
Jeremy T. Fineman
ILI-Ting Angelina Lee
I-Ting Angelina Lee
RURobert Utterback
Robert Utterback
CXChangming Xu
Changming Xu
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.

26 May 2017 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
MBMichael A. Bender
Michael A. Bender
MFMartín Farach-Colton
Martín Farach-Colton
SFSándor P. Fekete
Sándor P. Fekete
JFJeremy T. Fineman
Jeremy T. Fineman
SGSeth Gilbert
Seth Gilbert
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.