content-distribution-networks or P2P overlays. Within this paper

we extend approaches for heterogeneous placement scenarios

described in prior publications. Therefor we presume heterogeneous

server peers' bandwidth, HD capacity, and movie popularities.

Movie documents are replicated and placed onto server peers with

respect to the predicted popularity values. Thus each document

aims to gain fair networks resources according to its popularity.

We present simulation results of heuristics of different placement

strategies and compare them with a near optimal technique. AU - Schomaker, Gunnar AU - Loeser, Christoph AU - Schubert, Matthias ID - 19854 T2 - 5th International Conference on Networking (ICN). TI - Predictive Replication and Placement Strategies for Movie Documents in heterogeneous Content Delivery Networks ER - TY - CHAP AU - Dynia, Miroslaw AU - Kutyłowski, Jarosław AU - Lorek, Paweł AU - Meyer auf der Heide, Friedhelm ID - 16476 SN - 1571-5736 T2 - IFIP International Federation for Information Processing TI - Maintaining Communication Between an Explorer and a Base Station ER - TY - GEN AB - We present a parallel algorithm for the rendering of complex three-dimensional scenes. The algorithm runs across heterogeneous architectures of PC-clusters consisting of a visualization-node, equipped with a powerful graphics adapter, and cluster nodes requiring weaker graphics capabilities only. The visualization-node renders a mixture of scene objects and simplified meshes (Reliefboards). The cluster nodes assist the visualization-node by asynchronous computing of Reliefboards, which are used to replace and render distant parts of the scene. Our algorithm is capable of gaining significant speedups if the cluster's nodes provide weak graphics adapters only. We trade the number of cluster nodes off the scene objects' image quality. ED - Rammig, Franz-Josef ED - Dangelmaier, Wilhelm ED - Karl, Holger ED - Mertsching, Bärbel ED - Meyer auf der Heide, Friedhelm ED - Trächtler, Ansgar ID - 17417 TI - Self-Coordinating Systems: The Next Challenge in Research on Distributed Systems ER - TY - JOUR AU - Schindelhauer, Christian AU - Volbert, Klaus AU - Ziegler, Martin ID - 17979 JF - Computational Geometry SN - 0925-7721 TI - Geometric spanners with applications in wireless networks ER - TY - THES AU - Damerow, Valentina ID - 18972 SN - 3-939350-09-5 TI - Average and Smoothed Complexity of Geometric Structures ER - TY - CONF AU - Briest, Patrick AU - Gunia, Christian ID - 19691 T2 - Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC) TI - Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels ER - TY - CONF AU - Grünewald, Matthias AU - Meyer auf der Heide, Friedhelm AU - Rührup, Stefan AU - Schindelhauer, Christian AU - Volbert, Klaus ID - 17619 T2 - New Trends in Parallel & Distributed Computing, 6th Int. Heinz Nixdorf Symposium TI - Directional Communication in Mobile Ad Hoc Networks ER - TY - CONF AB - #hniid 2484 AU - Kortenjan, Michael AU - Schomaker, Gunnar ID - 19932 T2 - 4th International Conference on Virtual Reality, Computer Graphics, Visualization and Interaction (Afrigraph 2006) TI - Size equivalent cluster trees (SEC-Trees) realtime rendering of large industrial scenes ER - TY - CHAP AU - Demaine, Erik D. AU - Meyer auf der Heide, Friedhelm AU - Pagh, Rasmus AU - Pǎtraşcu, Mihai ID - 16472 SN - 0302-9743 T2 - LATIN 2006: Theoretical Informatics TI - De Dictionariis Dynamicis Pauco Spatio Utentibus ({lat.} On Dynamic Dictionaries Using Little Space) ER - TY - BOOK AU - Monien, Burkhard AU - Meyer auf der Heide, Friedhelm ID - 17475 SN - 978-3-939350-00-2 TI - New trends in parallel and distributed computing VL - 181 ER - TY - CHAP AU - Meer, Klaus AU - Ziegler, Martin ID - 17987 SN - 0302-9743 T2 - Logical Approaches to Computational Barriers TI - Uncomputability Below the Real Halting Problem ER - TY - CONF AU - Sohler, Christian AU - Frahling, Gereon AU - Marchetti-Spaccamela, Alberto AU - Leonardi, Stefano AU - Buriol, Luciana ID - 18745 TI - Counting Triangles in Data Streams ER - TY - THES AU - Frahling, Gereon ID - 18973 SN - 978-3-942647-09-0 TI - Algorithms for Dynamic Geometric Data Streams ER - TY - CONF AU - Brinkmann, A. AU - Effert, S. AU - Heidebuer, M. AU - Vodisek, M. ID - 19870 SN - 0769525520 T2 - 5th International Conference on Networking (ICN) TI - Realizing Multilevel Snapshots in Dynamically Changing Virtualized Storage Environments ER - TY - CHAP AU - Köhler, Sven AU - Schindelhauer, Christian AU - Ziegler, Martin ID - 17988 SN - 0302-9743 T2 - Fundamentals of Computation Theory TI - On Approximating Real-World Halting Problems ER - TY - CONF AU - Dangelmaier, Wilhelm AU - Mueck, Bengt AU - Fischer, Matthias AU - Mahajan, Kiran AU - Laroque, Christoph ID - 18366 T2 - Simulation in wider Europe - 19th European Conference on Modelling and Simulation ECMS 2005 TI - Methods to lead the user to significant processes in a 3D material flow simulation ER - TY - JOUR AB - Nowadays companies operate in a difficult environment: the dynamics of innovations increase and product life cycles become shorter. Furthermore products and the corresponding manufacturing processes get more and more complex. Therefore, companies need new methods for the planning of manufacturing systems. One promising approach in this context is digital factory/virtual productionthe modeling and analysis of computer models of the planned factory with the objective to reduce time and costs. For the modeling and analysis various simulation methods and programs have been developed. They are a highly valuable support for planning and visualizing the manufacturing system. But there is one major disadvantage: only experienced and long trained experts are able to operate with these programs. The graphical user interface is very complex and not intuitive to use. This results in an extensive and error-prone modeling of complex simulation models and a time-consuming interpretation of the simulation results. To overcome these weak points, intuitive and understandable manmachine interfaces like augmented and virtual reality can be used. This paper describes the architecture of a system which uses the technologies of augmented and virtual reality to support the planning process of complex manufacturing systems. The proposed system assists the user in modeling, the validation of the simulation model, and the subsequent optimization of the production system. A general application of the VR- and AR-technologies and of the simulation is realized by the development of appropriate linking and integration mechanisms. For the visualization of the arising 3D-data within the VR- and AR-environments, a dedicated 3D-rendering library is used. AU - Dangelmaier, Wilhelm AU - Fischer, Matthias AU - Gausemeier, Jürgen AU - Grafe, Michael AU - Matysczok, Carsten AU - Mueck, Bengt ID - 17414 JF - Computers in Industry SN - 0166-3615 TI - Virtual and augmented reality support for discrete manufacturing system simulation ER - TY - CONF AU - Oesterdiekhoff, Brigitte ID - 18450 T2 - IEEE International Conference on Emerging Technologies and Factory Automation (ETFA) TI - Glaschick, Rainer; Service Oriented Interface Design for Embedded Devices ER - TY - CONF AB - The page migration problem is one of subproblems of data management in networks. It occurs

