9 Search Results for "H�mmerli, Bernhard"


Document
Invited Talk
The Quest for Universally-Optimal Distributed Algorithms (Invited Talk)

Authors: Bernhard Haeupler

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)


Abstract
Many distributed optimization algorithms achieve an existentially-optimal round complexity (of (Õ(√n + D)), i.e., there exists some pathological worst-case topology on which no algorithm can be faster. However, most networks of interest allow for exponentially faster algorithms. This motivates two questions: - What network topology parameters determine the complexity of distributed optimization? - Are there universally-optimal algorithms that are as fast as possible on every single topology? This talk provides an overview over the freshly-completed 6-year program that resolves these 25-year-old open problems for a wide class of global network optimization problems including MST, (1+ε)-min cut, various approximate shortest path problems, sub-graph connectivity, etc. We provide several equivalent graph parameters that are tight universal lower bounds for the above problems, fully characterizing their inherent complexity. We also give the first universally-optimal algorithms approximately achieving this complexity on every topology. The quest for universally-optimal distributed algorithms required novel techniques that also answer fundamental (open) questions in seemingly unrelated fields, such as, network information theory, approximation algorithms, (oblivious) packet routing, (algorithmic & topological) graph theory, and metric embeddings. Generally, the problems addressed in these fields explicitly or implicitly ask to jointly optimize 𝓁_∞ & 𝓁₁ parameters such as congestion & dilation, communication rate & delay, capacities & diameters of subnetworks, or the makespan of packet routings. In particular, results obtained on the way include the following firsts: (Congestion+Dilation)-Competitive Oblivious Routing, Network Coding Gaps for Completion-Times, Hop-Constrained Expanders & Expander Decompositions, Bi-Criteria (Online / Demand-Robust) Approximation Algorithms for many Diameter-Constrained Network Design Problems (e.g., (Group) Steiner Tree/Forest), Makespan-Competitive (Compact and Distributed) Routing Tables, and (Probabilistic) Tree Embeddings for Hop-Constrained Distances. (Joint work with M. Ghaffari, G. Zuzic, D.E. Hershkowitz, D. Wajc, J. Li, H. Raecke, T. Izumi)

Cite as

Bernhard Haeupler. The Quest for Universally-Optimal Distributed Algorithms (Invited Talk). In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{haeupler:LIPIcs.DISC.2021.1,
  author =	{Haeupler, Bernhard},
  title =	{{The Quest for Universally-Optimal Distributed Algorithms}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.1},
  URN =		{urn:nbn:de:0030-drops-148030},
  doi =		{10.4230/LIPIcs.DISC.2021.1},
  annote =	{Keywords: Distributed algorithms}
}
Document
Globalizing Domain-Specific Languages (Dagstuhl Seminar 14412)

Authors: Betty H. C. Cheng, Benoit Combemale, Robert B. France, Jean-Marc Jézéquel, and Bernhard Rumpe

Published in: Dagstuhl Reports, Volume 4, Issue 10 (2015)


Abstract
This report documents the program and the outcomes of the Dagstuhl Seminar 14412 "Globalizing Domain-Specific Languages" held in October 2014. Complex, data-intensive, cyper-physical, cloud-based etc. systems need effective modeling techniques, preferably based on DSLs to describe aspects and views. Models written in heterogeneous languages however need to be semantically compatible and their supporting individual tools need to be interoperable. This workshop discusses possible and necessary forms of interoperation their benefits and drawbacks and in particular whether there is a general pattern on coordination, composition and interoperation possible. Main goal was to establish a research programme towards such techniques.

Cite as

Betty H. C. Cheng, Benoit Combemale, Robert B. France, Jean-Marc Jézéquel, and Bernhard Rumpe. Globalizing Domain-Specific Languages (Dagstuhl Seminar 14412). In Dagstuhl Reports, Volume 4, Issue 10, pp. 32-50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.4.10.32,
  author =	{Cheng, Betty H. C. and Combemale, Benoit and France, Robert B. and J\'{e}z\'{e}quel, Jean-Marc and Rumpe, Bernhard},
  title =	{{Globalizing Domain-Specific Languages (Dagstuhl Seminar 14412)}},
  pages =	{32--50},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{10},
  editor =	{Cheng, Betty H. C. and Combemale, Benoit and France, Robert B. and J\'{e}z\'{e}quel, Jean-Marc and Rumpe, Bernhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.10.32},
  URN =		{urn:nbn:de:0030-drops-48913},
  doi =		{10.4230/DagRep.4.10.32},
  annote =	{Keywords: Modelling, Domain Specific Language, Software, Coordination, Globalization, Heterogeneous Complex Systems, DSL, UML, Composition}
}
Document
09302 Abstracts Collection – New Developments in the Visualization and Processing of Tensor Fields

Authors: Bernhard Burgeth and David H. Laidlaw

Published in: Dagstuhl Seminar Proceedings, Volume 9302, New Developments in the Visualization and Processing of Tensor Fields (2009)


Abstract
From 19.07. to 24.07.2009, the Dagstuhl Seminar 09302 ``New Developments in the Visualization and Processing of Tensor Fields '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Bernhard Burgeth and David H. Laidlaw. 09302 Abstracts Collection – New Developments in the Visualization and Processing of Tensor Fields. In New Developments in the Visualization and Processing of Tensor Fields. Dagstuhl Seminar Proceedings, Volume 9302, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{burgeth_et_al:DagSemProc.09302.1,
  author =	{Burgeth, Bernhard and Laidlaw, David H.},
  title =	{{09302 Abstracts Collection – New Developments in the Visualization and Processing of Tensor Fields}},
  booktitle =	{New Developments in the Visualization and Processing of Tensor Fields},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9302},
  editor =	{Bernhard Burgeth and David H. Laidlaw},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09302.1},
  URN =		{urn:nbn:de:0030-drops-22381},
  doi =		{10.4230/DagSemProc.09302.1},
  annote =	{Keywords: Visualization, image processing, tensor fields, diffusion tensor imaging (DT-MRI), partial differential equations (PDEs), tensor decomposition, feature extraction, segmentation, fiber tracking, elastography, fluid dynamics, structural mechanics}
}
Document
09302 Summary – New Developments in the Visualization and Processing of Tensor Fields

