Maintaining Random Assignments under Adversarial Dynamics

Bernhard Haeupler, Anton Paramonov · 2026

Read Maintaining Random Assignments under Adversarial Dynamics by Bernhard Haeupler, Anton Paramonov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-05606.txt.

Introduction

Haeupler and Paramonov keep random assignments fresh under hostile, adaptive changes with few resamples per change. They expose a time-selection attack that skews even proactive resampling and answer with a time-aggregation rule plus two new schemes. The headline use keeps graph coloring near best with sublinear mean work per change.

Catalog record

CREATORBernhard Haeupler, Anton Paramonov
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE120770
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.05606

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Maintaining Random Assignments under Adversarial Dynamics Bernhard Haeupler, Anton Paramonov Abstract We study and further develop powerful general-purpose schemes to maintain random assignments under adversarial dynamic changes. The goal is to maintain assignments that are (approximately) distributed similarly as a completely fresh resampling of all assignments after each change, while doing only a few resamples per change. This becomes particularly interesting and challenging when dynamics are controlled by an adaptive adversary. Our work builds on and further develops the proactive resampling technique [Bhattacharya, Saranurak, and Sukprasert ESA’22]. We identify a new “temporal selection” attack that adaptive adversaries can use to cause biases, even against proactive resampling. We propose a new ”temporal aggregation” principle that algorithms should follow to counteract these biases, and present two powerful new resampling schemes based on this principle. We give various applications of our new methods. The main one in maintaining proper coloring of the graph under adaptive adversarial modifications: we maintain O ⁡ ( Δ ) O(\Delta) coloring for general graphs with maximum degree Δ \Delta and O ⁡ ( Δ ln ⁡ Δ ) O(\frac{\Delta}{\ln\Delta}) coloring for triangle free graphs, both with sublinear in the number of vertices average work per modification. Other applications include efficiently maintaining random walks in dynamically changing graphs. 1 Introduction Randomness is a remarkably effective organizing principle across many computational and algorithmic settings. It naturally balances load, prevents concentration of adversarial influence, and ensures that local irregularities do not aggregate into global bias. Yet, in many real-world or algorithmic systems, the underlying structure changes continuously—participants join or leave, resources become unavailable, or edges in a network appear and disappear. The challenge, then, is not merely to generate a good random assignment once, but to maintain such assignments as the system evolves. The central question of this work is: How can we maintain random-like assignments under ongoing, potentially adversarial dynamics, while making only a few updates per change? We begin by illustrating why random assignments are beneficial through three settings. These settings are of increasing generality and complexity and will serve as running examples throughout this paper. Participant–Group Assignment. Consider a setting with many participants that must be divided into several groups. A good example is a distributed peer-to-peer system in which groups are used to distribute work or storage (of a distributed hash table) among participants. A fraction of these participants may be malicious, yet their identities are not known. In this setting, assigning each participant to a group uniformly at random offers several advantages. First, it ensures that group sizes remain balanced. Second, if the overall fraction of malicious participants is less than one half, then with high probability, each group will contain a majority of honest participants. Finally, random assignments satisfy many natural fairness notions (e.g., no participant can choose its group) and minimize the chances of small groups of colluding participants being placed in the same group. Job–Machine Assignment. Consider a system consisting of jobs and machines, where each job can be processed by several routines eligible for this job, and each routine is performed by a subset of machines. A natural randomized strategy to achieve effective load balancing without requiring centralized coordination is to assign each job to a uniformly random routine. Node–Random Walk Assignment. Random walks and branching random walks have a wide variety of applications. The famous PageRank [ 5 ] measure of importance corresponds to expected times to be visited when running a random walk of geometric length from every node in a network. Random walks are also used in popular ML features for node similarity in networks, including node2vec [ 11 ] , using the idea that branching random walks started from similar nodes encounter the same nodes or regions of a graph more often than dissimilar ones. Overall, assigning to each node in a network one or multiple (branching) random walks and using the dispersion, concentration, mixing, and other properties of random walks to estimate, define, and measure properties of nodes within a network has been a powerful and widely used paradigm across sciences. Random walks can also be used to distribute traffic evenly and keep network congestion low, as for example done by many oblivious routing schemes [ 8 , 9 , 1 , 17 , 16 , 14 ] . In each of these settings, pure randomization performs well in a static world. But when the system evolves dynamically, e.g., participants join and leave, or edges are being deleted, naive strategies fail and assignments lose their random properties. A natural countermeasure against this is to rerandomize the entire system after each modification, thereby restoring a perfectly random configuration. Yet this comes with an enormous computational overhead—one that might not even be necessary: perhaps similar distributions can be achieved with only limited, carefully chosen updates. The difficulty of maintaining a (close to) random assignment increases even further when system updates are not arbitrary but chosen adversarially in response to the algorithm’s previous actions. An adaptive adversary might, for instance, repeatedly join and leave the system until it lands in a particular group, or selectively delete edges to steer random walks toward a specific region of the graph. These manipulations can create highly biased, undesirable distributions. This paper focuses on precisely this problem: how to preserve strong distribution guarantees efficiently even under adaptive, potentially malicious dynamics. We identify limitations and vulnerabilities of existing methods and introduce new algorithmic tools that maintain provable distribution guarantees with low resampling cost. 2 Related Work We now formally define the two settings - the Participant-Group Assignment and Job-Machine Assignment. We provide especially in-depth formulations so as to present concrete, formal examples of the results that can be obtained. 2.1 Participant-Group Setting: Problem-specific Cuckoo/Rotate Rules We start by looking more formally at the participant-group setting in which a large number of participants must be continuously assigned to g groups. Participants are indistinguishable to the system: when they join, leave, or rejoin, the assignment algorithm cannot tell whether it is interacting with a new or returning individual. The system evolves dynamically as participants repeatedly join and leave, and upon each join, the newcomer is assigned uniformly at random to one of the groups. If the schedule of joins and departures is oblivious , that is, independent of the random outcomes of the assignment process, then the configuration at any fixed time is distributed uniformly and satisfies all previously mentioned desirable fairness, robustness, and load-balancing properties. However, if some participants are malicious, they can leave and immediately rejoin the system, thereby triggering an adversarial resample , and these resamples can be scheduled adaptively : a participant may decide whether to trigger a resample after observing its current assignment or state of the system. This adaptivity enables malicious participants to severely bias the resulting assignment in what is commonly called a join-leave attack . Theoretically sound methods for preventing such attacks were proposed by Scheideler and Awerbuch in [ 4 , 13 ] . We paraphrase their ideas and results for the context of the group assignment setting, which we define formally next: Participant-Group Assignment Setting There are n participants, g groups, and a \beta fraction of malicious participants. Initially, every participant gets assigned a random group. At

Read the complete text