Abstract Consider a set of jobs connected to a directed acyclic task graph with a fixed source and sink. The edges of this graph model precedence constraints and the jobs have to be scheduled with respect to those. We introduce the server cloud scheduling problem, in which the jobs have to be processed either on a single local machine or on one of infinitely many cloud machines. For each job, processing times both on the server and in the cloud are given. Furthermore, for each edge in the task graph, a communication delay is included in the input and has to be taken into account if one of the two jobs is scheduled on the server and the other in the cloud. The server processes jobs sequentially, whereas the cloud can serve as many as needed in parallel, but induces costs. We consider both makespan and cost minimization. The main results are an FPTAS for the makespan objective for graphs with a constant source and sink dividing cut and strong hardness for the case with unit processing times and delays.

We consider a swarm of $n$ robots in \mathbb{R}^d. The robots are oblivious, disoriented (no common coordinate system/compass), and have limited visibility (observe other robots up to a constant distance). The basic formation task gathering requires that all robots reach the same, not predefined position. In the related near-gathering task, they must reach distinct positions such that every robot sees the entire swarm. In the considered setting, gathering can be solved in $\mathcal{O}(n + Δ^2)$ synchronous rounds both in two and three dimensions, where $Δ$ denotes the initial maximal distance of two robots. In this work, we formalize a key property of efficient gathering protocols and use it to define $λ$-contracting protocols. Any such protocol gathers $n$ robots in the $d$-dimensional space in $\mathcal{O}(Δ^2)$ synchronous rounds. Moreover, we prove a corresponding lower bound stating that any protocol in which robots move to target points inside of the local convex hulls of their neighborhoods -- $λ$-contracting protocols have this property -- requires $Ω(Δ^2)$ rounds to gather all robots. Among others, we prove that the $d$-dimensional generalization of the GtC-protocol is $λ$-contracting. Remarkably, our improved and generalized runtime bound is independent of $n$ and $d$. The independence of $d$ answers an open research question. We also introduce an approach to make any $λ$-contracting protocol collisionfree to solve near-gathering. The resulting protocols maintain the runtime of $Θ(Δ^2)$ and work even in the semi-synchronous model.

The famous k-Server Problem covers plenty of resource allocation scenarios, and several variations have been studied extensively for decades. However, to the best of our knowledge, no research has considered the problem if the servers are not identical and requests can express which specific servers should serve them. Therefore, we present a new model generalizing the k-Server Problem by preferences of the requests and proceed to study it in a uniform metric space for deterministic online algorithms (the special case of paging).

We consider a natural extension to the metric uncapacitated Facility Location Problem (FLP) in which requests ask for different commodities out of a finite set (S) of commodities. Ravi and Sinha (SODA 2004) introduced the model as the Multi-Commodity Facility Location Problem (MFLP) and considered it an offline optimization problem. The model itself is similar to the FLP: i.e., requests are located at points of a finite metric space and the task of an algorithm is to construct facilities and assign requests to facilities while minimizing the construction cost and the sum over all assignment distances. In addition, requests and facilities are heterogeneous; they request or offer multiple commodities out of S. A request has to be connected to a set of facilities jointly offering the commodities demanded by it. In comparison to the FLP, an algorithm has to decide not only if and where to place facilities, but also which commodities to offer at each. To the best of our knowledge we are the first to study the problem in its online variant in which requests, their positions and their commodities are not known beforehand but revealed over time. We present results regarding the competitive ratio. On the one hand, we show that heterogeneity influences the competitive ratio by developing a lower bound on the competitive ratio for any randomized online algorithm of (Ω( √|S| + log/n log log n)) that already holds for simple line metrics. Here, (n) is the number of requests. On the other side, we establish a deterministic (O(√|S| · log n))-competitive algorithm and a randomized (O(√|S| · log/n log log n))-competitive algorithm. Further, we show that when considering a more special class of cost functions for the construction cost of a facility, the competitive ratio decreases given by our deterministic algorithm depending on the function.

Robot coordination problems deal with systems consisting of many autonomous, but simple, mobile agents that try to achieve a common, complex task. The agents' capabilities depend on the exact model and task but are typically very restricted. For example, there is usually no common coordinate system or sense of direction, and agents often have limited sensing capabilities. Among the most basic and well-studied type of tasks are GATHERING problems, in which initially scattered agents must gather at a single point. CHAINFORMATION problems represent another important formation primitive. Here, agents take the role of communication relays that, initially, form a winding chain connecting two base stations. The relays are to move such that the chain becomes straight, allowing for a more energy-efficient communication along the relay chain. Both GATHERING and CHAINFORMATION problems can be described as contracting: starting from an initially scattered formation, they seek to reach a smaller, more efficient structure. A natural complement are extension problems, where agents start in an initially dense formation and seek to reach an extended formation that covers as much area as possible. While there are some results about extension problems if agents move on grids or rings, results in standard discrete and continuous models for the Euclidean plane are scarce. Our work introduces the MAXFORM problem on the Euclidean plane and provides first analytical results for both the discrete and continuous case.