in a distributed network of processors sharing one indivisible memory page of size D. During runtime,

the processors access a unit of data from the page, and the system is allowed to migrate the page

between the processors. The problem is to compute (on-line) a schedule of page movements

to minimize the total communication cost.

The Dynamic Page Migration problem is an extension to the page migration.

It attempts to model the network dynamics, occurring, for example, in mobile networks.

However, the pace of changes is restricted, i.e. the distances between processors can

change only by a constant per round.

The movement of the nodes induce changes in the communication cost between each pair of nodes,

which is proportional to the distance between them raised to some power $alpha$.

This is typical for mobile wireless networks, where nodes can move with a constant speed,

and the cost of communication is measured in terms of energy used for sending the data.

Thus, by setting $alpha$ equal to the propagation exponent of the medium,

cost minimization becomes minimizing the total energy consumption in the system.

However, as proven in citedynamic-page-migration, if both network mobility and

request sequence are created by an adversary, then the competitive ratio is polynomially large in D and

in the number of the nodes. In our search for a reasonable, close-to-reality model, in this paper we

consider a scenario in which the network mobility is adversarial, but the requests are

generated randomly by a stochastic process. We design an algorithm MTFR for this scenario,

and prove that it is O(1)-competitive, on expectation and with high probability. AU - Bienkowski, Marcin ID - 18917 T2 - Proc. of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005) TI - Dynamic Page Migration with Stochastic Requests ER - TY - CONF AB - We consider Dynamic Page Migration (DPM) problem, one of the fundamental subproblems of data management in dynamically changing networks. We investigate a hybrid scenario, where access patterns to the shared object are dictated by an adversary, and each processor performs a random walk in X. We extend the previous results of [4]: we develop algorithms for the case where X is a ring, and prove that with high probability they achieve a competitive ratio of O~(min{D−−√4,n}), where D is the size of the shared object and n is the number of nodes in the network. These results hold also for any d-dimensional torus or mesh with diameter at least Ω~(D−−√). AU - Bienkowski, Marcin AU - Korzeniowski, Miroslaw ID - 18912 SN - 0302-9743 T2 - Proc. of the European Conference in Parallel Processing (Euro-Par) TI - Dynamic Page Migration Under Brownian Motion ER - TY - CONF AB - Bluetooth is a wireless communication standard developed for personal area networks (PAN) that gained popularity in the last years. It was designed to connect a few devices together, however nowadays there is a need to build larger networks. Construction and maintenance algorithms have great effect on performance of the network. We present an algorithm based on Cube Connected Cycles (CCC) topology and show how to maintain the network so that it is easily scalable. Our design guarantees good properties such as constant degree and logarithmic dilation. Besides, the construction costs are proven to be at most constant times larger than any other algorithm would need. AU - Bienkowski, Marcin AU - Brinkmann, André AU - Korzeniowski, Miroslaw AU - Orhan, Orhan ID - 18924 SN - 0302-9743 T2 - Proceedings of the 4th International Conference on Networking TI - Cube Connected Cycles Based Bluetooth Scatternet Formation VL - 3420 ER - TY - CONF AB - Data has become the most valuable asset for many companies; loosing important data can cause companies to fail quite immediately. The protection of data inside storage systems is mostly achieved by using a RAID scheme that adds redundant data to user data, enabling recovery from single or multiple disk failures. This protection against data loss in case of a disk failure can be achieved either by dedicated hardware or a software RAID solution.

