Gradient Clock Synchronization in Wireless Sensor Networks (2009)
Accurately synchronized clocks are crucial for many applications in sensor networks. Existing time synchronization algorithms provide on average good synchronization between arbitrary nodes, however,...
Algorithms for Sensor and Ad-Hoc Networks Distributed Computing Group (2009)
– Ad-Hoc and Sensor Networks
On the topologies formed by selfish peers (2009)
Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer
Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem....
Differential Code Updates in Wireless Sensor Networks (2009)
Pascal Von Rickenbach, Roger Wattenhofer
Abstract. Wireless sensor networks come of age and start moving out of the laboratory into the field. As the number of deployments is increasing the need for an efficient and reliable code update...
On the topologies formed by selfish peers (2009)
Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer
Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem....
Fabian Kuhn, Stefan Schmid, Joest Smit, Roger Wattenhofer
Abstract — Until now, the analysis of fault tolerance of peerto-peer systems usually only covers random faults of some kind. Contrary to traditional algorithmic research, faults as well as joins...
Capacity of Arbitrary Wireless Networks (2009)
Olga Goussevskaia, Magnús M. Halldórsson, Roger Wattenhofer, Emo Welzl
Abstract — In this work we study the problem of determining the throughput capacity of a wireless network. We propose a scheduling algorithm to achieve this capacity within an approximation factor....
Robust and Energy-Efficient Environmental Monitoring using Wireless Sensor Networks (2009)
Nicolas Burri, Pascal Von Rickenbach, Roger Wattenhofer
Long-term surveillance of environmental conditions is a prevalent application for wireless sensor networks. To guarantee persistent network operation over a period of several years a highly...
Local Broadcasting in the Physical Interference Model (2009)
Olga Goussevskaia, Thomas Moscibroda, Roger Wattenhofer
In this work we analyze the complexity of local broadcasting in the physical interference model. We present two distributed randomized algorithms: one that assumes that each node knows how many nodes...
Greedy Routing with Bounded Stretch (2009)
Roland Flury, Sriram V. Pemmaraju, Roger Wattenhofer
Abstract—Greedy routing is a novel routing paradigm where messages are always forwarded to the neighbor that is closest to the destination. Our main result is a polynomial-time algorithm that...
Clock Synchronization with Bounded Global and Local Skew* (2009)
Christoph Lenzen, Thomas Locher, Roger Wattenhofer
Abstract We present a distributed clock synchronization algorithm that guarantees an exponen-tially improved bound of O(log D) on the clock skew between neighboring nodes in anygraph G of diameter D....
ABSTRACT On the Windfall of Friendship: Inoculation Strategies on Social Networks (2009)
Dominic Meier, Yvonne Anne Oswald, Stefan Schmid, Roger Wattenhofer
This paper studies a virus inoculation game on social networks. A framework is presented which allows the measuring of the windfall of friendship, i.e., how much players benefit if they care about...
Word of Mouth: Rumor Dissemination in Social Networks (2009)
Jan Kostka, Yvonne Anne Oswald, Roger Wattenhofer
Abstract. In this paper we examine the diffusion of competing rumors in social networks. Two players select a disjoint subset of nodes as initiators of the rumor propagation, seeking to maximize the...
Clock Synchronization with Bounded Global and Local Skew ∗ (2009)
Christoph Lenzen, Thomas Locher, Roger Wattenhofer
We present a distributed clock synchronization algorithm that guarantees an exponentially improved bound of O(log D) on the clock skew between neighboring nodes in any graph G of diameter D. In light...
The Layered World of Scientific Conferences (2009)
Michael Kuhn, Roger Wattenhofer
Abstract. Recent models have introduced the notion of dimensions and hierarchies in social networks. These models motivate the mining of small world graphs under a new perspective. We exemplary base...
Stefan Schmid, Hedingen Zh, Prof Dr, Roger Wattenhofer, Eth Zurich
born 31.07.1978 citizen of
Distributed Disaster Disclosure (2009)
Bernard Mans, Roger Wattenhofer
Abstract. Assume a set of distributed nodes which are equipped with a sensor device. When nodes sense an event, they want to know (the size of) the connected component consisting of nodes which have...
VENETA: Serverless Friend-of-Friend Detection in Mobile Social Networking (2009)
Marco Von Arb, Matthias Bader, Michael Kuhn, Roger Wattenhofer
Abstract—Recently, mobile social software has become an active area of research and development. A multitude of systems have been proposed over the past years that try to follow the success of...
Decoding Code on a Sensor Node (2009)
Pascal Von Rickenbach, Roger Wattenhofer
Abstract. Wireless sensor networks come of age and start moving out of the laboratory into the field. As the number of deployments is increasing the need for an efficient and reliable code update...
Leveraging Linial’s Locality Limit (2009)
Christoph Lenzen, Roger Wattenhofer
www.dcg.ethz.ch Abstract. In this paper we extend the lower bound technique by Linial for local coloring and maximal independent sets. We show that constant approximations to maximum independent sets...
Lukas Füllemann, Supervisors Prof, Dr. Roger Wattenhofer, Stefan Schmid
2.1 Asymmetric Network Connections....................................................................................... 3
Categories and Subject Descriptors (2008)
Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger
All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we...
Nonnumerical Algorithms and Problems—geometrical (2008)
Martin Burkhart, Pascal Von Rickenbach, Roger Wattenhofer, Aaron Zollinger
Topology control in ad-hoc networks tries to lower node energy consumption by reducing transmission power and by confining interference, collisions and consequently retransmissions. Commonly low...
Maximal Independent Sets in Radio Networks (2008)
Thomas Moscibroda, Roger Wattenhofer
We study the distributed complexity of computing a maximal independent set (MIS) in radio networks with completely unknown topology, asynchronous wake-up, and no collision detection mechanism...
DIPLOMA THESIS Dynamic & Fault-Tolerant P2P-Topologies Distributed Computing Group (2008)
Stefan Schmid, Prof Dr, Roger Wattenhofer, Fabian Kuhn
Until now, the analysis of fault tolerance of peer-to-peer (p2p) systems usually only covers random faults of some kind. Contrary to traditional algorithmic research, faults as well as joins and...
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
In this paper we study a model for ad-hoc networks close enough to reality as to represent existing networks, being at the same time concise enough to promote strong theoretical results. The Quasi...
458 Abstract Randomized Greedy Hot-Potato Routing (2008)
Costas Busch, Maurice Herlihy, Roger Wattenhofer
We present a novel greedy hot-potato routing algorithm for the 2-dimensional n × n mesh or torus. This algorithm uses randomization to adjust packet priorities. For any permuta-tion problem or...
Dynamic Analysis of the Arrow Distributed Protocol (2008)
Maurice Herlihy, Fabian Kuhn, Srikanta Tirthapura, Roger Wattenhofer
Distributed queuing is a fundamental coordination problem that arises in a variety of applications, including distributed directories, totally ordered multicast, and distributed mutual exclusion. The...
Baptiste Prêtre, Prof Dr, Roger Wattenhofer, Advisors Stefan Schmid
In this thesis, we collect information about known attacks on P2P networks. We try to classify them as well as study the different possible defense mechanisms. As a case study, we take Freenet, a...
A Cone-Based Distributed Topology-Control Algorithm for Wireless Multi-Hop Networks (2008)
Paramvir Bahl, Yi-min Wang, Roger Wattenhofer
Abstract — The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed...
Distributed Computing Group (2008)
Thomas Locher, Prof Dr, Roger Wattenhofer, Advisor Stefan Schmid
Peer-to-peer systems (p2p) are highly dynamic in nature and the topology of these networks changes rapidly. Such a system may consist of millions of peers joining only for a limited period of time,...
Distributed Computing Group (2008)
Philip Frey, Prof Dr, Roger Wattenhofer, Advisors Stefan Schmid, Thomas Locher
Today’s Internet connections are getting faster and faster. Therefore it has become possible to use the Internet not only for conventional content such as websites but also for live media streams...
ABSTRACT On the Topologies Formed by Selfish Peers (2008)
Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer
Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem....
General Terms Algorithms, Theory (2008)
Fabian Kuhn, Roger Wattenhofer
Arrow is a prominent distributed protocol which globally orders requests initiated by the nodes in a distributed system. In this paper we present a dynamic analysis of the Arrow protocol. We prove...
Fast and Simple Algorithms for Weighted Perfect Matching (2008)
Mirjam Wattenhofer, Roger Wattenhofer
We present two fast and simple combinatorial approximation algorithms for constructing a minimum-weighted perfect matching on complete graphs whose cost functions satisfy the triangle inequality. The...
Efficient Adaptive Collect using Randomization \Lambda (2008)
Hagit Attiya, Roger Wattenhofer
Abstract An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractivefor distributed systems with a highly-variable number of processes. The cornerstone of...
BEATCS no 90 THE EATCS COLUMNS (2008)
Mario Mavronicolas, James Aspnes, Shlomi Dolev, Chryssis Georgiou, Costas Busch, Panagiota Fatourou, ...
Distributed Computing Theory continues to be one of the most active research fields in Theoretical Computer Science today. Besides its foundational topics (such as consensus and synchronization), it...
Structuring Unstructured Peer-to-Peer Networks (2008)
Stefan Schmid, Roger Wattenhofer
Abstract. Flooding is a fundamental building block of unstructured peer-to-peer (P2P) systems. In this paper, we investigate techniques to improve the performance of flooding. In particular, we...
ABSTRACT Efficient Multi-Word Locking Using Randomization (2008)
Phuong Hoai Ha, Mirjam Wattenhofer, Roger Wattenhofer
In this paper we examine the general multi-word lock problem, where processes are allowed to multilock arbitrary registers. Aiming for a highly efficient solution we propose a randomized algorithm...
Received-Signal-Strength-Based Logical Positioning Resilient to Signal Fluctuation (2008)
Thomas Locher, Roger Wattenhofer, Aaron Zollinger
Positioning based on received signal strengths from base stations is highly sensitive to the effects of signal attenuation, reflection, and scattering. Moreover, experimental measurements show that...
Rescuing tit-for-tat with source coding (2008)
Thomas Locher, Stefan Schmid, Roger Wattenhofer
Tit-for-tat is widely believed to be the most effective strategy to enforce collaboration among selfish users. However, it has been shown that its usefulness for decentralized and dynamic...
Nonnumerical Algorithms and Problems—geometrical (2008)
Martin Burkhart, Pascal Von Rickenbach, Roger Wattenhofer, Aaron Zollinger
Topology control in ad-hoc networks tries to lower node energy consumption by reducing transmission power and by confining interference, collisions and consequently retransmissions. Commonly low...
Topology Control Made Practical: Increasing the Performance of Source Routing ⋆ (2008)
Nicolas Burri, Pascal Von Rickenbach, Roger Wattenhofer, Yves Weber
Abstract. Wireless ad hoc and sensor networks need to deal with unstable links. In practice the link quality between neighboring nodes fluctuates significantly over time. In this paper we evaluate...
Fast and Simple Algorithms for Weighted Perfect Matching (2008)
Mirjam Wattenhofer, Roger Wattenhofer
We present two fast and simple combinatorial approximation algorithms for constructing a minimum-weighted perfect matching on complete graphs whose cost functions satisfy the triangle inequality. The...
Nonnumerical Algorithms and Problems—geometrical (2008)
Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger
All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we...
Push-to-Pull Peer-to-Peer Live Streaming (2008)
Thomas Locher, Remo Meier, Stefan Schmid, Roger Wattenhofer
Abstract. In contrast to peer-to-peer file sharing, live streaming based on peer-to-peer technology is still awaiting its breakthrough. This may be due to the additional challenges live streaming...
ABSTRACT Efficient Multi-Word Locking Using Randomization (2008)
Phuong Hoai Ha, Mirjam Wattenhofer, Roger Wattenhofer
In this paper we examine the general multi-word lock problem, where processes are allowed to multilock arbitrary registers. Aiming for a highly efficient solution we propose a randomized algorithm...
Abstract The Price of Being Near-Sighted (2008)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
Achieving a global goal based on local information is challenging, especially in complex and large-scale networks such as the Internet or even the human brain. In this paper, we provide an almost...
Manipulation in Games ⋆ (2008)
Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid, Roger Wattenhofer
Abstract. This paper studies to which extent the social welfare of a game can be influenced by an interested third party within economic reason, i.e., by taking the implementation cost into account....
Abstract Towards a Theory of Peer-to-Peer Computability (2008)
Joachim Giesen, Roger Wattenhofer, Aaron Zollinger
A peer-to-peer system is a distributed system with no physical or logical central authority. We give a formal model of a peer-to-peer system where agents communicate through read-modify-write...
Fabian Kuhn, Roger Wattenhofer
Abstract. Finding a small dominating set is one of the most fundamental problems of classical graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP...
ABSTRACT Efficient Multi-Word Locking Using Randomization (2008)
Phuong Hoai Ha, Mirjam Wattenhofer, Roger Wattenhofer
In this paper we examine the general multi-word lock problem, where processes are allowed to multilock arbitrary registers. Aiming for a highly efficient solution we propose a randomized algorithm...
Manipulation in Games ⋆ (2008)
Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid, Roger Wattenhofer
Abstract. This paper studies to which extent the social welfare of a game can be influenced by an interested third party within economic reason, i.e., by taking the implementation cost into account....
ABSTRACT MLS: An Efficient Location Service (2008)
MLS is a distributed location service to track the position of mobile nodes and to route messages between any two nodes. The lookup of nodes is achieved by searching in a hierarchy of pointers that...
DISS. ETH NO. 16800 Understanding Ad hoc Networks From Geometry to Mobility (2008)
Dipl Inf. -ing, Eth Zürich, Prof Dr, Roger Wattenhofer, Prof Dr, Rajmohan Rajaraman, ...
born 26.04.1980
Nonnumerical Algorithms and Problems—geometrical (2008)
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
In this paper we study a model for ad-hoc networks close enough to reality as to represent existing networks, being at the same time concise enough to promote strong theoretical results. The Quasi...
SANS: A Simple Ad Hoc Network Simulator (2008)
Nicolas Burri, Roger Wattenhofer, Yves Weber, Aaron Zollinger
Does Topology, Control Reduce, Interference? Martin Burkhart, Pascal Von Rickenbach, Roger Wattenhofer, ...
ABSTRACT Topology control in ad-hoc networks tries to lower node energy consumption by reducing transmission power and by confining interference, collisions and consequently retransmissions. Commonly...
Nonnumerical Algorithms and Problems—geometrical (2008)
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
In this paper we study a model for ad-hoc networks close enough to reality as to represent existing networks, being at the same time concise enough to promote strong theoretical results. The Quasi...
Towards Decentralized Distributed Data Structures (2008)
Roger Wattenhofer, Peter Widmayer
We motivate and present a simple measure of efficiency for distributed data structures called "bottleneck complexity". We investigate a distributed counter as a case study for our measure...
Fast and Simple Algorithms for Weighted Perfect Matching (2008)
Mirjam Wattenhofer, Roger Wattenhofer
We present two fast and simple combinatorial approximation algorithms for constructing a minimum-weighted perfect matching on complete graphs whose cost functions satisfy the triangle inequality. The...
Sensor networks continue to puzzle: Selected open problems (2008)
Thomas Locher, Pascal Von Rickenbach, Roger Wattenhofer
Abstract. While several important problems in the field of sensor networks have already been tackled, there is still a wide range of challenging, open problems that merit further attention. We...
Sensor networks continue to puzzle: Selected open problems (2008)
Thomas Locher, Pascal Von Rickenbach, Roger Wattenhofer
Abstract. While several important problems in the field of sensor networks have already been tackled, there is still a wide range of challenging, open problems that merit further attention. We...
Symmetric Clock Synchronization in Sensor Networks (2008)
Philipp Sommer, Roger Wattenhofer
In this paper we argue that achieving symmetric errors is the key to an improved understanding of clock synchronization. We present a clock synchronization algorithm with drift compensation that...
Sensor networks continue to puzzle: Selected open problems (2008)
Thomas Locher, Pascal Von Rickenbach, Roger Wattenhofer
Abstract. While several important problems in the field of sensor networks have already been tackled, there is still a wide range of challenging, open problems that merit further attention. We...
Fast Counting with the Optimum Combining Tree (2007)
Roger Wattenhofer, Peter Widmayer
A distributed counter is a concurrent object which provides a test-and-incrementoperation on a shared value. On the basis of a distributed counter, one can implement various fundamental data...
Distributed Combinatorial Optimization-- Extended Abstract (2007)
Fabian Kuhn, Roger Wattenhofer
Approximating integer linear programs by solving a relaxation to a linear program (LP) and afterwards reconstructing an integer solution from the fractional one is a standard technique in a...
1 Resilience Characteristics of the Internet Backbone Routing Infrastructure (2007)
Craig Labovitz, Roger Wattenhofer, Srinivasan Venkatachary, Abha Ahuja
It is widely believed that the Internet is a highly faulttolerant, survivable network. In particular, the Internet is attributed with the ability to route packets around faults quickly, in a matter...
Costas Busch, Maurice Herlihy, Roger Wattenhofer
We present the rst hot-potato routing algorithm for the n n mesh whose running time on any \hard" (i.e., n)) \many-to-one " batch routing problem is, with high probability, within a...
Roger Wattenhofer, Li Li, Paramvir Bahl, Yi-min Wang
Abstract--- The topology of wireless multihop ad hoc networks can be controlled by varying the transmission power of each node. We propose a simple distributed algorithm where each node makes local...
Ordered Multicast and Distributed Swap preliminary report (2007)
Maurice Herlihy, Srikanta Tirthapura, Roger Wattenhofer
A multicast protocol is ordered (or totally ordered) if it ensures that messages multicast to a group of nodes are delivered in the same order at each destination node, even when those messages are...
Craig Labovitz, Ahba Ahuja, Roger Wattenhofer, Srinivasan Venkatachary
This paper examines the role inter-domain topology and routing policy play in the process of delayed Internet routing convergence. In recent work, we showed that the Internet lacks effective...
1.1 Correlated Data Gathering (2007)
Răzvan Cristescu, Baltasar Beferull-lozano, Martin Vetterli, Roger Wattenhofer
We consider the problem of correlated data gathering by a network with a sink node and a tree based communication structure, where the goal is to minimize the total transmission cost of transporting...
Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger
All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we...
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
In this paper we study a model for ad-hoc networks close enough to reality as to represent existing networks, being at the same time concise enough to promote strong theoretical results. The Quasi...
Costas Busch, Maurice Herlihy, Roger Wattenhofer
We present the rst hot-potato routing algorithm for the n n mesh whose running time on any \hard" (i.e., n)) \many-to-one " batch routing problem is, with high probability, within a...
]: Nonnumerical Algorithms and Problems---geometrical (2007)
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
In this paper we present GOAFR, a new geometric ad-hoc routing algorithm combining greedy and face routing. We evaluate this algorithm by both rigorous analysis and comprehensive simulation. GOAFR is...
Craig Labovitz, Ahba Ahuja, Roger Wattenhofer, Srinivasan Venkatachary
This paper examines the role inter-domain topology and routing policy play in the process of delayed Internet routing convergence. In recent work, we showed that the Internet lacks effective...
Regina Bischoff, Roger Wattenhofer
We investigate the theoretical limits of positioning algorithms. In particular, we study scenarios where the nodes do not receive anchors directly (multi-hop) and where no physical distance or angle...
Roger Wattenhofer, Li Li, Paramvir Bahl, Yi-min Wang
Abstract--- The topology of wireless multihop ad hoc networks can be controlled by varying the transmission power of each node. We propose a simple distributed algorithm where each node makes local...
Costas Busch, Maurice Herlihy, Roger Wattenhofer
We present the rst dynamic hot-potato routing algorithm that does not require any form of explicit ow control: a node may inject a message into the network (n n mesh) whenever a link is free. In the...
Fabian Kuhn, Roger Wattenhofer
Arrow is a prominent distributed protocol which globally orders requests initiated by the nodes in a distributed system. In this paper we present a dynamic analysis of the Arrow protocol. We prove...
How Optimal are Wireless Scheduling Protocols? (2007)
Thomas Moscibroda, Yvonne Anne Oswald, Roger Wattenhofer
In wireless networks mutual interference impairs the quality of received signals and might even prevent the correct reception of messages. It is therefore of paramount importance to dispose of power...
R.: Mechanism Design by Creditability (2007)
Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid, Roger Wattenhofer
Abstract. This paper attends to the problem of a mechanism designer seeking to influence the outcome of a strategic game based on her creditability. The mechanism designer offers additional payments...
R.: Mechanism Design by Creditability (2007)
Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid, Roger Wattenhofer
Abstract. This paper attends to the problem of a mechanism designer seeking to influence the outcome of a strategic game based on her creditability. The mechanism designer offers additional payments...
07151 Abstracts Collection -- Geometry in Sensor Networks (2007)
Suri, Subhash, Wattenhofer, Roger, Widmayer, Peter
From 9.4.2007 to 13.4.07, the Dagstuhl Seminar 07151 ``Geometry in Sensor Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several...
R.: Mechanism Design by Creditability (2007)
Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid, Roger Wattenhofer
Abstract. This paper attends to the problem of a mechanism designer seeking to influence the outcome of a strategic game based on her creditability. The mechanism designer offers additional payments...
R.: Mechanism Design by Creditability (2007)
Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid, Roger Wattenhofer
Abstract. This paper attends to the problem of a mechanism designer seeking to influence the outcome of a strategic game based on her creditability. The mechanism designer offers additional payments...
R.: How Optimal are Wireless Scheduling Protocols (2007)
Thomas Moscibroda, Yvonne Anne Oswald, Roger Wattenhofer
Abstract — In wireless networks mutual interference impairs the quality of received signals and might even prevent the correct reception of messages. It is therefore of paramount importance to...
Olga Goussevskaia, Roger Wattenhofer, Thomas Moscibroda
In this work we analyze the complexity of local broadcasting in the physical interference model. We present two distributed randomized algorithms: one that assumes that each node knows how many nodes...
Network correlated data gathering with explicit communication: NP-completeness and algorithms (2006)
Cristescu, Răzvan, Beferull-Lozano, Baltasar, Vetterli, Martin, Wattenhofer, Roger
We consider the problem of correlated data gathering by a network with a sink node and a tree-based communication structure, where the goal is to minimize the total transmission cost of transporting...
Free Riding in BitTorrent is Cheap (2006)
Thomas Locher, Patrick Moor, Stefan Schmid, Roger Wattenhofer
While it is well-known that BitTorrent is vulnerable to selfish behavior, this paper demonstrates that even entire files can be downloaded without reciprocating at all in BitTorrent. To this end, we...
(Revised) Distributed Computing Group (2006)
Gabor Cselle, Prof Dr, Roger Wattenhofer, Dr. Keno Albrecht, Copyright Gabor Cselle, Distributed Computing Group, ...
Email clients were not designed to handle the volume and variety of messages users are dealing with today. While this problem, termed “email overload, ” is widely acknowledged, there exist only...
On the Topologies Formed by Selfish Peers (2006)
Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer
Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem....
Havelaar: A Robust and Efficient Reputation System for Active Peer-to-Peer Systems (2006)
Dominik Grolimund, Luzius Meisser, Stefan Schmid, Roger Wattenhofer
Abstract — Peer-to-peer (p2p) systems have the potential to harness huge amounts of resources. Unfortunately, however, it has been shown that most of today’s p2p networks suffer from a large...
Oblivious Gradient Clock Synchronization (2006)
Thomas Locher, Roger Wattenhofer
Abstract. We study the gradient clock synchronization (GCS) problem, in which the worst-case clock skew between neighboring nodes has to be minimized. In particular, we consider oblivious clock...
Roland Schuler, Roger Wattenhofer, Short Tinyos Introduction, Nicolas Burri Realwsn, Interface I, Component B
• TinyOS consists of a scheduler & graph of components
Algorithmic Models for Sensor Networks (2006)
Stefan Schmid, Roger Wattenhofer
Developing algorithms for sensor networks—and proving their correctness and performance—, requires simplifying but still realistic models. This paper surveys various models in use today and puts...
Sensor Networks: Distributed Algorithms Reloaded - Or Revolutions (2006)
Abstract. This paper wants to motivate the distributed algorithms community to study sensor networks. We discuss why sensor networks are distributed algorithms, and why they are not. 1
Analyzing the Energy-Latency Trade-off during the Deployment of Sensor Networks (2006)
Thomas Moscibroda, Pascal Von Rickenbach, Roger Wattenhofer
Abstract — The inherent trade-off between energy-efficiency and rapidity of event dissemination is characteristic for wireless sensor networks. Scarcity of energy renders it necessary for nodes to...
Oblivious Gradient Clock Synchronization (2006)
Thomas Locher, Roger Wattenhofer
Abstract. We study the gradient clock synchronization (GCS) problem, in which the worst-case clock skew between neighboring nodes has to be minimized. In particular, we consider oblivious clock...
Community-Aware Mobile Networking (2006)
Michael Kuhn, Roger Wattenhofer
Community related applications such as dating platforms, instant messengers, or file-sharing tools enjoy a great popularity in the Internet. Motivated by this success, community-awareness also has...
equus: A provably robust and locality-aware peer-to-peer system (2006)
Thomas Locher, Stefan Schmid, Roger Wattenhofer
Peer-to-peer systems (p2p) are highly dynamic in nature. They may consist of millions of peers joining only for a limited period of time, resulting in hundreds of join and leave events per second. In...
Dynamic Internet Congestion with Bursts (2006)
Stefan Schmid, Roger Wattenhofer
Abstract. This paper studies throughput maximization in networks with dynamically changing congestion. First, we give a new and simple analysis of an existing model where the bandwidth available to a...
Cryptree: A folder tree structure for cryptographic file systems (2006)
Dominik Grolimund, Luzius Meisser, Stefan Schmid, Roger Wattenhofer
We present Cryptree, a cryptographic tree structure which facilitates access control in file systems operating on untrusted storage. Cryptree leverages the file system’s folder hierarchy to achieve...
Free Riding in BitTorrent is Cheap (2006)
Thomas Locher, Patrick Moor, Stefan Schmid, Roger Wattenhofer
While it is well-known that BitTorrent is vulnerable to selfish behavior, this paper demonstrates that even entire files can be downloaded without reciprocating at all in BitTorrent. To this end, we...
Analyzing the Energy-Latency Trade-off during the Deployment of Sensor Networks (2006)
Thomas Moscibroda, Pascal Von Rickenbach, Roger Wattenhofer
Abstract — The inherent trade-off between energy-efficiency and rapidity of event dissemination is characteristic for wireless sensor networks. Scarcity of energy renders it necessary for nodes to...
citizen of Germany accepted on the recommendation of (2006)
Prof Dr, Roger Wattenhofer, Prof Dr, Gordon V. Cormack, Prof Dr, Christof Fetzer
Email is undoubtedly one of the most important applications used to communicate over the Internet. Unfortunately, the email service lacks a crucial security mechanism: It is possible to send emails...
Dipl Inf. -ing, Eth Zürich, Malters Lu, Prof Dr, Roger Wattenhofer, Prof Dr, ...
born 11.09.1979 citizen of
Distributed Computing Group (2006)
Gabor Cselle, Prof Dr, Roger Wattenhofer, Dr. Keno Albrecht, Copyright Gabor Cselle, Distributed Computing Group, ...
Email clients were not designed to handle the volume and variety of messages users are dealing with today. While this problem, termed “email overload, ” is widely acknowledged, there exist only...
Havelaar: A Robust and Efficient Reputation System for Active Peer-to-Peer Systems (2006)
Dominik Grolimund, Luzius Meisser, Stefan Schmid, Roger Wattenhofer
Abstract — Peer-to-peer (p2p) systems have the potential to harness huge amounts of resources. Unfortunately, however, it has been shown that most of today’s p2p networks suffer from a large...
On the Topologies Formed by Selfish Peers (2006)
Schmid, Stefan, Moscibroda, Thomas, Wattenhofer, Roger
Many P2P systems are only proven efficient for static environments. However, in practice, P2P systems are often very dynamic in the sense that peers can join and leave a system at any time and...
Taming Dynamic and Selfish Peers (2006)
Schmid, Stefan, Kuhn, Fabian, Moscibroda, Thomas, Wattenhofer, Roger
Peer-to-peer systems are often faced with the problem of frequent membership changes. However, many systems are only proven efficient or correct in static environments. In my talk, I will present...
The price of being near-sighted (2006)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
Achieving a global goal based on local information is challenging, especially in complex and large-scale networks such as the Internet or even the human brain. In this paper, we provide an almost...
Development, Deployment, and Rating of Plug-Ins Technical Report TIK-259 (2006)
Keno Albrecht, Roger Wattenhofer
In this paper, we present a lightweight but powerful plug-in container which provides advanced features such as dynamic class loading, dependency, configuration, and security management. We highlight...
Havelaar: A Robust and Efficient Reputation System for Active Peer-to-Peer Systems (2006)
Dominik Grolimund, Luzius Meisser, Stefan Schmid, Roger Wattenhofer
Abstract — Peer-to-peer (p2p) systems have the potential to harness huge amounts of resources. Unfortunately, however, it has been shown that most of today’s p2p networks suffer from a large...
Havelaar: A Robust and Efficient Reputation System for Active Peer-to-Peer Systems (2006)
Dominik Grolimund, Luzius Meisser, Stefan Schmid, Roger Wattenhofer
Abstract — Peer-to-peer (p2p) systems have the potential to harness huge amounts of resources. Unfortunately, however, it has been shown that most of today’s p2p networks suffer from a large...
Dominik Kaspar, Supervisor Prof, Dr. Roger Wattenhofer, Dominik Kaspar, Prof Dr, Roger Wattenhofer
This report was written in the context of a master thesis at the Swiss Federal
A Self-Repairing Peer-to-Peer System (2005)
Fabian Kuhn, Stefan Schmid, Roger Wattenhofer
We present a dynamic distributed hash table where peers may join and leave at any time. Our system tolerates a powerful adversary which has complete visibility of the entire state of the system and...
Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs (2005)
Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, Roger Wattenhofer
Abstract. The distributed complexity of computing a maximal independent set in a graph is of both practical and theoretical importance. While there exists an elegant O(log n) time randomized...
Interference in cellular networks: The minimum membership set cover problem (2005)
Fabian Kuhn, Pascal Von Rickenbach, Roger Wattenhofer, Emo Welzl, Aaron Zollinger
Abstract. The infrastructure for mobile distributed tasks is often formed by cellular networks. One of the major issues in such networks is interference. In this paper we tackle interference...
Fabian Kuhn, Dipl Inf. -ing, Eth Zürich, Waltenschwil Ag, Prof Dr, Roger Wattenhofer, ...
born 30.07.1976 citizen of
Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs (2005)
Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, Roger Wattenhofer
Abstract. The distributed complexity of computing a maximal independent set in a graph is of both practical and theoretical importance. While there exists an elegant O(log n) time randomized...
Distributed Algorithms vs. Ad Hoc Networking (2005)
Roger Wattenhofer, Small Community
• Everybody knows best paper • New algorithm: Compare it with the best previous • Sometimes study the wrong problem; propose protocols that are way too complicated • Big community •...
Interference Arises at the Receiver (2005)
Martin Fussen, Roger Wattenhofer, Aaron Zollinger
Abstract — Energy consumption in general and interference in particular being among the most critical issues in wireless networks, this paper introduces an explicit definition of interference,...
Aaron Zollinger, Dipl Inf. -ing, Eth Zürich, Prof Dr, Roger Wattenhofer, Prof Dr, ...
born 24.04.1975 citizen of
Maximizing the Lifetime of Dominating Sets (2005)
Thomas Moscibroda, Roger Wattenhofer
We investigate the problem of maximizing the lifetime of wireless ad hoc and sensor networks. Being battery powered, nodes in such networks have to perform their intended task under rigid energy...
Geometric routing without geometry (2005)
Mirjam Wattenhofer, Roger Wattenhofer, Peter Widmayer
Abstract. In this paper we propose a new routing paradigm, called pseudogeometric routing. In pseudo-geometric routing, each node u of a network of computing elements is assigned a pseudo coordinate...
Interference Arises at the Receiver (2005)
Martin Fussen, Roger Wattenhofer, Aaron Zollinger
Abstract — Energy consumption in general and interference in particular being among the most critical issues in wireless networks, this paper introduces an explicit definition of interference,...
A cone-based distributed topology-control algorithm for wireless multi-hop networks (2005)
Li (erran Li, Joseph Y. Halpern, Paramvir Bahl, Senior Member, Senior Member, Yi-min Wang, ...
Abstract—The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed...
A Robust Interference Model for Wireless Ad-Hoc Networks (2005)
Pascal Von Rickenbach, Stefan Schmid, Roger Wattenhofer, Aaron Zollinger
Among the foremost goals of topology control in wireless ad-hoc networks is interference reduction. This paper presents a receiver-centric interference model featuring two main advantages over...
A Self-Repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn (2005)
Fabian Kuhn, Stefan Schmid, Roger Wattenhofer
Abstract. We present a dynamic distributed hash table where peers may join and leave at any time. Our system tolerates a powerful adversary which has complete visibility of the entire state of the...
Coloring Unstructured Radio Networks (2005)
Thomas Moscibroda, Roger Wattenhofer
During and immediately after their deployment, ad hoc and sensor networks lack an efficient communication scheme rendering even the most basic network coordination problems difficult. Before any...
A Self-Repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn (2005)
Fabian Kuhn, Stefan Schmid, Roger Wattenhofer
Abstract We present a dynamic distributed hash table where peers may join and leave at any time. Our system tolerates a powerful adversary which has complete visibility of the entire state of the...
A Self-Repairing Peer-toPeer System Resilient to Dynamic Adversarial Churn (2005)
Fabian Kuhn, Stefan Schmid, Roger Wattenhofer
Abstract. We present a dynamic distributed hash table where peers may join and leave at any time. Our system tolerates a powerful adversary which has complete visibility of the entire state of the...
A Self-Repairing Peer-toPeer System Resilient to Dynamic Adversarial Churn (2005)
Fabian Kuhn, Stefan Schmid, Roger Wattenhofer
Abstract We present a dynamic distributed hash table where peers may join and leave at any time. Our system tolerates a powerful adversary which has complete visibility of the entire state of the...
A Self-Repairing Peer-toPeer System Resilient to Dynamic Adversarial Churn (2005)
Fabian Kuhn, Stefan Schmid, Roger Wattenhofer
We present a dynamic distributed hash table where peers may join and leave at any time. Our system tolerates a powerful adversary which has complete visibility of the entire state of the system and...
Unit Disk Graph Approximation (2004)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
Finding a good embedding of a unit disk graph given by its connectivity information is a problem of practical importance in a variety of fields. In wireless ad hoc and sensor networks, such an...
Initializing Newly Deployed Ad Hoc and Sensor Networks (2004)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
A newly deployed multi-hop radio network is unstructured and lacks a reliable and e#cient communication scheme. In this paper, we take a step towards analyzing the problems existing during the...
Virtual Coordinates for Ad hoc and Sensor Networks (2004)
Thomas Moscibroda, Mirjam Wattenhofer, Roger Wattenhofer
In many applications of wireless ad hoc and sensor networks, position-awareness is of great importance. Often, as in the case of geometric routing, it is su#cient to have virtual coordinates, rather...
Radio Network Clustering from Scratch (2004)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
Abstract. We propose a novel randomized algorithm for computing a dominating set based clustering in wireless ad-hoc and sensor networks. The algorithm works under a model which captures the...
What Cannot be Computed Locally (2004)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be...
every available mail client using a Spamato Mail Proxy (2004)
Andreas Wetzel, Supervising Professor, Prof Dr, Roger Wattenhofer, Supervising Assistants, Nicolas Burri, ...
spam filter capabilities to
Distributed Weighted Matching (2004)
Mirjam Wattenhofer, Roger Wattenhofer
Abstract. In this paper, we present fast and fully distributed algorithms for matching in weighted trees and general weighted graphs. The time complexity as well as the approximation ratio of the...
Ad-hoc and sensor networks: worst-case vs. average-case (2004)
Abstract--- Ad-hoc and sensor networks are rapidly growing areas of research which study the problems arising when small and feeble devices build a communication infrastructure. A vast majority of...
Efficient adaptive collect using randomization (2004)
Hagit Attiya, Fabian Kuhn, Mirjam Wattenhofer, Roger Wattenhofer
Abstract. An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractive for distributed systems with a highly-variable number of processes. The cornerstone of...
What Cannot be Computed Locally (2004)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be...
Efficient computation of maximal independent sets in unstructured multi-hop radio networks (2004)
Thomas Moscibroda, Roger Wattenhofer
Abstract--- When being deployed, ad-hoc and sensor networks are unstructured and lack an efficient and reliable communication scheme. Hence, the organization of a MAC layer is the primary goal during...
XTC: A Practical Topology Control Algorithm for Ad-Hoc Networks (2004)
Roger Wattenhofer, Aaron Zollinger
The XTC ad-hoc network topology control algorithm introduced in this paper shows three main advantages over previously proposed algorithms. First, it is extremely simple and strictly local. Second,...
Does Topology Control Reduce Interference? (2004)
Martin Burkhart, Pascal Von Rickenbach, Roger Wattenhofer, Aaron Zollinger
Topology control in ad-hoc networks tries to lower node energy consumption by reducing transmission power and by confining interference, collisions and consequently retransmissions. Commonly low...
Gathering Correlated Data in Sensor Networks (2004)
Pascal Von Rickenbach, Roger Wattenhofer
In this paper, we consider energy-e#cient gathering of correlated data in sensor networks. We focus on single-input coding strategies in order to aggregate correlated data. For foreign coding we...
Aggregating Information in Peer-to-Peer Systems for Improved Join and Leave (2004)
Keno Albrecht, Ruedi Arnold, Michael Gähwiler, Roger Wattenhofer
In this paper, we introduce the Distributed Approximative System Information Service (DASIS) as a useful scheme to aggregate approximative information on the state of a peer-to-peer system. We...
Aggregating Information in Peer-to-Peer Systems for Improved Join and Leave (2004)
Keno Albrecht, Ruedi Arnold, Michael Gähwiler, Roger Wattenhofer
In this paper, we introduce the Distributed Approximative System Information Service (DASIS) as a useful scheme to aggregate approximative information on the state of a peer-to-peer system. We...
Near-Optimal Hot-Potato Routing on Trees (2004)
Costas Busch, Malik Magdon-ismail, Marios Mavronicolas, Roger Wattenhofer
In hot-potato (deflection) routing, nodes in the network have no bu#ers for packets in transit, so that some conflicting packets must be deflected away from their destinations. In this work, we study...
Distributed Weighted Matching (2004)
Mirjam Wattenhofer, Roger Wattenhofer
Abstract. In this paper, we present fast and fully distributed algorithms for matching in weighted trees and general weighted graphs. The time complexity as well as the approximation ratio of the...
Aggregating Information in Peer-to-Peer Systems for Improved Join and Leave (2004)
Keno Albrecht, Ruedi Arnold, Michael Gähwiler, Roger Wattenhofer
In this paper, we introduce the Distributed Approximative System Information Service (DASIS) as a useful scheme to aggregate approximative information on the state of a peer-to-peer system. We...
Analyzing connectivity-based multi-hop ad-hoc positioning (2004)
Regina Bischoff, Roger Wattenhofer
We investigate the theoretical limits of positioning algorithms. In particular, we study scenarios where the nodes do not receive anchors directly (multi-hop) and where no physical distance or angle...
Distributed Weighted Matching (2004)
Mirjam Wattenhofer, Roger Wattenhofer
Abstract. In this paper, we present fast and fully distributed algorithms for matching in weighted trees and general weighted graphs. The time complexity as well as the approximation ratio of the...
Radio Network Clustering from Scratch (2004)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
Abstract. We propose a novel randomized algorithm for computing a dominating set based clustering in wireless ad-hoc and sensor networks. The algorithm works under a model which captures the...
Abstract Algorithms for ad hoc and sensor networks * (2004)
Wireless and mobiles networks are excellent playground for researchers with an algorithm background. Many research problem turn out to be variants of classic graph theory problems. In particular the...
Efficient adaptive collect using randomization (2004)
Hagit Attiya, Fabian Kuhn, Mirjam Wattenhofer, Roger Wattenhofer
Abstract. An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractive for distributed systems with a highly-variable number of processes. The cornerstone of...
Dynamic Analysis of the Arrow Distributed Protocol (2004)
Fabian Kuhn, Roger Wattenhofer
Arrow is a prominent distributed protocol which globally orders requests initiated by the nodes in a distributed system. In this paper we present a dynamic analysis of the Arrow protocol. We prove...
Lower and Upper Bounds for Distributed Packing and Covering (2004)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
We make a step towards understanding the distributed complexity of global optimization problems. We give bounds on the trade-off between locality and achievable approximation ratio of distributed...
How the Hidden-Terminal Problem Affects Clustering in Ad Hoc and Sensor Networks (2004)
Thomas Moscibroda, Fabian Kuhn, Roger Wattenhofer
A newly deployed multi-hop radio network is unstructured and lacks a reliable and efficient communication scheme. In this paper, we define a model containing the characteristics of the initialization...
Marco Cicolini, Supervising Professor, Prof Dr, Roger Wattenhofer
This thesis is about a collaborative text editor, Gclipse. The editor is implemented in Java as an Eclipse plug-in. Eclipse is an application development framework for Java that also provides a Java...
Lower and upper bounds for distributed packing and covering (2004)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
We make a step towards understanding the distributed complexity of global optimization problems. We give bounds on the trade-off between locality and achievable approximation ratio of distributed...
What Cannot Be Computed Locally (2004)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be...
Lower and upper bounds for distributed packing and covering (2004)
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
Abstract We make a step towards understanding the distributed complexity of global optimization problems.We give bounds on the trade-off between locality and achievable approximation ratio of...
Geometric ad-hoc routing : of theory and practice (2003)
Kuhn, Fabian, Wattenhofer, Roger, Zhang, Yan, Zollinger, Aaron
All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we...
Constant-Time Distributed Dominating Set Approximation (2003)
Fabian Kuhn, Roger Wattenhofer
Finding a small dominating set is one of the most fundamental problems of traditional graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation...
Clippee: A large-scale client/peer system (2003)
Keno Albrecht, Ruedi Arnold, Roger Wattenhofer
Abstract--- This paper introduces a client/peer architecture providing services similar to Group Communication systems, but with the scalability of peer-to-peer systems and its dynamic behavior. We...
Constant-Time Distributed Dominating Set Approximation (2003)
Fabian Kuhn, Roger Wattenhofer
Finding a small dominating set is one of the most fundamental problems of traditional graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation...
Geometric Ad-Hoc Routing: Of Theory and Practice (2003)
Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger
All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we...
Clippee: A Large-Scale Client/Peer System (2003)
Keno Albrecht, Ruedi Arnold, Roger Wattenhofer
This paper introduces a client/peer architecture providing services similar to Group Communication systems, but with the scalability of peer-to-peer systems and its dynamic behavior. We present...
Geometric Ad-Hoc Routing: Of Theory and Practice (2003)
Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Computer Science
ABSTRACT All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In...
Li, Erran L., Halpern, Joseph Y., Bahl, Paramvir, Wang, Yi-Min, Wattenhofer, Roger
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...
Asymptotically optimal geometric mobile ad-hoc routing (2002)
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
In this paper we present AFR, a new geometric mobile adhoc routing algorithm. The algorithm is completely distributed; nodes need to communicate only with direct neighbors in their transmission...
Asymptotically optimal geometric mobile ad-hoc routing (2002)
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
In this paper we present AFR., a new geometric mobile adhoc routing algorithm. The algorithm is completely distributed; nodes need to communicate only with direct neighbors in their transmission...
Geometric ad-hoc routing for unit disk graphs and general cost models (2002)
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
What is the in uence of the chosen cost metric on the performance of a mobile ad-hoc routing algorithm? In this paper we dene the notion of a general cost metric and observe that all cost metrics...
Geometric ad-hoc routing for unit disk graphs and general cost models (2002)
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
What is the in uence of the chosen cost metric on the performance of a mobile ad-hoc routing algorithm? In this paper we dene the notion of a general cost metric and observe that all cost metrics...
Towards a Theory of Peer-to-Peer Computability (2002)
Joachim Giesen, Roger Wattenhofer, Aaron Zollinger
A peer-to-peer system is a distributed system with no physical or logical central authority. We give a formal model of a peer-to-peer system where agents communicate through read-modify-write...
A Cone-Based Distributed Topology-Control Algorithm for Wireless Multi-Hop Networks (2002)
Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...
Competitive concurrent distributed queuing (2001)
Maurice Herlihy, Srikanta Tirthapura, Roger Wattenhofer
Distributed queuing is a fundamental problem in distributed computing, arising in a variety of applications. The challenge in designing a distributed queuing algorithm is to minimize message trac and...
Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer
bahl~microsoft, corn ymwang~microsoft, corn rogerwa~microsoft, corn The topology of a wireless multi-hop network can be con-trolled by varying the transmission power at each node. In this paper, we...
Competitive Hill-Climbing Strategies for Replica Placement in a Distributed File System (2001)
John Douceur, Roger Wattenhofer
1 Introduction This paper analyzes algorithms for automated placement of file replicas in the Farsite [3] system, using both theory and simulation. In the Farsite distributed file system, multiple...
The Impact of Internet Policy and Topology on Delayed Routing Convergence (2001)
Craig Labovitz, Roger Wattenhofer
Although recent advances in the IETF's Differentiated Services workinggroup promise to improve the performance of application-level services within some networks, across the wide-area Internet...
Roger Wattenhofer, Li Li, Paramvir Bahl, Yi-min Wang
Abstract — The topology of wireless multihop ad hoc networks can be controlled by varying the transmission power of each node. We propose a simple distributed algorithm where each node makes local...
Competitive Hill-Climbing Strategies for Replica Placement in a Distributed File System (2001)
John Douceur, Roger Wattenhofer
The Farsite distributed le system stores multiple replicas of les on multiple machines, to provide le access even when some machines are unavailable. Farsite assigns le replicas to machines so as to...
Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...
The Impact of Internet Policy and Topology on Delayed Routing Convergence (2001)
Craig Labovitz, Roger Wattenhofer, Srinivasan Venkatachary, Abha Ahuja
The Internet's sustained exponential growth and the continued emergence of new and varied network applications provides testament to the scalability of the backbone infrastructure and protocols....
Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-Min Wang, Roger Wattenhofer
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...
Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...
John Douceur, Roger Wattenhofer
We examine the replica placement aspect of a distributed peer-to-peer le system that replicates and stores les on ordinary desktop computers. It has been shown that some desktop machines are...
Roger Wattenhofer, Li Li, Paramvir Bahl, Yi-min Wang
Abstract — The topology of wireless multihop ad hoc networks can be controlled by varying the transmission power of each node. We propose a simple distributed algorithm where each node makes local...
Competitive concurrent distributed queuing (2001)
Maurice Herlihy, Srikanta Tirthapura, Roger Wattenhofer
Distributed queuing is a fundamental problem in distributed computing, arising in a variety of applications. The challenge in designing a distributed queuing algorithm is to minimize message trac and...
Roger Wattenhofer, Li Li, Paramvir Bahl, Yi-min Wang
Abstract--- The topology of wireless multihop ad hoc networks can be controlled by varying the transmission power of each node. We propose a simple distributed algorithm where each node makes local...
John Douceur, Roger Wattenhofer
We examine the replica placement aspect of a distributed peer-to-peer file system that replicates and stores files on ordinary desktop computers. It has been shown that some desktop machines are...
Competitive concurrent distributed queuing (2001)
Maurice Herlihy, Srikanta Tirthapura, Roger Wattenhofer
Distributed queuing is a fundamental problem in distributed computing, arising in a variety of applications. The challenge in designing a distributed queuing algorithm is to minimize message traffic...
Roger Wattenhofer, Li Li, Paramvir Bahl, Yi-min Wang
Abstract — The topology of wireless multihop ad hoc networks can be controlled by varying the transmission power of each node. We propose a simple distributed algorithm where each node makes local...
Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...
Resilience characteristics of the internet backbone routing infrastructure (2000)
Craig Labovitz, Roger Wattenhofer, Srinivasan Venkatachary, Abha Ahuja
It is widely believed that the Internet is a highly faulttolerant,
Resilience characteristics of the internet backbone routing infrastructure (2000)
Craig Labovitz, Roger Wattenhofer, Srinivasan Venkatachary
It is widely believed that the Internet is a highly faulttolerant, survivable network. In particular, the Internet is attributed with the ability to route packets around faults quickly, in a matter...
Randomized Greedy Hot-Potato Routing (2000)
Costas Busch, Maurice Herlihy, Roger Wattenhofer
We present a novel greedy hot-potato routing algorithm for the 2-dimensional n × n mesh or torus. This algorithm uses randomization to adjust packet priorities. For any permutation problem...
Ordered Multicast and Distributed Swap (2000)
Maurice Herlihy, Srikanta Tirthapura, Roger Wattenhofer
A multicast protocol is ordered (or totally ordered) if it ensures that messages multicast to a group of nodes are delivered in the same order at each destination node, even when those messages are...
Randomized Greedy Hot-Potato Routing (2000)
Costas Busch Maurice, Maurice Herlihy, Roger Wattenhofer
We present a novel greedy hot-potato routing algorithm for the 2-dimensional n n mesh or torus. This algorithm uses randomization to adjust packet priorities. For any permutation problem or random...
Ordered Multicast and Distributed Swap preliminary report (2000)
Maurice Herlihy, Srikanta Tirthapura, Roger Wattenhofer
A multicast protocol is ordered (or totally ordered) if it ensures that messages multicast to a group of nodes are delivered in the same order at each destination node, even when those messages are...
Roger Wattenhofer, Peter Widmayer
A distributed counter is a concurrent object which provides a test-and-incrementoperation on a shared value. On the basis of a distributed counter, one can implement various fundamental data...
An Inherent Bottleneck in Distributed Counting (1997)
Roger Wattenhofer, Peter Widmayer
A distributed counter allows each processor in an asynchronous message passing network to access the counter value and increment it. We study the problem of implementing a distributed counter such...
Distributed Counting at Maximum Speed (1997)
Roger Wattenhofer, Peter Widmayer
this paper, we propose an efficient linearizable counter. The definition of efficiency for distributed data structures in general and for a distributed counter in particular is not as immediate as in...
An Inherent Bottleneck in Distributed Counting (1997)
Roger Wattenhofer, Peter Widmayer
A distributed counter allows each processor in an asynchronous message passing network to access the counter value and increment it. We study the problem of implementing a distributed counter such...
Thomas Moscibroda, Roger Wattenhofer
Reducing interference is one of the main challenges in wireless communication, and particularly in ad hoc networks. The amount of interference experienced by a node v corresponds to the number of...
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be...
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
Many large-scale networks such as ad hoc and sensor networks, peer-to-peer networks, or the Internet have the property that the number of independent nodes does not grow arbitrarily when looking at...
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
Many large-scale networks such as ad hoc and sensor networks, peer-to-peer networks, or the Internet have the property that the number of independent nodes does not grow arbitrarily when looking at...
Thomas Moscibroda, Roger Wattenhofer
Reducing interference is one of the main challenges in wireless communication, and particularly in ad hoc networks. The amount of interference experienced by a node v corresponds to the number of...
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
Finding a good embedding of a unit disk graph given by its connectivity information is a problem of practical importance in a variety of fields. In wireless ad hoc and sensor networks, such an...
Thomas Moscibroda, Roger Wattenhofer
During and immediately after their deployment, ad hoc and sensor networks lack an efficient communication scheme rendering even the most basic network coordination problems difficult. Before any...
Fabian Kuhn, Thomas Locher, Roger Wattenhofer
We revisit the problem of distributed k-selection where, given a general connected graph of diameter D consisting of n nodes in which each node holds a numeric element, the goal is to determine the k...
Fabian Kuhn, Tim Nieberg, Thomas Moscibroda, Roger Wattenhofer
We present two local approaches that yield polynomial-time approximation schemes (PTAS) for the Maximum Independent Set and Minimum Dominating Set problem in unit disk graphs. The algorithms run...
Fabian Kuhn, Roger Wattenhofer
Coloring the nodes of a graph with a small number of colors is one of the most fundamental problems in theoretical computer science. In this paper, we study graph coloring in a distributed setting....
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be...
Distributed Data & Resources: Models, Tractability, and Complexity (1968)
Prof Dr, Peter Widmayer, Prof Dr, Roger Wattenhofer
The title page shows an example for the Weber set. There are four points in convex position. The Weber point is the intersection of the diagonals, the Weber set is marked grey.
Distributed Data & Resources: Models, Tractability, and Complexity (1968)
Prof Dr, Peter Widmayer, Prof Dr, Roger Wattenhofer
The title page shows an example for the Weber set. There are four points in convex position. The Weber point is the intersection of the diagonals, the Weber set is marked grey.
Greedy O(c+d) hot-potato routing on trees (1218)
Costas Busch, Malik Magdon-ismail, Marios Mavronicolas, Roger Wattenhofer
In hot-potato (deflection) routing, nodes in the network have no bu#ers for packets in transit. A hotpotato routing algorithm is greedy if packets are advanced from their sources toward their...
Greedy O(c+d) hot-potato routing on trees (1218)
Costas Busch, Malik Magdon-ismail, Marios Mavronicolas, Roger Wattenhofer
In hot-potato (deflection) routing, nodes in the network have no buffers for packets in transit. A hotpotato routing algorithm is greedy if packets are advanced from their sources toward their...