Abstract We extend the Mobile Server problem introduced in Feldkord and Meyer auf der Heide (TOPC 6(3), 14:1–14:17 2019) to a model where k identical mobile resources, here named servers, answer requests appearing at points in the Euclidean space. To reduce communication costs, the positions of the servers can be adapted by a limited distance ms per round for each server. The costs are measured similarly to the classical Page Migration problem: i.e., answering a request induces costs proportional to the distance to the nearest server, and moving a server induces costs proportional to the distance multiplied with a weight D. We show that, in our model, no online algorithm can have a constant competitive ratio: i.e., one which is independent of the input length n, even if an augmented moving distance of (1 + δ)ms is allowed for the online algorithm. Therefore we investigate a restriction of the power of the adversary dictating the sequence of requests: We demand locality of requests: i.e., that consecutive requests come from points in the Euclidean space with distance bounded by some constant mc. We show constant lower bounds on the competitiveness in this setting (independent of n, but dependent on k, ms and mc). On the positive side, we present a deterministic online algorithm with bounded competitiveness when an augmented moving distance and locality of requests is assumed. Our algorithm simulates any given algorithm for the classical k-Page Migration problem as guidance for its servers and extends it by a greedy move of one server in every round. The resulting competitive ratio is polynomial in the number of servers k, the ratio between mc and ms, the inverse of the augmentation factor 1/δ and the competitive ratio of the simulated k-Page Migration algorithm. We also show how to directly adapt the Double Coverage algorithm (Chrobak et al. SIAM J. Discrete Math. 4(2), 172–181 11) for the k-Server problem to receive an algorithm with improved competitiveness on the line.

Abstract In this paper, we present the first algorithm for progressive sampling of 3D surfaces with blue noise characteristics that runs entirely on the GPU. The performance of our algorithm is comparable to state‐of‐the‐art GPU Poisson‐disk sampling methods, while additionally producing ordered sequences of samples where every prefix exhibits good blue noise properties. The basic idea is, to reduce the 3D sampling domain to a set of 2.5D images which we sample in parallel utilizing the rasterization hardware of current GPUs. This allows for simple visibility‐aware sampling that only captures the surface as seen from outside the sampled object, which is especially useful for point‐based level‐of‐detail rendering methods. However, our method can be easily extended for sampling the entire surface without changing the basic algorithm. We provide a statistical analysis of our algorithm and show that it produces good blue noise characteristics for every prefix of the resulting sample sequence and analyze the performance of our method compared to related state‐of‐the‐art sampling methods.

We examine the Online Facility Location Problem in an augmented version, where the online algorithm is allowed to adapt the position of the facilities for costs proportional to the distance by which the position is changed. In this setting, it is possible to construct online algorithms which deal with the lower bound instances of Online Facility Location much more effectively. Fotakis showed a lower bound of $Ømega(\fracłog n łog łog n )$ for the original Online Facility Location Problem, where n denotes the number clients. This bounds holds even on the real line and for randomized algorithms against oblivious adversaries. In contrast, we are able to achieve competitive ratios independent of n in our model. We propose randomized online algorithms in two settings: We consider the Euclidean space (of arbitrary dimension) and allow the facilities to either move arbitrarily or to move at most a constant distance m in each time step. The costs for moving a facility from a to b is $D\cdot d(a,b)$ where $D\geq 1$ is a constant. Our algorithms are memoryless w.r.t. past requests and only make local modifications to at most one facility in each time step. In the case of arbitrary movement, the competitive ratio only depends on D . In the case of limiting the movement to a constant distance m , the competitive ratio additionally depends on the opening cost $c_f$ of facilities and m . We show that our results are asymptotically tight on the real line. For the Euclidean space of higher dimensions, the competitive ratio of our algorithms is tight with respect to D , $c_f$ and m , but is additionally impacted by the number of optimal facilities.

We consider a scenario where agents have to exchange data in a wireless ad-hoc network, although it is not connected. We assume that each agent has a static home base. To improve connectivity, each agent is allowed to move away from his home base, but only for a limited distance which may be different for different agents. These distances might be dictated by limited batteries of the agents, which forces them to return to their home charging station after a while. An application currently widely considered in literature (and in projects and applications) is disaster management, where helpers are equipped with smartphones to submit important local information to a coordinating station. In case of the network being disconnected, mobile "postmen'' are used for long distance connections. In this paper, we focus on the aspect of "communication by postmen''. We model such a scenario by a weighted directed graph. It consists of n (static) nodes describing the home bases of the agents. A directed edge from base $v_i$ to base $v_j$ with weight $w(v_i,v_j)$ indicates that agent $a_i$ can walk from his home base to the home base of $a_j$, which needs time $w(v_i,v_j)$. If agent $a_j$ is at home when agent $a_i$ arrives, they can exchange messages. % Alongside with the introduction of the model, we present a randomized distributed algorithm for all-to-all message dissemination and show that its performance is, in many cases, close to optimal.

We introduce the mobile server problem, inspired by current trends to move computational tasks from cloud structures to multiple devices close to the end user. An example for this are embedded systems in autonomous cars that communicate in order to coordinate their actions. Our model is a variant of the classical Page Migration Problem. More formally, we consider a mobile server holding a data page. The server can move in the Euclidean space (of arbitrary dimension). In every round, requests for data items from the page pop up at arbitrary points in the space. The requests are served, each at a cost of the distance from the requesting point and the server, and the mobile server may move, at a cost D times the distance traveled for some constant D. We assume a maximum distance m the server is allowed to move per round.

We consider the following variant of the two-dimensional gathering problem for swarms of robots:Given a swarm of n indistinguishable, point-shaped robots on a two-dimensional grid. Initially, the robots form a closed chain on the grid and must keep this connectivity during the whole process of their gathering. Connectivity means, that neighboring robots of the chain need to be positioned at the same or neighboring points of the grid. In our model, gathering means to keep shortening the chain until the robots are located inside a 2x2 subgrid. Our model is completely local (no global control, no global coordinates, no compass, no global communication or vision, ). Each robot can only see its next constant number of left and right neighbors on the chain. This fixed constant is called the viewing path length. All its operations and detections are restricted to this constant number of robots. Other robots, even if located at neighboring or the same grid point, cannot be detected. Only based on the relative positions of its detectable chain neighbors, can a robot decide to obtain a certain state. Based on this state and their local knowledge, the robots do local modifications to the chain by moving to neighboring grid points without breaking the chain. These modifications are performed without the knowledge whether they lead to a global progress or not. We assume the fully synchronous FSYNC model. For this problem, we present a gathering algorithm which needs linear time. This result generalizes the result from [1], where an open chain with specified distinguishable (and fixed) endpoints is considered.