Authors: Bernhard Burgeth and David H. Laidlaw

Published in: Dagstuhl Seminar Proceedings, Volume 9302, New Developments in the Visualization and Processing of Tensor Fields (2009)


Abstract
This Dagstuhl Seminar was concerned with the visualization and processing of tensor fields, like its two predecessors: seminar 04172 organized by Hans Hagen and Joachim Weickert in April 2004, and the follow-up seminar 07022 in January 2007 with David Laidlaw and Joachim Weickert as organizers. Both earlier meetings were successful, resulting in well received books and triggering fruitful scientific interaction and exchange of experience across interdisciplinary boundaries. We believe that the 2009 seminar will prove to have been equally successful.

Cite as

Bernhard Burgeth and David H. Laidlaw. 09302 Summary – New Developments in the Visualization and Processing of Tensor Fields. In New Developments in the Visualization and Processing of Tensor Fields. Dagstuhl Seminar Proceedings, Volume 9302, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{burgeth_et_al:DagSemProc.09302.2,
  author =	{Burgeth, Bernhard and Laidlaw, David H.},
  title =	{{09302 Summary – New Developments in the Visualization and Processing of Tensor Fields}},
  booktitle =	{New Developments in the Visualization and Processing of Tensor Fields},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9302},
  editor =	{Bernhard Burgeth and David H. Laidlaw},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09302.2},
  URN =		{urn:nbn:de:0030-drops-22378},
  doi =		{10.4230/DagSemProc.09302.2},
  annote =	{Keywords: Visualization, image processing, tensor fields, diffusion tensor imaging (DT-MRI), partial differential equations (PDEs), tensor decomposition, feature extraction, segmentation, fiber tracking, elastography, fluid dynamics, structural mechanics}
}
Document
Composing Personalised Services on top of Abstract State Services

Authors: Hui Ma, Klaus-Dieter Schewe, Bernhard Thalheim, and Qing Wang

Published in: Dagstuhl Seminar Proceedings, Volume 8181, The Evolution of Conceptual Modeling (2008)


Abstract
We introduce Abstract State Services (ASSs) as an abstraction of data-intensive services that can be made available for use by other systems, e.g. via the web. An ASS combines a hidden database layer with an operation-equipped view layer, and can be anything from a simple function to a full-fledged Web Information System or a Data Warehouse. We adopt the fundamental approach of Abstract State Machines to model ASSs. Then we show how tailored services can be extracted from available ASSs, integrated with other ASSs and personalised to user preferences.

Cite as

