Volker Stemann

STOC Conference 1997 Conference Paper

Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers

• Joe Buhler
• Mohammad Amin Shokrollahi
• Volker Stemann

STOC Conference 1997 Conference Paper

Practical Loss-Resilient Codes

• Michael Luby
• Michael Mitzenmacher
• Mohammad Amin Shokrollahi
• Daniel A. Spielman
• Volker Stemann

FOCS Conference 1997 Conference Paper

Randomized Allocation Processes

• Artur Czumaj
• Volker Stemann

We investigate various randomized processes allocating balls into bins that arise in applications in dynamic resource allocation and on-line load balancing. We consider the scenario when m balls arriving sequentially are to be allocated into n bins on-line and without using a global controller. Traditionally, the main aim of allocation processes is to place the balls into bins to minimize the maximum load in bins. However in many applications it is equally important to minimize the number of trails performed by the balls (the allocation time). We study adaptive allocation schemes that achieve optimal tradeoffs between the maximum load, the maximum allocation time, and the average allocation time. We investigate allocation processes that may reallocate the balls. We provide a tight analysis of the maximum load of processes that during placing a new ball may reassign the balls in up to d randomly chosen bins. We study infinite processes, in which in each step a random ball is removed and a new ball is placed according to some scheduling rule. We present a novel approach that establishes a tight estimation of the time needed for the infinite process to be in the state near to its equilibrium. Finally, we provide a tight analysis of the maximum load of the off-line process in which each ball may be placed into one of d randomly chosen bins. We apply this result to competitive analysis of on-line load balancing processes.

I&C Journal 1997 Journal Article

Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures

• Artur Czumaj
• Friedhelm Meyer auf der Heide
• Volker Stemann

We consider randomized simulations of shared memory on a distributed memory machine (DMM) where thenprocessors and thenmemory modules of the DMM are connected via a reconfigurable architecture. We first present a randomized simulation of a CRCW PRAM on a reconfigurable DMM having a complete reconfigurable interconnection. It guarantees delay O (log*n), with high probability. Next we study a reconfigurable mesh DMM (RM-DMM). Here thenprocessors andnmodules are connected via ann×nreconfigurable mesh. It was already known that ann×mreconfigurable mesh can simulate in constant time ann-processor CRCW PRAM with shared memory of sizem. In this paper we present a randomized step by step simulation of a CRCW PRAM with arbitrarily large shared memory on an RM-DMM. It guarantees constant delay with high probability, i. e. , it simulates in real time. Finally we prove a lower bound showing that sizeΩ(n 2) for the reconfigurable mesh is necessary for real time simulations.

TCS Journal 1996 Journal Article

Exploiting storage redundancy to speed up randomized shared memory simulations

• Friedhelm Meyer auf der Heide
• Christian Scheideler
• Volker Stemann

Assume that a set U of memory locations is distributed among n memory modules, using some number a of hash functions h 1, …, h a, randomly and independently drawn from a high-performance universal class of hash functions. Thus, each memory location has a copies. Consider the task of accessing b out of the a copies for each of given keys x 1, …, x n ∈ U, b < a. The paper presents and analyses a simple process executing the above task on distributed memory machines (DMMs) with n processors. Efficient implementations are presented, implying - a simulation of an n-processor PRAM on an n-processor optical crossbar DMM with delay O(log log n), - a simulation as above on an arbitrary-DMM with delay O( log log n log log log n ), - an implementation of a static dictionary on an arbitrary-DMM with parallel access time O( log∗ n + log log n log a ), if a hash functions are used. In particular, an access time of O(log∗ n) can be reached if (log n) 1 log∗ n hash functions are used. We further prove a lower bound for executing the above process by any so-called simple access protocol, showing that our implementations are optimal.