Consider the continuous distributed monitoring model in which n distributed nodes, receiving individual data streams, are connected to a designated server. The server is asked to continuously monitor a function defined over the values observed across all streams while minimizing the communication. We study a variant in which the server is equipped with a broadcast channel and is supposed to keep track of an approximation of the set of nodes currently observing the k largest values. Such an approximate set is exact except for some imprecision in an ε-neighborhood of the k-th largest value. This approximation of the Top-k-Position Monitoring Problem is of interest in cases where marginal changes (e.g. due to noise) in observed values can be ignored so that monitoring an approximation is sufficient and can reduce communication. This paper extends our results from [6], where we have developed a filter-based online algorithm for the (exact) Top-k-Position Monitoring Problem. There we have presented a competitive analysis of our algorithm against an offline adversary that also is restricted to filter-based algorithms. Our new algorithms as well as their analyses use new methods. We analyze their competitiveness against adversaries that use both exact and approximate filter-based algorithms, and observe severe differences between the respective powers of these adversaries.

In this paper, we solve the local gathering problem of a swarm of n indistinguishable, point-shaped robots on a two-dimensional grid in asymptotically optimal time O(n) in the fully synchronous FSYNC time model. Given an arbitrarily distributed (yet connected) swarm of robots, the gathering problem on the grid is to locate all robots within a 2 x 2-sized area that is not known beforehand. Two robots are connected if they are vertical or horizontal neighbors on the grid. The locality constraint means that no global control, no compass, no global communication and only local vision is available; hence, a robot can see its grid neighbors only up to a constant L1-distance, which also limits its movements. A robot can move to one of its eight neighboring grid cells and if two or more robots move to the same location they are merged to be only one robot. The locality constraint is the significant challenging issue here, since robot movements must not harm the (only globally checkable) swarm connectivity. For solving the gathering problem, we provide a synchronous algorithm -- executed by every robot -- which ensures that robots merge without breaking the swarm connectivity. In our model, robots can obtain a special state, which marks such a robot to be performing specific connectivity preserving movements in order to allow later merge operations of the swarm. Compared to the grid, for gathering in the Euclidean plane for the same robot and time model the best known upper bound is O(n2).

Consider n nodes connected to a single coordinator. Each node receives an individual online data stream of numbers and, at any point in time, the coordinator has to know the k nodes currently observing the largest values, for a given k between 1 and n. We design and analyze an algorithm that solves this problem while bounding the amount of messages exchanged between the nodes and the coordinator. Our algorithm employs the idea of using filters which, intuitively speaking, leads to few messages to be sent, if the new input is “similar” to the previous ones. The algorithm uses a number of messages that is on expectation by a factor of O ((log Δ + k) · log n) larger than that of an offline algorithm that sets filters in an optimal way, where Δ is upper bounded by the largest value observed by any node.

Many markets have seen a shift from the idea of buying and moved to leasing instead. Arguably, the latter has been the major catalyst for their success. Ten years ago, research realized this shift and initiated the study of 'online leasing problems' by introducing leasing to online optimization problems. Resources required to provide a service in an 'online leasing problem' are no more bought but leased for different durations. In this paper, we provide an overview of results that contribute to the understanding of 'online resource leasing problems'.

We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement rj∈[0,1]. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature.

In this paper we introduce “On-The-Fly Computing”, our vision of future IT services that will be provided by assembling modular software components available on world-wide markets. After suitable components have been found, they are automatically integrated, configured and brought to execution in an On-The-Fly Compute Center. We envision that these future compute centers will continue to leverage three current trends in large scale computing which are an increasing amount of parallel processing, a trend to use heterogeneous computing resources, and — in the light of rising energy cost — energy-efficiency as a primary goal in the design and operation of computing systems. In this paper, we point out three research challenges and our current work in these areas.

Abstract Many 3D scenes (e.g. generated from CAD data) are composed of a multitude of objects that are nested in each other. A showroom, for instance, may contain multiple cars and every car has a gearbox with many gearwheels located inside. Because the objects occlude each other, only few are visible from outside. We present a new technique, Spherical Visibility Sampling (SVS), for real‐time 3D rendering of such – possibly highly complex – scenes. SVS exploits the occlusion and annotates hierarchically structured objects with directional visibility information in a preprocessing step. For different directions, the directional visibility encodes which objects of a scene's region are visible from the outside of the regions' enclosing bounding sphere. Since there is no need to store a separate view space subdivision as in most techniques based on preprocessed visibility, a small memory footprint is achieved. Using the directional visibility information for an interactive walkthrough, the potentially visible objects can be retrieved very efficiently without the need for further visibility tests. Our evaluation shows that using SVS allows to preprocess complex 3D scenes fast and to visualize them in real time (e.g. a Power Plant model and five animated Boeing 777 models with billions of triangles). Because SVS does not require hardware support for occlusion culling during rendering, it is even applicable for rendering large scenes on mobile devices.

We consider a scenario in which n mobile robots with a limited viewing range are distributed arbitrarily in the plane, such that the visibility graph of the robots is connected. The goal is to gather the robots in one (not predefined) point. Each robot may base its decision where to move only on the current relative positions of the robots which are in its viewing range. That is, besides having a limited viewing range, the robots are oblivious (they do not use information from the past), they do not have IDs, and they do not have a common sense of direction. On the other hand side, we assume that they are points, i.e., have no extent.

