Arrow Research search

Author name cluster

Thomas Sauerwald

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

SODA Conference 2023 Conference Paper

Balanced Allocations with Heterogeneous Bins: The Power of Memory

  • Dimitrios Los
  • Thomas Sauerwald
  • John Sylvester 0001

We consider the allocation of m balls (jobs) into n bins (servers). In the standard TWO-CHOICE process, at each step t = 1, 2, …, m we first sample two bins uniformly at random and place a ball in the least loaded bin. It is well-known that for any m  n, this results in a gap (difference between the maximum and average load) of log 2 log n + θ(1) (with high probability). In this work, we consider the MEMORY process [27] where instead of two choices, we only sample one bin per step but we have access to a cache which can store the location of one bin. Mitzenmacher, Prabhakar and Shah [23] showed that in the lightly loaded case ( m = n ), the MEMORY process achieves a gap of 𝒪 (log log n ). Extending the setting of Mitzenmacher et al. in two ways, we first allow the number of balls m to be arbitrary, which includes the challenging heavily loaded case where m  n. Secondly, we follow the heterogeneous bins model of Wieder [30], where the sampling distribution of bins can be biased up to some arbitrary multiplicative constant. Somewhat surprisingly, we prove that even in this setting, the MEMORY process still achieves an 𝒪(loglog n ) gap bound. This is in stark contrast with the TWO-CHOICE (or any d -CHOICE with d = 𝒪(1)) process, where it is known that the gap diverges as m → ∞ [30]. Further, we show that for any sampling distribution independent of m (but possibly dependent on n ) the MEMORY process has a gap that can be bounded independently of m. Finally, we prove a tight gap bound of 𝒪(log n ) for MEMORY in another relaxed setting with heterogeneous (weighted) balls and a cache which can only be maintained for two steps. * The full version of the paper can be accessed at [20]

Details

SODA Conference 2022 Conference Paper

Balanced Allocations: Caching and Packing, Twinning and Thinning

  • Dimitrios Los
  • Thomas Sauerwald
  • John Sylvester 0001

We consider the sequential allocation of m balls (jobs) into n bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small gap between the maximum load and the average load. In this paper, we present a general framework that allows us to analyze various allocation processes that slightly prefer allocating into underloaded, as opposed to overloaded bins. Our analysis covers several natural instances of processes, including: • The C aching process (a. k. a. memory protocol) as studied by Mitzenmacher, Prabhakar and Shah (2002). • The P acking process: At each round we only take one bin sample. If the load is below some threshold (e. g. , the average load), then we place as many balls until the threshold is reached; otherwise, we place only one ball. • The T winning process: At each round, we only take one bin sample. If the load is below some threshold, then we place two balls; otherwise, we place only one ball. • The T hinning process as recently studied by Feldheim and Gurel-Gurevich (2021). As we demonstrate, using an interplay between several potential functions our general framework implies for all these processes a gap of O (log n ) for any number of balls m ≥ n.

Details

SODA Conference 2019 Conference Paper

On coalescence time in graphs: When is coalescing as fast as meeting? : Extended Abstract

  • Varun Kanade
  • Frederik Mallmann-Trenn
  • Thomas Sauerwald

Coalescing random walks is a fundamental stochastic process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as by Cooper, Elsässer, Ono, Radzik [13] and Cooper, Frieze and Radzik [12], the coalescence time for graphs such as binary trees, d -dimensional tori, hypercubes and more generally, vertex-transitive graphs, remains unresolved. We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log 2 n ), the coalescence time of n random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. For almost-regular graphs, we bound the coalescence time by the hitting time, resolving the discrete-time variant of a conjecture by Aldous for this class of graphs. Finally, we prove that for any graph the coalescence time is bounded by O ( n 3 ) (which is tight for the Barbell graph); surprisingly even such a basic question about the coalescing time was not answered before this work. By duality, our results give bounds on the voter model and therefore give bounds on the consensus time in arbitrary undirected graphs. We also establish a new bound on the hitting time and cover time of regular graphs, improving and tightening previous results by Broder and Karlin [10], as well as those by Aldous and Fill [1].

Details

TCS Journal 2014 Journal Article

Randomised broadcasting: Memory vs. randomness

  • Petra Berenbrink
  • Robert Elsässer
  • Thomas Sauerwald