Hui Ma, Klaus-Dieter Schewe, Bernhard Thalheim, and Qing Wang. Composing Personalised Services on top of Abstract State Services. In The Evolution of Conceptual Modeling. Dagstuhl Seminar Proceedings, Volume 8181, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{ma_et_al:DagSemProc.08181.3,
  author =	{Ma, Hui and Schewe, Klaus-Dieter and Thalheim, Bernhard and Wang, Qing},
  title =	{{Composing Personalised Services on top of Abstract State Services}},
  booktitle =	{The Evolution of Conceptual Modeling},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8181},
  editor =	{Lois Delcambre and Roland H. Kaschek and Heinrich C. Mayr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08181.3},
  URN =		{urn:nbn:de:0030-drops-15975},
  doi =		{10.4230/DagSemProc.08181.3},
  annote =	{Keywords: Abstract State Machines, services, integration, composition}
}
Document
2. 08102 Working Group – Early Warning Systems

Authors: Joachim Biskup, Bernhard Hämmerli, Michael Meier, Sebastian Schmerl, Jens Tölle, and Michael Vogel

Published in: Dagstuhl Seminar Proceedings, Volume 8102, Perspectives Workshop: Network Attack Detection and Defense (2008)


Abstract
Early Warning Systems aim at detecting unclassified but potentially harmful sys-tem behavior based on preliminary indications and are complementary to Intrusion Detection Systems. Both kinds of systems try to detect, identify and react before pos-sible damage occurs and contribute to an integrated and aggregated situation report (big picture). A particular emphasis of Early Warning Systems is to establish hypotheses and predictions as well as to generate advises in still not completely understood situations. Thus the term early has two meanings, a) to start early in time aiming to minimize damage, and b) to process uncertain and incomplete information.

Cite as