A left-to-right maximum in a sequence of n numbers s 1 , …, s n is a number that is strictly larger than all preceding numbers. In this article we present a smoothed analysis of the number of left-to-right maxima in the presence of additive random noise. We show that for every sequence of n numbers s i ∈ [0,1] that are perturbed by uniform noise from the interval [-ϵ,ϵ], the expected number of left-to-right maxima is Θ(√ n /ϵ + log n ) for ϵ>1/ n . For Gaussian noise with standard deviation σ we obtain a bound of O ((log 3/2 n )/σ + log n ). We apply our results to the analysis of the smoothed height of binary search trees and the smoothed number of comparisons in the quicksort algorithm and prove bounds of Θ(√ n /ϵ + log n ) and Θ( n /ϵ+1√ n /ϵ + n log n ), respectively, for uniform random noise from the interval [-ϵ,ϵ]. Our results can also be applied to bound the smoothed number of points on a convex hull of points in the two-dimensional plane and to smoothed motion complexity, a concept we describe in this article. We bound how often one needs to update a data structure storing the smallest axis-aligned box enclosing a set of points moving in d -dimensional space.

The problem of gathering n autonomous robots in the Euclidean plane at one (not predefined) point is well-studied under various restrictions on the capabilities of the robots and in several time models. However, only very few runtime bounds are known. We consider the scenario of local algorithms in which the robots can only observe their environment within a fixed viewing range and have to base their decision where to move in the next step solely on the relative positions of the robots within their viewing range. Such local algorithms have to guarantee that the (initially connected) unit disk graph defined by the viewing range of the robots stays connected at all times. In this paper, we focus on the synchronous setting in which all robots are activated concurrently. Ando et al.

Consider two far apart base stations connected by an arbitrarily winding chain of n relay robots to transfer messages between them. Each relay acts autonomously, has a limited communication range, and knows only a small, local part of its environment.

The gathering problem, where n autonomous robots with restricted capabilities are required to meet in a single point of the plane, is widely studied. We consider the case that robots are limited to see only robots within a bounded vicinity and present an algorithm achieving gathering in O(n2) rounds in expectation. A round consists of a movement of all robots, in random order. All previous algorithms with a proven time bound assume global view on the configuration of all robots.

This paper extends the online file allocation problem of Bartal et al. to the following scenario: An indivisible file consisting of multiple units is stored on a network of stationary servers which are connected to a mobile ad hoc network. We model the mobile ad hoc network as a dynamic unit disk graph. The mobile nodes access single units (read/write) of the file using multihop paths to a close-by server, if they do not posses a copy of the file. In order to minimize the amount of data to be transferred, the data management system may create/delete copies of the complete file on arbitrary mobile nodes. Our cost model addresses the overall power consumption of the nodes of the mobile ad hoc network needed for the data management. It consists of a time dependent stand-by power consumption of the mobile nodes and the power consumption used by the hops during data transfers between the servers and the mobile nodes. We introduce the notion of an "energy-distance" which is the energy consumed by a data transfer of an unit-sized message between a server and a mobile node.

We envision a scenario with robots moving on a terrain represented by a plane. A mobile robot, called explorer is connected by a communication chain to a stationary base camp. The chain is expected to pass communication messages between the explorer and the base camp. It is composed of simple, mobile robots, called relays. We are investigating strategies for organizing and maintaining the chain, so that the number of relays employed is minimized and nevertheless the distance between neighbored relays in the chain remains bounded. We are looking for local and distributed strategies employed by restricted relays that have to base their decision (“Where should I go?”) solely on the relative positions of its neighbors in the chain. We present the Manhattan–Hopper and the Hopper strategy which improve the performance of all known solutions to this problem significantly. They are the first such strategies that are optimal in this setting, i.e., that allow the explorer to move with constant speed, independent of the length of the chain, and keep this length minimum up to a constant factor.

We present a randomized block-level storage virtualization for arbitrary heterogeneous storage systems that can distribute data in a fair and redundant way and can adapt this distribution in an efficient way as storage devices enter or leave the system. More precisely, our virtualization strategies can distribute a set of data blocks among a set of storage devices of arbitrary non-uniform capacities so that a storage device representing x% of the capacity in the system will get x% of the data (as long as this is in principle possible) and the different copies of each data block are stored so that no two copies of a data block are located in the same device. Achieving these two properties is not easy, and no virtualization strategy has been presented so far that has been formally shown to satisfy fairness and redundancy while being time- and space-eflcient and allowing an efjTcient adaptation to a changing set of devices.

We discuss strategies for maintaining connectivity in a system consisting of a stationary base station and a mobile explorer. For this purpose we introduce the concept of mobile relay stations, which form a chain between the base station and the explorer and forward all communication.

Page migration is one of the fundamental subproblems in the framework of data management in networks. It occurs in a distributed network of processors sharing one indivisible memory page of size D, which is stored in one of the processors. During runtime, processors access unit size data items from the page, and the system is allowed to move the page from one processor to another in order to minimize the total communication cost.This problem was considered in the online setting numerous times by many researchers, and some online algorithms were proven to achieve a cost within a constant factor of the optimal offline solution. However, all results were achieved under the assumption that the communication costs between processors were fixed during the execution of the whole process.In this paper we consider a model in which the communication costs can change in each time step, but the pace of the changes is restricted. This is typical in mobile networks, and also models the dynamics of networks that are not exclusively dedicated to the page migration.If both changes of the network and the request sequence are given by some adversarial entity, we prove a tight bound on the competitive ratio of the problem. However, the size of this ratio motivates us to assume that the changes of communication costs are modeled by some stochastic process, and an adversary dictates only which processor issues a request. To analyze such a hybrid case, we introduce the notion of expected competitive ratio and prove that, for the case where constant number of processors perform a random walk on a torus or on a mesh of diameter √D, it is O(log2D).

Using idle times of the processors is a well-known approach to run coarse grained parallel algorithms for extremely complex problems. We present on-line algorithms for scheduling the processes of a parallel application that is known off-line on a dynamic network in which the idle times of the processors are dictated by an adversary. We also take communication and synchronization costs into account.Our first contribution consists of a formal model to restrict the adversary in a reasonable way. We then show a constant factor approximation for the off-line scheduling problem. As this problem has to take communication cost into account, it can be seen as a generalization of many NP-hard parallel machine scheduling problems. Finally, we present on-line algorithms for different models with constant or with "nearly constant" competitive ratio.

The GigaNetIC project aims to develop high-speed components for networking applications based on massively parallel architectures. A central part of this project is the design, evaluation, and realization of a parameterizable network processing unit. In this paper we present a design methodology for network processors which encompasses the research areas from the application software down to the gate level of the chip. Key components of this holistic approach have been successfully applied to characteristic examples of architecture refinements.

We investigate the problem of path selection in radio networks for a given set of sites in two-dimensional space. For some given static point-to-point communication demand we define measures for congestion, energy consumption and dilation that take interferences between communication links into account.We show that energy optimal path selection for radio networks can be computed in polynomial time. Then, we introduce the diversity $g(V)$ of a set $V\subseteq \REAL^2$. It can be used to upperbound the number of interfering edges. For real-world applications it can be regarded as $\Theta(\log n)$. A main result of the paper is that a weak $c$-spanner construction as a communication network allows to approximate the congestion-optimal communication network by a factor of $O(g(V)^2)$.Furthermore, we show that there are vertex sets where only one of the performance parameters congestion, energy, and dilation can be optimized at a time. We show trade-offs lower bounding congestion $\times$ dilation and dilation $\times$ energy. For congestion and energy the situation is even worse. It is only possible to find a reasonable approximation for either congestion or energy minimization, while the other parameter is at least a polynomial factor worse than in the optimal network.

We present a new data structure for rendering highly complex virtual environments of arbitrary topology. The special feature of our approach is that it allows an interactive navigation in very large scenes (30 GB/400 million polygons in our benchmark scenes) that cannot be stored in main memory, but only on a local or remote hard disk. Furthermore, it allows interactive rendering of substantially more complex scenes by instantiating objects.For the computation of an approximate image of the scene, a sampling technique is used. In the preprocessing, a so-called sample tree is built whose nodes contain randomly selected polygons from the scene. This tree only uses space that is linear in the number of polygons. In order to produce an image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walkthrough, parts of the sample tree are loaded from local or remote hard disk.We implemented our algorithm in a prototypical walkthrough system. Analysis and experiments show that the quality of our images is comparable to images computed by the conventional z-buffer algorithm regardless of the scene topology.

We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of an arbitrary three-dimensional scene consisting of triangular primitives by reconstruction from a dynamically chosen set of random surface sample points. This approach is independent of mesh connectivity and topology. The resulting rendering time grows only logarithmically with the numbers of triangles in the scene. We were able to render walkthroughs of scenes of up to 1014 triangles at interactive frame rates. Automatic identification of low detail scene components ensures that the rendering speed of the randomized z-buffer cannot drop below that of conventional z-buffer rendering. Experimental and analytical evidence is given that the image quality is comparable to that of common approaches like z-buffer rendering. The precomputed data structures employed by the randomized z-buffer allow for interactive dynamic updates of the scene. Their memory requirements grow only linearly with the number of triangles and allow for a scene graph based instantiation scheme to further reduce memory consumption.

A hierarchical bus network T = (V, E) uses hierarchically, tree-like connected buses as a communication network. New communication technologies like SCI (Scalable Coherent Interface) (see, e.g., [6, 7]) make such networks very attractive, because they allow their easy construction and guarantee reasonable communication performance. Such networks can be modeled as tree networks: leaves correspond to processors, inner nodes to buses, edges to switches, and bandwidths of inner nodes and edges are related to bandwidths of buses and switches, respectively.

In this paper we study the problem of simulating shared memory on the distributed memory machine (DMM). Our approach uses multiple copies of shared memory cells, distributed among the memory modules of the DMM via universal hashing. The main aim is to design strategies that resolve contention at the memory modules. Extending results and methods from random graphs and very fast randomized algorithms, we present new simulation techniques that enable us to improve the previously best results exponentially. In particular, we show that an n-processor CRCW PRAM can be simulated by an n-processor DMM with delay $\O(\log\log\log n \log^*n)$, with high probability. Next we describe a general technique that can be used to turn these simulations into time-processor optimal ones, in the case of EREW PRAMs to be simulated. We obtain a time-processor optimal simulation of an (n log log log n log * n )-processor EREW PRAM on an n-processor DMM with delay $\O(\log\log\log n \log^*n)$, with high probability. When an (n log log log n log * n )-processor CRCW PRAM is simulated, the delay is only by a log * n factor larger. We further demonstrate that the simulations presented can not be significantly improved using our techniques. We show an $\Omega(\log\log\log n / \log\log\log\log n)$ lower bound on the expected delay for a class of PRAM simulations, called topological simulations, that covers all previously known simulations as well as the simulations presented in the paper.

This paper deals with data management for parallel and distributed systems. We present the DIVA (Distributed Variables ) library that provides direct access to shared data objects from each node in a network. The current implementations are based on mesh-connected massively parallel computers. Our algorithms dynamically create and discard copies of the data objects in order to reduce the communication overhead. We use a non-standard approach based on a randomized but locality preserving embedding of ``access trees'' into the network.

In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for the messages with small congestion, dilation, and setup time. Our algorithms are based on the idea of having each message choose a route from two possibilities, a technique that has previously proven successful in simpler load balancing settings. As an application of our techniques, we propose a novel design for a data server.

This paper deals with data management in computer systems in which the computing nodes are connected by a relatively sparse network. We consider the problem of placing and accessing a set of shared objects that are read and written from the nodes in the network. These objects are, e.g., global variables in a parallel program, pages or cache lines in a virtual shared memory system, shared files in a distributed file system, or pages in the World Wide Web. A data management strategy consists of a placement strategy that maps the objects (possibly dynamically and with redundancy) to the nodes, and an access strategy that describes how reads and writes are handled by the system (including the routing). We investigate static and dynamic data management strategies.

It is well known that after placing m n balls independently and uniformly at random (i.u.r.) into n bins, the fullest bin contains \\Theta(log n= log log n+ m n ) balls, with high probability. It is also known (see [Ste96]) that a maximum load of O \\Gamma m n \\Delta can be obtained for all m n if a ball is allocated in one (suitably chosen) of two (i.u.r.) bins. Stemann ([Ste96]) shows that r communication rounds suffice to guarantee a maximum load of maxf r p log n; O \\Gamma m n \\Delta g, with high probability. Adler et al. have shown in [ACMR95] that Stemanns protocol is optimal for constant r. In this paper we extend the above results in two directions: We generalize the lower bound to arbitrary r log log n. This implies that the result of Stemanns protocol is optimal for all r. Our main result is a generalization of Stemanns upper bound to weighted jobs: Let W A (W M ) denote the average (maximum) weight of the balls. Further let \\Delta = W A =W M . Note that...

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of size n, the routing number of H is defined as the maximum over all permutations /spl pi/ on [n] of the minimal number of steps to route /spl pi/ offline in H. We can show that for any network H of size n with routing number R our protocol needs O(log/sub R/ n/spl middot/R) time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular our result yields optimal deterministic routing protocols for arbitrary networks with diameter /spl Omega/(n/sup /spl epsiv//) or bisection width O(n/sup 1-/spl epsiv//), /spl epsiv/>0 constant. Furthermore we can extend our result to deterministic compact routing. This yields, e.g., a deterministic routing protocol with runtime O((log n)/(log log n) R) for arbitrary bounded degree networks if only O(log n) bits are available at each node for storing routing information. Our proofs use a new protocol for routing arbitrary r/spl middot/s-relations in r-replicated s-ary Multibutterflies in optimal time O(log, n).

In this paper we present routing algorithms that are tmiversal in the sense that they route messages along arbitrary (simple) paths in arbitrary networks.The algorithms are analyzed in terms of the number of messages being routed, the maximum number of messages that must cross any edge in the network (edge congestion), the maximum number of edges that a message must cross (dilation), the bufler size, and the bandwidth of the links.We present two main results, both of which have applications to ttnivexsal storeand-forwwd routing and universal wormhole routing.Our results yield significant performance improvements over all previously known universal routing algorithms for a wide range of parameters, and they even improve many time bounds for standard networks.In addition, we present adaptations of our main results for routing along shortest paths in arbitrary networks, and for routing in leveled networks, node-symmetric networks, edge-symmetric networks, expanders, butterflies, and meshes.

Article Free Access Share on A lower bound for randomized algebraic decision trees Authors: Dima Grigoriev Dept. of Computer Science and Mathematics, Penn State University, University Park Dept. of Computer Science and Mathematics, Penn State University, University ParkView Profile , Marek Karpinski Dept. of Computer Science, University of Bonn, 53117, Bonn Dept. of Computer Science, University of Bonn, 53117, BonnView Profile , Friedhelm Meyer auf der Heide Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098 Paderborn Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098 PaderbornView Profile , Roman Smolensky Dept. of Computer Science, University of Bonn, 53117, Bonn Dept. of Computer Science, University of Bonn, 53117, BonnView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 612–619https://doi.org/10.1145/237814.238011Published:01 July 1996Publication History 12citation385DownloadsMetricsTotal Citations12Total Downloads385Last 12 Months13Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We define a new simple and general model for hashing. The basic model together with several variants capture many natural (sequential and parallel) hashing algorithms and represent common hashing practice. Our main results exhibit tight tradeoffs between hash-table size and the number of applications of a hash function on a single key.

In this paper we prove an upper bound for the tradeoff between routing time and space needed to store routing information in the processors and the packets.It holds for all vertex-symmetric networks.In particular, we prove that for any vertex-symmetric network with n vertices, degree d, and diameter D it holds for all s ~[2, n]: h .n packets, h per processor, can be routed to random destinations in time ~(hlog, n .(D + (~+ ~)kn)) , dilation, ignoring congestion and the design of routing protocols.

Article Optimal trade-offs between size and slowdown for universal parallel networks Share on Authors: Friedhelm Meyer auf der Heide Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, Germany Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, GermanyView Profile , Martin Storch Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, Germany Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, GermanyView Profile , Rolf Wanka Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, Germany Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, GermanyView Profile Authors Info & Claims SPAA '95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architecturesJuly 1995 Pages 119–128https://doi.org/10.1145/215399.215430Online:20 July 1995Publication History 1citation174DownloadsMetricsTotal Citations1Total Downloads174Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Simple, efficient shared memory simulations Authors: Martin Dietzfelbinger View Profile , Friedhelm Meyer auf der Heide View Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 110–119https://doi.org/10.1145/165231.165246Published:01 August 1993Publication History 46citation248DownloadsMetricsTotal Citations46Total Downloads248Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a randomized simulation of a nlog log (n) log (n)-processor shared memory machine (DMM) with optimal expected delay O(log log (n)) per step of simulation. The time bound for the delay is guaranteed with overwhelming probability. The algorithm is based on hashing and uses a novel simulation scheme. The best previous simulations use a simpler scheme based on hashing and have much larger expected delay: Θ(log(n)/log log (n)) for the simulation of an n-processor PRAM on an n processor DMM, and Θ(log(n)) in the case where the simulation preserves the processor-time product.

We present a distributed (dynamic) dictionary implemented on a complete network of p processors.The (randomized) algorithm is based on hashing and needs expected O(n/p) time to execute n arbitrary instructions (Insert, Delete, Lookup).The response time for each lookup is expected constant.The algorithm applies a novel, randomized construction of hash functions.These functions can be evaluated in constant time, constructed on sublinear space in sublinear expected time, and have many features of random functions.The algorithm further makes use of a new Monte Carlo type sequential dictionary with worst case constant time per instruction, which was recently developed by the authors.Applications of the distributed dictionary are e.g. two improvements of PRAM-simulations: A PRAM with p processors can be simulated by a complete network with p processors with expected delay log p/ log log p (before: logp), and on one with p/logp processors with optimal expected delay logp (before: pl-e processors, delay pC).

Article Free Access Share on Not all keys can be hashed in constant time Authors: J. Gil Dept. of Gomp. Sc. Hebrew University, Jerusalem, 91904, Israel Dept. of Gomp. Sc. Hebrew University, Jerusalem, 91904, IsraelView Profile , F. Meyer auf der Heide Fachbereich 17, Mathematik/Informatik, Univesität. Gll Paderborn, D-4790 Paderborn, Fed.Rep. of Germany Fachbereich 17, Mathematik/Informatik, Univesität. Gll Paderborn, D-4790 Paderborn, Fed.Rep. of GermanyView Profile , A. Wigderson Dept. of Gomp. Sc. Hebrew University, Jerusalem, 91904, Israel Dept. of Gomp. Sc. Hebrew University, Jerusalem, 91904, IsraelView Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990Pages 244–253https://doi.org/10.1145/100216.100247Published:01 April 1990Publication History 10citation330DownloadsMetricsTotal Citations10Total Downloads330Last 12 Months29Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on An optimal parallel dictionary Authors: M. Dietzfelbinger Fachbereich 17 - Mathematik - Informatik, Universität-GH Paderborn, D-4790 Paderborn, Fed. Rep. of Germany Fachbereich 17 - Mathematik - Informatik, Universität-GH Paderborn, D-4790 Paderborn, Fed. Rep. of GermanyView Profile , F. Meyer auf der Heide Fachbereich 17 - Mathematik - Informatik, Universität-GH Paderborn, D-4790 Paderborn, Fed. Rep. of Germany Fachbereich 17 - Mathematik - Informatik, Universität-GH Paderborn, D-4790 Paderborn, Fed. Rep. of GermanyView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989Pages 360–368https://doi.org/10.1145/72935.72974Published:01 March 1989Publication History 18citation253DownloadsMetricsTotal Citations18Total Downloads253Last 12 Months15Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A randomized algorithm is given for the dictionary problem with O(1) worst-case time for lookup and O(1) amortized expected time for insertion and deletion. An Omega (log n) lower bound is proved for the amortized worst-case time complexity of any deterministic algorithm in a class of algorithms encompassing realistic hashing-based schemes. If the worst-case lookup time is restricted to k, then the lower bound for insertion becomes Omega (kn/sup 1/k/).>

Let M be a parallel RAM with p processors and arithmetic operations addition and subtraction recognizing L ⊂ N n in T steps. (Inputs for M are given integer by integer, not bit by bit.) Then L can be recognized by a (sequential) linear search algorithm (LSA) in O ( n 4 (log( n ) + T + log( p ))) steps. Thus many n -dimensional restrictions of NP-complete problems (binary programming, traveling salesman problem, etc.) and even that of the uniquely optimum traveling salesman problem, which is Δ P 2 -complete, can be solved in polynomial time by an LSA. This result generalizes the construction of a polynomial LSA for the n -dimensional restriction of the knapsack problem previously shown by the author, and destroys the hope of proving nonpolynomial lower bounds on LSAs for any problem that can be recognized by a PRAM as above with 2 poly( n ) processors in poly( n ) time.

In A time space tradeoff for sorting on non-oblivious machines, Borodin et al. [J. Comput. System Sci., 22 (1981), pp. 351–364] proved that to sort n elements requires $TS = \Omega (n^2 )$ where $T = $ time and $S = $ space on a comparison based branching program. Although element distinctness and sorting are equivalent problems on a computation tree, the stated tradeoff result does not immediately follow for element distinctness or indeed for any decision problem. In this paper, we are able to show that $TS = \Omega (n^{{3 / 2}} \sqrt {\log n} )$ for deciding element distinctness (or the sign of a permutation).

The model we consider-is the (concurrent-write, PRIORITY) PRAM. It has n synchronous processors, which communicate via an infinite shared memory. When several processors simultaneously write to the same cell, the one with the largest index succeeds. We allow the processors arbitrary computational power. Our main result is that sorting n integers requires $\Omega (\sqrt {\log n} )$ steps in this strong model. This bound is proved in two stages. First, using a novel Ramsey theoretic argument, we “reduce” sorting on a PRAM to sorting on a parallel merge tree. This tree is a generalization of Valiant’s parallel comparison tree from [V] in which at every step n pairs of (previously ordered) sets are merged (rather then n pairs of elementscompared). The second stage is proving the lower bound for such trees. The Ramsey theoretic technique, together with known methods for bounding the “degree” of the computation, can be used to unify and generalize previous lower bounds for PRAM’s. For example, we can show that the computation of any symmetric polynomial (e.g. the sum or product) on n integers requires exactly $\log _2 n$ steps.

A parallel computer (PC) with fixed communication network is called fair if the degree of this network is bounded, otherwise it is called unfair. In a PC with predictable communication each processor can precompute the addresses of the processors it wants to communicate with in the next t steps in $O(t)$ steps. For an arbitrary $\varepsilon > 0$ we define fair PC’s M and $M'$ with $O(n^{1 + \varepsilon } )$ processors each. $M(M')$ can simulate each unfair PC with predictable communication and $O(\log (n))$ storage locations per processor (each fair PC) with n processors with constant time loss. $M'$ improves a result from [Acts Informatics, 19 (1983), pp. 269–296] where a time loss of $O(\log \log (n))$ was achieved. Assuming some reasonable properties of simulations we finally prove a lower bound $\Omega (\log (n))$ for the time loss of a fair PC which can simulate each unfair PC. Applying fast sorting or packet switching algorithms (Proc.15th Annual ACM Symposiums on Theory of Computing, Boston, 1983, pp. 1–9; 10–16; Proc. ACM Symposiums on Principles of Distributed Computing, Ottawa, 1982) one sees easily that this bound is asymptotically tight.

The "component counting lower bound" known for deterministic linear search algorithms (LSA's) also holds for their probabilistic versions (PLSA's) for many problems, even if two-sided error is allowed, and if one does not charge for probabilistic choice. This implies lower bounds on PLSA's for e.g. the element distinctness problem (n log n) or the knapsack problem (n2). These results yield the first separations between probabilistic and non-deterministic LSA's, because the above problems are non-deterministically much easier. Previous lower bounds for PLSA's either only worked for one-sided error "on the nice side", i.e. on the side where the problems are even non-deterministically hard, or only for probabilistic comparison trees. The proof of the lower bound differs fundamentally from all known lower bounds for LSA's or PLSA's, because it does not reduce the problem to a combinatorial one but argues extensively about e.g. a non-discrete measure for similarity of sets in Rn. This lower bound result solves an open problem posed by Manber and Tompa as well as by Snir. Furthermore, a PLSA for n input variables with two-sided error and expected runtime T can be simulated by a (deterministic) LSA in T2n steps. This proves that the gaps between probabilistic and deterministic LSA's shown by Snir cannot be too large. As this simulation even holds for algebraic computation trees we show that probabilistic and deterministic versions of this model are polynomially related. This is a weaker version of a result due to the author which shows that in case of LSA's, even the non-deterministic and deterministic versions are polynomially related.

We consider PRAM's with arbitrary computational power for individual processors, infinitely large shared memory and "priority" writeconflict resolution. The main result is that sorting n integers with n processors requires Ω(√log n) steps in this strong model. We also show that computing any symmetric polynomial (e.g. the sum or product) of n integers requires exactly log2n steps, for any finite number of processors.

In this paper we compare the power of the two most commonly used concurrent-write models of parallel computation, the COMMON PRAM and the PRIORITY PRAM. These models differ in the way they resolve write conflicts. If several processors want to write into the same shared memory cell at the same time, in the COMMON model they have to write the same value. In the PRIORITY model, they may attempt to write different values; the processor with smallest index succeeds.

Veröffentlichungen der Universität ohne VL-DOI. Meyer auf der Heide, Friedhelm: Fast algorithms for N-dimensional restrictions of hard problems. In: Journal of the Association for Computing Machinery. Vol.1988. 2009, page 740-747

The problem of recognizing the language L n ( L n, k ) of solvable Diophantine linear equations with n variables (and solutions from {O, … , k } n ) is considered. The languages ∪ nϵN L n , ∪ nϵN L n, l , the knapsack problem, are NP-complete. The Ω( n 2 lower bound for L n ,1 on linear search algorithms due to Dobkin and Lipton is generalized to an Ω( n 2 log( k + 1)) lower bound for L n, k . The method of Klein and Meyer auf der Heide is further improved to carry over the Ω( n 2 ) lower bound for L n,1 to random access machines (RAMS) in such a way that it holds for a large class of problems and for very small input sets. By this method, lower bounds that depend on the input size, as is necessary for L n , are proved. Thereby, an Ω( n 2 log( k + 1)) lower bound is obtained for RAMS recognizing L n or L n, k , for inputs from {0, … , ( nk ) 0 ( n 2 ) } n .

Lower bounds for sequential and parallel random access machines (RAM's, WRAM's) and distributed systems of RAM's (DRAM's) are proved. We show that, when p processors instead of one are available, the computation of certain functions cannot be speeded up by a factor p but only by a factor 0 (log(p)). For DRAM's with communication graph of degree c a maximal speedup 0 (log(c)) can be achieved for these problems. We apply these results to testing the solvability of linear diophantine equations. This generalizes a lower bond of Yao for parallel computation trees. Improving results of Dobkin/Lipton and Klein/Meyer auf der Heide, we establish large lower bounds for the above problem on RAM's. Finnaly we prove that at least log (n) + 1 steps are necessary for computing the sum of n integers by a WRAM regardless of the number of processors and the solution of write conflicts.

article Free Access Share on A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem Author: Friedhelm Meyer auf der Heide Fachbereich 20 (Informatik), Johann Wolfgang Goethe Universitat, Mertonstrasse 17-25, 6000 Frankfurt am Main, West Germany Fachbereich 20 (Informatik), Johann Wolfgang Goethe Universitat, Mertonstrasse 17-25, 6000 Frankfurt am Main, West GermanyView Profile Authors Info & Claims Journal of the ACMVolume 31Issue 3July 1984 pp 668–676https://doi.org/10.1145/828.322450Published:26 June 1984Publication History 68citation918DownloadsMetricsTotal Citations68Total Downloads918Last 12 Months89Last 6 weeks13 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a Linear Search Algorithm which decides the n-dimensional knapsack problem in n4log(n) + 0.(n3) steps. This algorithm works for inputs consisting of n numbers for some arbitrary but fixed integer n. This result solves an open problem posed for example in [6] and [7] by Dobkin / Lipton and A.C.C. Yao, resp.. It destroys the hope of proving large lower bounds for this NP-complete problem in the model of Linear Search Algorithms.