One major advantage of software RAID is that it comes for free as a built-in functionality in many operating systems like Linux or Microsoft Windows. The drawback of the built-in functionality is that it is not suited to run in multiple server environments; synchronization and recovery processes can be corrupted if more than a single server is allowed to access a software RAID volume.

In this paper, we present an enhancement for the Linux md-driver that enables a consistent usage of RAID in multiple server environments. Based on the V:DRIVE virtualization environment, RAID volumes can be consistently synchronized and recovered even in distributed environments. Besides the architectural concepts, we present measurements that indicate the viability of this enhanced, distributed version of md. AU - Brinkmann, André AU - Effert, Sascha AU - Heidebuer, Michael AU - Vodisek, Mario ID - 19871 T2 - In Proceedings of the International Workshop on Storage Network Architecture and Parallel I/Os TI - Distributed MD ER - TY - CONF AU - Klein, Jan AU - Zachmann, Gabriel ID - 19890 T2 - Proceedings of the 13-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision'2005 (WSCG'2005) TI - Interpolation Search for Point Cloud Intersection ER - TY - CONF AU - Klein, Jan AU - Zachmann, Gabriel ID - 19888 T2 - ACM SIGGRAPH 2005 Posters on - SIGGRAPH '05 TI - The expected running time of hierarchical collision detection ER - TY - JOUR AU - Ziegler, Martin ID - 15058 JF - Theoretical Computer Science SN - 0304-3975 TI - Stability versus speed in a computable algebraic model ER - TY - CONF AU - Bienkowski, Marcin AU - Damerow, Valentina AU - Meyer auf der Heide, Friedhelm AU - Sohler, Christian ID - 17112 T2 - Proceedings of the 21st European Workshop on Computational Geometry, Eindhoven, The Netherlands, March 9-11, 2005 TI - Average case complexity of Voronoi diagrams of n sites from the unit cube ER - TY - CONF AU - Fischer, Matthias AU - Mueck, B. AU - Mahajan, K. AU - Kortenjan, M. AU - Laroque, C. AU - Dangelmaier, W. ID - 17415 SN - 0780395190 T2 - Proceedings of the Winter Simulation Conference TI - Multi-User Support and Motion Planning of Humans and Humans Driven Vehicles in Interactive 3D Material Flow Simulations ER - TY - CHAP AU - Meer, Klaus AU - Ziegler, Martin ID - 17989 SN - 0302-9743 T2 - Fundamentals of Computation Theory TI - An Explicit Solution to Post’s Problem over the Reals ER - TY - CONF AB - The sometimes so-called Main Theorem of Recursive Analysis implies that any computable real function is necessarily continuous. We consider three relaxations of this common notion of real computability for the purpose of treating also discontinuous functions f:R->R:

*) non-deterministic computation;

*) relativized computation, specifically given access to oracles like 0' or 0'';

*) encoding input x and/or output y=f(x) in weaker ways according to the Real Arithmetic Hierarchy.

It turns out that, among these approaches, only the first one provides the required power. AU - Ziegler, Martin ID - 18280 SN - 0302-9743 T2 - Proc. CiE 2005: New Computational Paradigms TI - Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism VL - 3526 ER - TY - CONF AU - Loeser, Christoph AU - Drüke, Isabell AU - Oesterdiekhoff, Brigitte ID - 18449 T2 - IEEE International Conference on Industrial Informatics (INDIN) TI - Glaschick, Rainer: Integrative Approach of Web Services and Universal Plug and Play within an AV Scenario ER - TY - JOUR AB - We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\mathbb R^d$. We focus on the setting where the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within $1 + \eps$ using only $\widetilde{\O}(\sqrt{n} \, \text{poly} (1/\eps))$ queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries. Read More: https://epubs.siam.org/doi/10.1137/S0097539703435297 AU - Czumaj, Artur AU - Ergün, Funda AU - Fortnow, Lance AU - Magen, Avner AU - Newman, Ilan AU - Rubinfeld, Ronitt AU - Sohler, Christian ID - 18855 IS - 1 JF - SIAM Journal on Computing SN - 0097-5397 TI - Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time VL - 35 ER - TY - CONF AB - Modern computer graphics systems are able to render sophisticated 3D szenes consisting of millions of polygons. In this paper we address the problem of occlusion culling. Aila, Miettinen, and Nordlund suggested to implement a FIFO buffer on graphics cards which is able to delay the polygons before drawing them. When one of the polygons within the buffer is occluded or masked by another polygon arriving later from the application, the rendering engine can drop the occluded one without rendering, saving important rendering time.

We introduce a theoretical online model to analyse these problems in theory using competitive analysis. For different cost measures addressed we invent the first competitive algorithms for online occlusion culling. Our implementation shows that these algorithms outperform known ones for real 3D scenes as well. AU - Frahling, Gereon AU - Krokowski, Jens ID - 18867 SN - 0302-9743 T2 - Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005) TI - Online Occlusion Culling VL - 3669 ER - TY - CONF AB - The dynamic page migration problem citedynamic-page-migration is defined in

a distributed network of $n$ mobile nodes sharing one indivisible memory page

of size $D$. During runtime, the nodes can both access a unit of data from

the page and move with a constant speed, thus changing the costs of communication.

The problem is to compute

to minimize the total communication cost.

In this paper we construct and analyze the first deterministic algorithm for this problem.

We prove that it achieves an (up to a constant factor) optimal competitive ratio

$O(n cdot sqrtD)$. We show that the randomization of this algorithm

improves this ratio to $O(sqrtD cdot log n)$ (against an oblivious adversary).

This substantially improves an $O(n cdot sqrtD)$ upper bound from citedynamic-page-migration.

We also give an almost matching lower bound of $Omega(sqrtD cdot sqrtlog n)$ for this problem. AU - Bienkowski, Marcin AU - Dynia, Miroslaw AU - Korzeniowski, Miroslaw ID - 18925 SN - 0302-9743 T2 - Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS) TI - Improved Algorithms for Dynamic Page Migration ER - TY - CONF AB - We present k-Flipper, a graph transformation algorithm that transforms regular undirected graphs. Given a path of k+2 edges it interchanges the end vertices of the path. By definition this operation preserves regularity and connectivity. We show that every regular connected graph can be reached by a series of these operations for all k ¡Ý 1. We use a randomized version, called Random k-Flipper, in order to create random regular connected undirected graphs that may serve as a backbone for peer-to-peer networks. We prove for degree d¡Ê ¦¸(log n) that a series of O(dn) Random k-Flipper operations with k ∈ ¦¨(d2n2 log 1/¦Å) transforms any graph into an expander graph with high probability, i.e. 1-n-¦¨(1). The Random 1-Flipper is symmetric, i.e. the transformation probability from any labeled

The cell structure has two advantages for applying position-based routing: It helps to determine local minima for greedy forwarding and improves recovery from such minima, because for recovery all edges can be used in contrast to other topology-based rules that can be appliedonly on a planar subgraph.

For the analysis of position-based routing algorithms the measures time and traffic are based on the cell structure. The difficulty of exploring the network is expressed by the size of the barriers (i.e. the number of cells in the perimeters). Exploration can be done in parallel, but with increasing traffic. We propose a comparative measure to assess both time and traffic, the combined comparative ratio, which is the maximum of the ratio of routing time and optimal time and the ratio of the traffic and the minimum exploration costs.

While flooding and common single-path strategies have a linear ratio, we present a simple algorithm that has a sub-linear

combined comparative ratio of O(sqrt(h)), where h is the minimal hop distance between source and target. AU - Rührup, S. AU - Schindelhauer, C. ID - 19834 SN - 0769523129 T2 - 19th IEEE International Parallel and Distributed Processing Symposium TI - Competitive Time and Traffic Analysis of Position-Based Routing using a Cell Structure ER - TY - CONF AB - Recent developments both in the business and the technological domain have led to a significant increase in demand for Business Intelligence (BI) infrastructures that can handle huge amounts of data in small time frames. BI applications are increasingly used by large user bases on all management levels; support tasks spanning the complete value chain are based on transactional data and are directly coupled with operational systems in closed loop approaches.

To effectively handle the resulting data volume turns out to be an extremely challenging task which encompasses a variety of issues on different levels. We propose an integrated multi layer tool for monitoring, benchmarking, analyzing, and optimizing the performance of such BI infrastructures.