Joachim Biskup, Bernhard Hämmerli, Michael Meier, Sebastian Schmerl, Jens Tölle, and Michael Vogel. 2. 08102 Working Group – Early Warning Systems. In Perspectives Workshop: Network Attack Detection and Defense. Dagstuhl Seminar Proceedings, Volume 8102, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{biskup_et_al:DagSemProc.08102.2,
  author =	{Biskup, Joachim and H\"{a}mmerli, Bernhard and Meier, Michael and Schmerl, Sebastian and T\"{o}lle, Jens and Vogel, Michael},
  title =	{{2. 08102 Working Group – Early Warning Systems}},
  booktitle =	{Perspectives Workshop: Network Attack Detection and Defense},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8102},
  editor =	{Georg Carle and Falko Dressler and Richard A. Kemmerer and Hartmut K\"{o}nig and Christopher Kruegel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08102.2},
  URN =		{urn:nbn:de:0030-drops-14936},
  doi =		{10.4230/DagSemProc.08102.2},
  annote =	{Keywords: Intrusion detection and prevention, attack response and countermeasures, reactive security, automated security, survivability and self-protection, ma network monitoring, flow analysis, denial of service detection and response, event correlation}
}
Document
Path planning and optimization in the traveling salesman problem: Nearest neighbor vs. region-based strategies

Authors: Jan Malte Wiener, Nicole N. Ehbauer, and H. A. Mallot

Published in: Dagstuhl Seminar Proceedings, Volume 5491, Spatial Cognition: Specialization and Integration (2007)


Abstract
According to the number of targets, route planning can be a very complex task. Human navigators, however, usually solve route planning tasks fastly and efficiently. Here two experiments are presented that studied human route planning performance, route planning strategies employed, and cognitive processes involved. For this, 25 places were arranged on a regular grid in a large room. Each place was marked by a unique symbol. Subjects were repeatedly asked to solve traveling salesman problems (TSP), i.e. to find the shortest closed loop connecting a given start place with a number of target places. For this, subjects were given a so-called 'shopping list' depicting the symbols of the start place and the target places. While the TSP is computationally hard, sufficient solutions can be found by simple strategies such as the nearest neighbor strategy. In Experiment 1, it was tested whether humans deployed the nearest neighbor strategy (NNS) when solving the TSP. Results showed that subjects outperformed the NNS in cases in which the NNS did not predict the optimal solution, suggesting that the NNS is not sufficient to explain human route planning behavior. As a second possible strategy a region-based approach was tested in Experiment 2. When optimal routes required more region transitions than other, sub-optimal routes, subjects preferred these sub-optimal routes. This result suggests that subjects first planned a coarse route on the region level and then refined the route during navigation. Such a hierarchical planning stragey would allow to reduce computational effort during route planning. In a control condition, the target places were directly marked in the environment rather than being depicted on the shopping list. As subjects did not have to identify and remember the positions of the target places based on the shopping list during route planning, this control condition tested for the influence of spatial working memory for route planning performance. Results showed a strong performance increase in the control condition, emphasizing the prominent role of spatial working memory for route planning.

Cite as

Jan Malte Wiener, Nicole N. Ehbauer, and H. A. Mallot. Path planning and optimization in the traveling salesman problem: Nearest neighbor vs. region-based strategies. In Spatial Cognition: Specialization and Integration. Dagstuhl Seminar Proceedings, Volume 5491, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{wiener_et_al:DagSemProc.05491.7,
  author =	{Wiener, Jan Malte and Ehbauer, Nicole N. and Mallot, H. A.},
  title =	{{Path planning and optimization in the traveling salesman problem: Nearest neighbor vs. region-based strategies}},
  booktitle =	{Spatial Cognition: Specialization and Integration},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{5491},
  editor =	{Anthony G. Cohn and Christian Freksa and Bernhard Nebel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05491.7},
  URN =		{urn:nbn:de:0030-drops-9848},
  doi =		{10.4230/DagSemProc.05491.7},
  annote =	{Keywords: Spatial cognition, navigation, route planning, path complexity, traveling salesman problem, regions, hierarchical planning, nearest neighbor strategy}
}
Document
Media Distribution in a Pervasive Computing Environment

Authors: Alexander Sinitsyn, Winfried A. H. Berkvens, Arjan Claassen, and Joep P. van Gassel

Published in: Dagstuhl Seminar Proceedings, Volume 5421, Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data (2006)


Abstract
Distribution of media in the fast growing world of digital stored content and multimedia supporting devices with connectivity, calls for a new media distribution architecture. The user should be provided with the experience of having an overview of his full media collection, regardless of the time, the place, and the connectivity. Transparent distributed data management is crucial to Ambient Intelligent applications. The proposed media distribution architecture offers a possible solution. It provides the user with the experience of having all his media collections available at any time, in any place, and managing them regardless of connection availability in the heterogeneous environment. This experience is enabled in our system by the separation of metadata and content handling. Other features are efficient handling of snapshots, usage of various database technologies, and leveraging device and service discovery mechanisms.

Cite as

Alexander Sinitsyn, Winfried A. H. Berkvens, Arjan Claassen, and Joep P. van Gassel. Media Distribution in a Pervasive Computing Environment. In Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data. Dagstuhl Seminar Proceedings, Volume 5421, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{sinitsyn_et_al:DagSemProc.05421.4,
  author =	{Sinitsyn, Alexander and Berkvens, Winfried A. H. and Claassen, Arjan and van Gassel, Joep P.},
  title =	{{Media Distribution in a Pervasive Computing Environment}},
  booktitle =	{Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5421},
  editor =	{Gustavo Alonso and Christian S. Jensen and Bernhard Mitschang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05421.4},
  URN =		{urn:nbn:de:0030-drops-7622},
  doi =		{10.4230/DagSemProc.05421.4},
  annote =	{Keywords: Data management}
}
Document
Semantics in Databases (Dagstuhl Seminar 01021)

Authors: Leopoldo Bertossi, Gyula O. H. Katona, Klaus-Dieter Schewe, and Bernhard Thalheim

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Leopoldo Bertossi, Gyula O. H. Katona, Klaus-Dieter Schewe, and Bernhard Thalheim. Semantics in Databases (Dagstuhl Seminar 01021). Dagstuhl Seminar Report 295, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)


Copy BibTex To Clipboard

@TechReport{bertossi_et_al:DagSemRep.295,
  author =	{Bertossi, Leopoldo and Katona, Gyula O. H. and Schewe, Klaus-Dieter and Thalheim, Bernhard},
  title =	{{Semantics in Databases (Dagstuhl Seminar 01021)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{295},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.295},
  URN =		{urn:nbn:de:0030-drops-151795},
  doi =		{10.4230/DagSemRep.295},
}
  • Refine by Author
  • 2 Burgeth, Bernhard
  • 2 Laidlaw, David H.
  • 2 Schewe, Klaus-Dieter
  • 2 Thalheim, Bernhard
  • 1 Berkvens, Winfried A. H.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 2 Visualization
  • 2 diffusion tensor imaging (DT-MRI)
  • 2 elastography
  • 2 feature extraction
  • 2 fiber tracking
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 2 2008
  • 2 2009
  • 1 2001
  • 1 2006
  • 1 2007
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail