TU Berlin

Internet Network ArchitecturesDistributed Systems

Page Content

to Navigation

Distributed Systems

Almost every computing system nowadays is distributed, ranging from multi-core laptops to Internet-scale services; understanding the principles of distributed computing is hence important for the design and engineering of modern computing systems.  Fundamental issues that arise in reliable and efficient distributed systems include developing adequate methods for modeling failures and synchrony assumptions, determining precise performance bounds on implementations of concurrent data structures, capturing the trade-off between consistency and efficiency, and demarcating the frontier of feasibility in distributed computing.

For example, popular Internet services and applications such as CNN.com, YouTube, Facebook, Skype, BitTorrent attract millions of users every day, and only by the effective load-balancing and collaboration of many thousand machines, an acceptable Quality-of-Service/Quality-of-Experience can be guaranteed. While distributed systems promise a good scalability as well as a high robustness, they pose challenging research problems, such as: How to design robust and scalable distributed architectures and services? How to coordinate access to a shared resource, e.g., by electing a leader? Or how to provide incentives for cooperation in an open, collaborative distributed system?

Selected Publications

Tight Bounds for Delay-Sensitive Aggregation
Citation key PSW-TBDSA-10
Author Pignolet, Yvonne Anne and Schmid, Stefan and Wattenhofer, Roger
Pages 39–58
Year 2010
ISSN 1365-8050
Journal Discrete Mathematics and Theoretical Computer Science Journal
Volume 12
Number 1
Month February
Abstract This article studies the fundamental trade-off between delay and communication cost in networks. We consider an online optimization problem where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about the changes of their states and to use as few transmissions as possible. We derive an upper bound on the competitive ratio of O(min(h,c)) where h is the tree's height, and c is the transmission cost per edge. Moreover, we prove that this upper bound is tight in the sense that any oblivious algorithm has a ratio of at least Ω(min(h,c)). For chain networks, we prove a tight competitive ratio of Θ(min(radic(h),c)). Furthermore, we introduce a model for value-sensitive aggregation, where the cost depends on the number of transmissions and the error at the root.
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe