@phdthesis{19613, author = {{Rührup, Stefan}}, isbn = {{978-3-939350-22-4}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Position-based Routing Strategies}}}, volume = {{203}}, year = {{2006}}, } @inproceedings{19690, author = {{Briest, Patrick and Krysta, Piotr}}, booktitle = {{Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA)}}, title = {{{Single-Minded Unlimited Supply Pricing on Sparse Instances}}}, year = {{2006}}, } @inproceedings{19691, author = {{Briest, Patrick and Gunia, Christian}}, booktitle = {{Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC)}}, title = {{{Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels}}}, year = {{2006}}, } @misc{19718, author = {{Degener, Bastian}}, title = {{{Die Analyse von Estimation-of-Distribution-Algorithmen auf ausgewählten Funktionen}}}, year = {{2006}}, } @inproceedings{19808, abstract = {{We study the problem of designing an adaptive hash table for redundant data storage in a system of storage devices with arbitrary capacities. Ideally, such a hash table should make sure that (a) a storage device with x% of the available capacity should get x% of the data, (b) the copies of each data item are distributed among the storage devices so that no two copies are stored at the same device, and (c) only a near-minimum amount of data replacements is necessary to preserve (a) and (b) under any change in the system. Hash tables satisfying (a) and (c) are already known, and it is not difficult to construct hash tables satisfying (a) and (b). However, no hash table is known so far that can satisfy all three properties as long as this is in principle possible. We present a strategy called SPREAD that solves this problem for the first time. As long as (a) and (b) can in principle be satisfied, SPREAD preserves (a) for every storage device nearly optimal, with high probability, guarantees (b) for every data item, and only needs a constant factor more data replacements than minimum possible in order to preserve (a) and (b).}}, author = {{Mahlmann, Peter and Schindelhauer, Christian}}, booktitle = {{Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures - SPAA '06}}, isbn = {{1595934529}}, pages = {{308----317}}, title = {{{Distributed random digraph transformations for peer-to-peer networks}}}, doi = {{10.1145/1148109.1148162}}, year = {{2006}}, } @inproceedings{19838, author = {{Rührup, Stefan and Schindelhauer, Christian}}, booktitle = {{Proc. of the 17th International Symposium on Algorithms and Computation (ISAAC 2006)}}, isbn = {{9783540496946}}, issn = {{0302-9743}}, title = {{{Online Multi-path Routing in a Maze}}}, doi = {{10.1007/11940128_65}}, year = {{2006}}, } @inproceedings{19839, abstract = {{Storage Area Networks commonly consist a more or less static set of n data servers that handle a dynamic collection of m documents. Such SANs can minimize the access time to documents by distributing each document among several servers, allowing users to access documents in parallel. This paper describes an efficient solution for providing parallel access to multiple hard disks for popular content. In extension to previous approaches we provide an efficient and elegant hash table data structure for utilizing the full capacity of each data server. Concerning the dynamics, documents as well as server may be added or removed from the system causing only local changes. We consider sequential and parallel access to data in the average case. For the average time model we present a fast optimal algorithm.}}, author = {{Schindelhauer, Christian and Schomaker, Gunnar}}, booktitle = {{5th International Conference on Networking (ICN)}}, isbn = {{0769525520}}, title = {{{SAN Optimal Multi Parameter Access Scheme}}}, doi = {{10.1109/icniconsmcl.2006.190}}, year = {{2006}}, } @techreport{19840, author = {{Rührup, Stefan and Schindelhauer, Christian}}, title = {{{Improved Bounds for Online Multi-Path Routing in Faulty Mesh Networks}}}, year = {{2006}}, } @inproceedings{19854, abstract = {{In previous publications there have been several proposals
regarding replica generation and placement of movie content in
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.}}, author = {{Schomaker, Gunnar and Loeser, Christoph and Schubert, Matthias}}, booktitle = {{5th International Conference on Networking (ICN).}}, title = {{{Predictive Replication and Placement Strategies for Movie Documents in heterogeneous Content Delivery Networks}}}, year = {{2006}}, } @inproceedings{19870, author = {{Brinkmann, Andre and Effert, Sascha and Heidebuer, Michael and Vodisek, Mario}}, booktitle = {{5th International Conference on Networking (ICN)}}, isbn = {{0769525520}}, title = {{{Realizing Multilevel Snapshots in Dynamically Changing Virtualized Storage Environments}}}, doi = {{10.1109/icniconsmcl.2006.182}}, year = {{2006}}, } @inproceedings{19932, abstract = {{#hniid 2484}}, author = {{Kortenjan, Michael and Schomaker, Gunnar}}, booktitle = {{4th International Conference on Virtual Reality, Computer Graphics, Visualization and Interaction (Afrigraph 2006)}}, title = {{{Size equivalent cluster trees (SEC-Trees) realtime rendering of large industrial scenes}}}, doi = {{10.1145/1108590.1108608}}, year = {{2006}}, } @inproceedings{24277, abstract = {{We propose a dynamic, ad-hoc communication network consisting of mobile units that can warn about traffic jams on motorways. Our goal is to provide a practical, low cost solution. Therefore we consider very simple wireless communication hardware, without collision detection, with very small bandwidth and a probabilistic model of link failure. We provide a complete system architecture. For this purpose we design and analyze solutions for size approximation, leader election and broadcasting. Our algorithms are fine-tuned for fast operation in a practical setting. We provide both a theoretical and experimental evaluation of our solutions. Our contribution is much different from the previous work, where either pure theoretical models with a pure theoretical analysis are provided or algorithms working in practical models are evaluated only through simulations.}}, author = {{Kutyłowski, Jarosław and Zagórski, Filip}}, booktitle = {{SOFSEM 2006: Theory and Practice of Computer Science}}, issn = {{0302-9743}}, title = {{{Reliable Broadcasting Without Collision Detection}}}, doi = {{10.1007/11611257_37}}, year = {{2006}}, } @inproceedings{26988, abstract = {{For most of today's IT environments, the tremendous need for storage capacity in combination with a required minimum I/O performance has become highly critical. In dynamically growing environments, a storage management solution's underlying data distribution scheme has great impact to the overall system I/O performance. The evaluation of a number of open system storage visualization solutions and volume managers has shown that all of them lack the ability to automatically adapt to changing access patterns and storage infrastructures; many of them require an error prone manual re-layout of the data blocks, or rely on a very time consuming re-striping of all available data. This paper evaluates the performance of conventional data distribution approaches compared to the adaptive virtualization solution V:DRIVE in dynamically changing storage environments. Changes of the storage infrastructure are normally not considered in benchmark results, but can have a significant impact on storage performance. Using synthetic benchmarks, V:DRIVE is compared in such changing environments with the non-adaptive Linux logical volume manager (LVM). The performance results of our tests clearly outline the necessity of adaptive data distribution schemes.}}, author = {{Brinkmann, Andre and Effert, Sascha and Heidebuer, Michael and Vodisek, Mario}}, booktitle = {{14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP'06)}}, title = {{{Influence of adaptive data layouts on performance in dynamically changing storage environments}}}, doi = {{10.1109/pdp.2006.44}}, year = {{2006}}, } @proceedings{17417, abstract = {{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.}}, editor = {{Rammig, Franz-Josef and Dangelmaier, Wilhelm and Karl, Holger and Mertsching, Bärbel and Meyer auf der Heide, Friedhelm and Trächtler, Ansgar}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts}}, title = {{{Self-Coordinating Systems: The Next Challenge in Research on Distributed Systems}}}, year = {{2006}}, } @book{17475, author = {{Monien, Burkhard and Meyer auf der Heide, Friedhelm}}, isbn = {{978-3-939350-00-2}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{New trends in parallel and distributed computing}}}, volume = {{181}}, year = {{2006}}, } @inproceedings{17619, author = {{Grünewald, Matthias and Meyer auf der Heide, Friedhelm and Rührup, Stefan and Schindelhauer, Christian and Volbert, Klaus}}, booktitle = {{New Trends in Parallel & Distributed Computing, 6th Int. Heinz Nixdorf Symposium}}, pages = {{225--234}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts}}, title = {{{Directional Communication in Mobile Ad Hoc Networks}}}, year = {{2006}}, } @inproceedings{18676, abstract = {{We present random sampling algorithms that with probability at least 1 - δ compute a (1 ± ǫ)- approximation of the clustering coefficient, the transitiv ity coefficient, and of the number of bipartite cliques in a graph given as a stream of edges. Our methods can be extended to approximately count the number of occurences of fixed constant-size subgraphs. Our a lgorithms only require one pass over the input stream and their storage space depends only on structural parameters of the graphs, the approxi- mation guarantee, and the confidence probability. For examp le, the algorithms to compute the clustering and transitivity coefficient depend on that coefficient but n ot on the size of the graph. Since many large social networks have small clustering and transitivity coe fficient, our algorithms use space independent of the size of the input for these graphs. We implemented our algorithms and evaluated their performance on networks from different appli- cation domains. The sizes of the considered input graphs varied from about 8, 000 nodes and 40, 000 edges to about 135 million nodes and more than 1 billion edges. For both algorithms we run experiments with a sample set size varying from 100, 000 to 1, 000, 000 to evaluate running time and approximation guarantee. Our algorithms appear to be time efficient for the se sample sizes.}}, author = {{Sohler, Christian and Frahling, Gereon and Marchetti-Spaccamela, Alberto and Leonardi, Stefano and Buriol, Luciana}}, booktitle = {{Proceedings of the European Conference on Complex Systems (ECCS'06)}}, title = {{{Computing Clustering Coefficients in Data Streams}}}, year = {{2006}}, } @inproceedings{18745, author = {{Sohler, Christian and Frahling, Gereon and Marchetti-Spaccamela, Alberto and Leonardi, Stefano and Buriol, Luciana}}, title = {{{Counting Triangles in Data Streams}}}, year = {{2006}}, } @inproceedings{18746, abstract = {{In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.}}, author = {{Sohler, Christian and Gehweiler, Joachim and Lammersen, Christiane}}, booktitle = {{Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}}, title = {{{A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem}}}, year = {{2006}}, } @inproceedings{18926, author = {{Dynia, Miroslaw and Korzeniowski, Miroslaw and Schindelhauer, Christian}}, booktitle = {{Architecture of Computing Systems - ARCS}}, isbn = {{9783540327653}}, issn = {{0302-9743}}, number = {{3894}}, pages = {{341----351}}, title = {{{Power-Aware Collective Tree Exploration}}}, doi = {{10.1007/11682127_24}}, year = {{2006}}, }