Inside this paper we give a coarse outline of the tools architecture and demonstrate the value of distinct measurement points at operating system layer. For that purpose we introduce a kernel based benchmark environment and present first measurement results. The gathered data clearly indicates that a meaningful analysis of performance benchmarks without kernel trace points is of limited value - which shows the necessity to consider a separate component within the tools architecture. AU - Brinkmann, André AU - Effert, Sascha AU - Heidebuer, Michael AU - Vodisek, Mario AU - Baars, Henning ID - 19872 T2 - In Proceedings of the International Workshop on Storage Network Architecture and Parallel I/Os TI - An integrated Architecture for Business Intelligence support from Application down to Storage ER - TY - CHAP AU - Bienkowski, Marcin AU - Korzeniowski, Miroslaw AU - Meyer auf der Heide, Friedhelm ID - 16468 SN - 0302-9743 T2 - Peer-to-Peer Systems IV TI - Dynamic Load Balancing in Distributed Hash Tables ER - TY - GEN ED - Leonardi, Stefano ED - Meyer auf der Heide, Friedhelm ED - Wagner, Dorothea ID - 17113 TI - Abstracts Collection -- Algorithmic Aspects of Large and Complex Networks VL - 05361 ER - TY - CONF AB - We present a web computing library (PUBWCL) in Java that allows to execute strongly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style on PCs distributed over the internet whose owners are willing to donate their unused computation power. PUBWCL is realized as a peer-to-peer system and features migration and restoration of BSP processes executed on it. The use of Java guarantees a high level of security and makes PUBWCL platform independent. In order to estimate the loss of efficiency inherent in such a Java-based system, we have compared it to our C-based PUB-Library. AU - Bonorden, Olaf AU - Gehweiler, Joachim AU - Meyer auf der Heide, Friedhelm ID - 16470 SN - 0302-9743 T2 - Proceeedings of 6th International Conference on Parallel Processing and Applied Mathematics (PPAM) TI - A Web Computing Environment for Parallel Algorithms in Java ER - TY - CONF AB - The Hierarchical Layer Graph (HL graph) is a promising network topology for wireless networks with

variable transmission ranges. It was introduced and analyzed by Meyer auf der Heide et al. 2004.

In this paper we present a distributed, localized and resource-efficient algorithm for constructing this graph. The qualtiy of the HL graph depends on the domination radius and the publication radius, which affect the amount of interference in the network. These parameters also determine whether the HL graph is a c-spanner, which implies an energy-efficient topology. We investigate the performance on randomly distributed node sets and show that the restrictions on these parameters derived from a worst case analysis are not so tight using realistic settings.

Here, we present the results of our extensive experimental evaluation, measuring congestion, dilation and energy. Congestion includes the load that is induced by interfering edges. We distinguish between congestion and realistic congestion where we also take the signal-to-interference ratio into account.

Our experiments show that the HL graph contains energy-efficient paths as well as paths with a few number of hops while preserving a low congestion. AU - Rührup, Stefan AU - Schindelhauer, Christian AU - Volbert, Klaus ID - 19835 SN - 0302-9743 T2 - Proc. of 4th International Conference on Ad-Hoc, Mobile & Wireless Networks (ADHOC-NOW 2005) TI - Performance Analysis of the Hierarchical Layer Graph for Wireless Networks VL - 3738 ER - TY - CONF AU - Loeser, Chris AU - Schomaker, Gunnar AU - Brinkmann, André AU - Vodisek, Mario AU - Heidebuer, Michael ID - 19912 SN - 0302-9743 T2 - Proceedings of the 4th International Conference on Networking TI - Content Distribution in Heterogenous Video-on-Demand P2P Networks with ARIMA Forecasts VL - 3421 ER - TY - CHAP AU - Bienkowski, Marcin AU - Meyer auf der Heide, Friedhelm ID - 16469 SN - 0302-9743 T2 - Mathematical Foundations of Computer Science 2005 TI - Page Migration in Dynamic Networks ER -