In this paper we analyse broadcasting in d-regular networks with good expansion properties. For the underlying communication, we consider modifications of the so-called random phone call model. In the standard version of this model, each node is allowed in every step to open a channel to a randomly chosen neighbour, and the channels can be used for bi-directional communication. Then, broadcasting on the graphs mentioned above can be performed in time O ( log n ), where n is the size of the network. However, every broadcast algorithm with runtime O ( log n ) needs on average Ω ( log n / log d ) message transmissions per node for random graphs with expected degree d [11]. In this paper we show that it is possible to save significantly on communications if the standard model is modified such that nodes can avoid opening channels to exactly the same neighbours in two consecutive steps. We consider the so-called Rr model where we assume that every node has a cyclic list of all of its neighbours, ordered in a random way. Then, in step i the node communicates with the i-th neighbour from that list. We provide an O ( log n ) time algorithm which produces in average O ( log n ) transmissions per node in networks with suitably defined expansion properties. Furthermore, we present a related lower bound of Ω ( log n / log log n ) for the average number of message transmissions. These results show that by using memory it is possible to reduce the number of transmissions per node by almost a quadratic factor.

Details DOI

SODA Conference 2012 Conference Paper

Rumor spreading and vertex expansion

  • George Giakkoupis
  • Thomas Sauerwald

We study the relation between the rate at which rumors spread throughout a graph and the vertex expansion of the graph. We consider the standard rumor spreading protocol where every node chooses a random neighbor in each round and the two nodes exchange the rumors they know. For any n -node graph with vertex expansion α, we show that this protocol spreads a rumor from a single node to all other nodes in rounds with high probability. Further, we construct graphs for which Ω(α −1 log 2 n ) rounds are needed. Our results complement a long series of works that relate rumor spreading to edge-based notions of expansion, resolving one of the most natural questions on the connection between rumor spreading and expansion.

Details

FOCS Conference 2012 Conference Paper

Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies

  • Thomas Sauerwald
  • He Sun 0001

We consider the problem of balancing load items (tokens) on networks. Starting with an arbitrary load distribution, we allow in each round nodes to exchange tokens with their neighbors. The goal is to achieve a distribution where all nodes have nearly the same number of tokens. For the continuous case where tokens are arbitrarily divisible, most load balancing schemes correspond to Markov chains whose convergence is fairly well-understood in terms of their spectral gap. However, in many applications load items cannot be divided arbitrarily and we need to deal with the discrete case where the load is composed of indivisible tokens. This discretization entails a non-linear behavior due to its rounding errors, which makes the analysis much harder than in the continuous case. Therefore, it has been a major open problem to understand the limitations of discrete load balancing and its relation to the continuous case. We investigate several randomized protocols for different communication models in the discrete case. Our results demonstrate that there is almost no difference between the discrete and continuous case. For instance, for any regular network in the matching model, all nodes have the same load up to an additive constant in (asymptotically) the same number of rounds required in the continuous case. This generalizes and tightens the previous best result, which only holds for expander graphs.

Details

MFCS Conference 2011 Conference Paper

Faster Coupon Collecting via Replication with Applications in Gossiping

  • Petra Berenbrink
  • Robert Elsässer
  • Tom Friedetzky
  • Lars Nagel 0001
  • Thomas Sauerwald

Abstract We consider an extension of the well-known coupon collecting (CC) problem. In our model we have a player who is allowed to deterministically select one box per time step. The player plays against a random sequence of box choices r 1, r 2, … In each step, the contents of both boxes are merged. The goal of the player is to collect all coupons in one box (the standard model), or to have a copy of each coupon in all boxes. We consider three information models, depending on the knowledge of the random choices that the player has before he has to fix his deterministic choices: (i) full prior knowledge of the whole random sequence; (ii) knowledge of the random sequence up to the previous step (but not the current or any subsequent step); (iii) all decisions must be made in advance without any knowledge of the random sequence. Our main results are lower and asymptotically matching constructive upper bounds for all three models. We also show that network gossiping (similar in spirit to all-in-all CC) is asymptotically no harder than collecting coupons.

Details

TCS Journal 2011 Journal Article

Tight bounds for the cover time of multiple random walks

  • Robert Elsässer
  • Thomas Sauerwald

We study the cover time of multiple random walks on undirected graphs G = ( V, E ). We consider k parallel, independent random walks that start from the same vertex. The speed-up is defined as the ratio of the cover time of a single random walk to the cover time of these k random walks. Recently, Alon et al. (2008) [5] derived several upper bounds on the cover time, which imply a speed-up of Ω ( k ) for several graphs; however, for many of them, k has to be bounded by O ( log n ). They also conjectured that, for any 1 ⩽ k ⩽ n, the speed-up is at most O ( k ) on any graph. We prove the following main results: • We present a new lower bound on the speed-up that depends on the mixing time. It gives a speed-up of Ω ( k ) on many graphs, even if k is as large as n. • We prove that the speed-up is O ( k log n ) on any graph. For a large class of graphs we can also improve this bound to O ( k ), matching the conjecture of Alon et al. • We determine the order of the speed-up for any value of 1 ⩽ k ⩽ n on hypercubes, random graphs and degree restricted expanders. For d -dimensional tori with d > 2, our bounds are tight up to logarithmic factors. • Our findings also reveal a surprisingly sharp threshold behaviour for certain graphs, e. g. , the d -dimensional torus with d > 2 and hypercubes: there is a value T such that the speed-up is approximately min { T, k } for any 1 ⩽ k ⩽ n.

Details DOI

TCS Journal 2010 Journal Article

A self-stabilizing algorithm for cut problems in synchronous networks

  • Thomas Sauerwald
  • Dirk Sudholt

Consider a synchronized distributed system where each node can only observe the state of its neighbors. Such a system is called self-stabilizing if it reaches a stable global state in a finite number of rounds. Allowing two different states for each node induces a cut in the graph. In each round, every node decides whether it is (locally) satisfied with the current cut. Afterwards all unsatisfied nodes change sides independently with a fixed probability p. Using different notions of satisfaction enables the computation of maximal and minimal cuts, respectively. We analyze the expected time until such cuts are reached on several graph classes and study the impact of the parameter p and the initial cut.

Details DOI

SODA Conference 2010 Conference Paper

Efficient Broadcast on Random Geometric Graphs

  • Milan Bradonjic
  • Robert Elsässer
  • Tobias Friedrich 0001
  • Thomas Sauerwald
  • Alexandre Stauffer

A Random Geometric Graph (RGG) in two dimensions is constructed by distributing n nodes independently and uniformly at random in and creating edges between every pair of nodes having Euclidean distance at most r, for some prescribed r. We analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that with probability 1 – ( n −1 ) this algorithm informs every node in the largest connected component of an RGG within rounds. This holds for any value of r larger than the critical value for the emergence of a connected component with Ω( n ) nodes. In order to prove this result, we show that for any two nodes sufficiently distant from each other in, the length of the shortest path between them in the RGG, when such a path exists, is only a constant factor larger than the optimum. This result has independent interest and, in particular, gives that the diameter of the largest connected component of an RGG is, which surprisingly has been an open problem so far.

Details

SODA Conference 2010 Conference Paper

Quasirandom Load Balancing

  • Tobias Friedrich 0001
  • Martin Gairing
  • Thomas Sauerwald

We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a random algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm approximates the idealized process (where the tokens are divisible) on important network topologies surprisingly closely. On d -dimensional torus graphs with n nodes it deviates from the idealized process only by an additive constant. In contrast to that, the randomized rounding approach of Friedrich and Sauerwald [8] can deviate up to Ω(polylog n ) and the deterministic algorithm of Rabani, Sinclair and Wanka [23] has a deviation of Ω( n 1/ d ). This makes our quasirandom algorithm the first known algorithm for this setting which is optimal both in time and achieved smoothness. We further show that also on the hypercube our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.

Details

STOC Conference 2009 Conference Paper

Near-perfect load balancing by randomized rounding

  • Tobias Friedrich 0001
  • Thomas Sauerwald

We consider and analyze a new algorithm for balancing indivisible loads on a distributed network with n processors. The aim is minimizing the discrepancy between the maximum and minimum load. In every time-step paired processors balance their load as evenly as possible. The direction of the excess token is chosen according to a randomized rounding of the participating loads.

Details

MFCS Conference 2004 Conference Paper

Agent-Based Information Handling in Large Networks

  • Robert Elsässer
  • Ulf Lorenz
  • Thomas Sauerwald

Abstract Mobile agents are software abstractions that can migrate across the links of a network. They naturally extend the object oriented program style and nicely correspond to agents as examined in game theory. In this paper, we introduce a simple, robust, and efficient randomized broadcast protocol within this mobile agent programming paradigm. We show that by using this scheme, broadcasting requires in a random graph of certain density O (ln n ) steps, where n denotes the number of nodes in the graph. Then, we consider bounded degree graphs and prove that we are able to distribute an information among all nodes in O ( D ) steps, where D denotes the diameter of the graph. We also show that, in contrast to traditional randomized broadcasting, graphs exist in which spreading an information requires Ω ( n 2 ) steps. On the other hand, some graphs which require Ω ( n ln n ) steps to spread the information in the traditional broadcast model, allow very fast agent based broadcasting. It should be noted that the previously mentioned results are guaranteed with probability 1– o (1/ n ).

Details
v2026.09.13