home > Publications > Search

Found 137 publications with these criteria

1. Fabian Kuhn, Christoph Lenzen, Thomas Locher, and Rotem Oshman   [KuhnLLO:10]   [published]
   Optimal Gradient Clock Synchronization in Dynamic Networks    
   29th Annual ACM Symposium on Principles of Distributed Computing, Zurich, 25-28 July 10
   We study the fundamental problem of synchronizing clocks in dynamic networks. The networks that we consider are highly dynamic in the sense that existing communication links may disappear and new links may appear in an arbitrary manner at any time. Furthermore, the progress rates of the hardware clocks may vary arbitrarily within specific bounds, and there is a certain inaccuracy in all timing information that a node possesses about the local time at other nodes. The goal is to analyze the feasible degree of synchronization in this model. Apart from synchronizing the clocks of any two nodes in the system as accurately as possible, we strive to guarantee a stronger bound on the worst-case clock skew between nodes that share a direct communication link. This bound is time-dependent and gets stronger the longer the communication link exists. The crucial question is whether the optimal bounds on the clock skews in the static model, where the underlying network topology never changes, also apply to this highly dynamic setting. We show that it is indeed possible to guarantee the same asymptotically optimal bounds on the worst-case clock skew, both between any two nodes in the network and also between nodes that have been connected directly for a sufficiently long period of time. Moreover, the stabilization time, i.e., the time it takes to reduce the potentially large clock skew over a newly formed communication link substantially is shown to be asymptotically optimal as well.
   
   
2. Thomas Lochmatter   [Lochmatter:10]   [published]
   Bio-inspired and probabilistic algorithms for distributed odor source localization using mobile robots    
   PhD thesis EPFL, Spring 2010 (Prof. A. Martinoli)
   
   
   
3. Maria Naya-Plasencia, Andrea Roeck, Jean-Philippe Aumasson, Yann Laigle-Chapuy, Gaetan Leurent, Willi Meier, and Thomas Peyrin   [NayaRALLMP:10]   [published]
   Cryptanalysis of ESSENCE    
   FES 2010, Seoul, 7-10 Feb 10
   ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly parallelizable design. Previous analysis showed some non-randomness in the compression function which could not be extended to an attack on the hash function and ESSENCE remained unbroken. Preliminary analysis in its documentation argues that it resists standard differential cryptanalysis. This paper disproves this claim, showing that advanced techniques can be used to signicantly reduce the cost of such attacks: using a manually found differential characteristic and an advanced search algorithm, we obtain collision attacks on the full ESSENCE-256 and ESSENCE- 512, with respective complexities 2^67.4 and 2^134.7. In addition, we show how to use these attacks to forge valid (message, MAC) pairs for HMACESSENCE- 256 and HMAC-ESSENCE-512, essentially at the same cost as a collision.
   
   
4. Christoph Lenzen, Thomas Locher, Philipp Sommer, and Roger Wattenhofer   [LenzenLSW:10]   [published]
   Clock Synchronization: Open Problems in Theory and Practice (Invited Paper)    
   36th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Splinderuv Mlyn, 23-29 Jan 10
   Clock synchronization is one of the most basic building blocks for many applications in computer science and engineering. The purpose of clock synchronization is to provide the constituent parts of a distributed system with a common notion of time. While the problem of synchronizing clocks in distributed systems has already received considerable attention from researchers and practitioners alike, we believe that there are many fascinating problems that remain unsolved. In this paper, we give a brief overview of previous work in this area, followed by a discussion of open clock synchronization problems in theory and practice.
   
   
5. Thomas Locher, David Mysicka, Stefan Schmid, and Roger Wattenhofer   [LocherMSW:10]   [published]
   Poisoning the Kad Network    
   11th International Conference on Distributed Computing and Networking (ICDCN), Kolkata, 3-6 Jan 10
   Since the demise of the Overnet network, the Kad network has become not only the most popular but also the only widely used peer-to-peer system based on a distributed hash table. It is likely that its user base will continue to grow in numbers over the next few years as, unlike the eDonkey network, it does not depend on central servers, which increases scalability and reliability. Moreover, the Kad network is more efficient than unstructured systems such as Gnutella. However, we show that today’s Kad network can be attacked in several ways by carrying out several (well-known) attacks on the Kad network. The presented attacks could be used either to hamper the correct functioning of the network itself, to censor contents, or to harm other entities in the Internet not participating in the Kad network such as ordinary web servers. While there are simple heuristics to reduce the impact of some of the attacks, we believe that the presented attacks cannot be thwarted easily in any fully decentralized peerto- peer system without some kind of a centralized certification and verification authority.
   
   
6. Christoph Lenzen, Thomas Locher, and Roger Wattenhofer   [LenzenLW:10]   [published]
   Tight Bounds for Clock Synchronization    
   Journal of the ACM, Volume 57, Number 2, Jan 2010
   We present a novel clock synchronization algorithm and prove tight upper and lower bounds on the worst-case clock skew that may occur between any two participants in any given distributed system. More importantly, the worst-case clock skew between neighboring nodes is (asymptotically) at most a factor of two larger than the best possible bound. While previous results solely focused on the dependency of the skew bounds on the network diameter, we prove that our techniques are optimal also with respect to the maximum clock drift, the uncertainty in message delays, and the imposed bounds on the clock rates. The presented results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specified bounds. Furthermore, our algorithm exhibits a number of other highly desirable properties. First, the algorithm ensures that the clock values remain in an affine linear envelope of real time. A better worst-case bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. Second, the algorithm minimizes the number and size of messages that need to be exchanged in a given time period. Moreover, only a small number of bits must be stored locally for each neighbor. Finally, our algorithm can easily be adapted for a variety of other prominent synchronization models. [pdf]
   
   
7. Eric Brier, Shahram Khazaei, Willi Meier and Thomas Peyrin   [BrierKMP:09]   [published]
   Linearization Framework for Collision Attacks: Application to CubeHash and MD6    
   Asiacrypt 2009, Tokyo, 6-10 Dec 09
   In this paper, an improved differential cryptanalysis framework for finding collisions in hash functions is provided. Its principle is based on linearization of compression functions in order to find low weight differential characteristics as initiated by Chabaud and Joux. This is formalized and refined however in several ways: for the problem of finding a conforming message pair whose differential trail follows a linear trail, a condition function is introduced so that finding a collision is equivalent to finding a preimage of the zero vector for the condition function. Then, the dependency table concept shows how much influence every input bit of the condition function has on each output bit. Careful analysis of the dependency table reveals degrees of freedom that can be exploited in accelerated preimage reconstruction of the condition function. These concepts are applied to an in-depth collision analysis of reduced-round versions of the two SHA-3 candidates CubeHash and MD6, and are demonstrated to give by far the best currently known collision attacks on these SHA-3 candidates.
   
   
8. Markus Waelchli, Reto Zurbuchen, Thomas Staub and Torsten Braun   [WaelchliZSB:09b]   [published]
   Backbone MAC for Energy-constrained Wireless Sensor Networks    
   34th IEEE Conference on Local Computer Networks (LCN), Zürich, 22-23 Oct 09
   In this paper we propose a routing backbone construction mechanism that exploits and uses the synchronization messages exchanged by synchronized contention-based MAC protocols. Due to the usage of synchronization messages no additional control traffic is required to setup the routing backbone. Every node running a synchronized contention-based MAC protocol follows a given listen/sleep cycle. Because routing is supported by the backbone, non-backbone nodes can temporarily turn off their radios for multiple listen/sleep cycles. Thus, additional energy can be saved. Accordingly, non-backbone nodes do not have to wake up in every listen/sleep cycle to synchronize with other nodes, but wake up only if required, i.e., if they have to report some sensor readings to a base station. In this case, they synchronize to the backbone, send their data, and go back to sleep after successful transmission. Our approach is applicable to rather static networks with mainly source-to-sink traffic. Most monitoring applications are of this kind.
   
   
9. Thomas Locher   [Locher:09]   [published]
   Foundations of aggregation and synchronization in distributed systems    
   PhD Thesis ETH Zurich, Autumn 2009 (Prof. R. Wattenhofer)
   
   
   
10. Thomas Locher, David Mysicka, Stefan Schmid, and Roger Wattenhofer   [LocherMSW:09]   [published]
    A Peer Activity Study in eDonkey and Kad (Invited paper)    
    International Workshop on Dynamic Networks: Algorithms and Security (DYNAS), Wroclaw, 5 Sep 09
    Although several fully decentralized peer-to-peer systems have been proposed in the literature, most existing systems still employ a centralized architecture. In order to compare these two paradigms, as a case study, we conduct measurements in the eDonkey and the Kad network—two of the most popular peer-to-peer systems in use today. We reengineered the eDonkey server software and integrated two modified servers into the eDonkey network in order to monitor traffic. Additionally, we implemented a Kad client exploiting a design weakness to spy on the traffic at arbitrary locations in the ID space. The goal of this study is to provide insight into the spacial and temporal distributions of the peers’ activities and also examine the searched contents. Finally, we discuss problems related to the collection of such data sets and investigate techniques to verify the representativeness of the measured data.
    
    
11. Fabian Kuhn, Thomas Locher, and Rotem Oshman   [KuhnLO:09]   [published]
    Gradient Clock Synchronization in Dynamic Networks    
    21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, 11-13 Aug 09
    
    
    
12. Christoph Lenzen, Thomas Locher, and Roger Wattenhofer   [LenzenLW:09]   [published]
    Tight Bounds for Clock Synchronization    
    28th ACM Symposium on Principles of Distributed Computing (PODC), Calgary, 10-12 Aug 09
    We present a novel clock synchronization algorithm and prove tight upper and lower bounds on the worst-case clock skew that may occur between any two participants in any given distributed system. More importantly, the worst-case clock skew between neighboring nodes is (asymptotically) at most a factor of two larger than the best possible bound. While previous results solely focused on the dependency of the skew bounds on the network diameter, we prove that our techniques are optimal also with respect to the maximum clock drift, the uncertainty in message delays, and the imposed bounds on the clock rates. The presented results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specied bounds. Furthermore, our algorithm exhibits a number of other highly desirable properties. First, the algorithm ensures that the clock values remain in an ane linear envelope of real time. A better bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. Second, the algorithm minimizes the number and size of messages that need to be exchanged in a given time period. Moreover, only a small number of bits must be stored locally for each neighbor. Finally, our algorithm can easily be adapted for a variety of other prominent synchronization models. [pdf]
    
    
13. Roderick Bloem, Krishnendu Chatterjee, Thomas Henzinger, Barbara Jobstmann   [BloemCHJ:09]   [published]
    Better Quality in Synthesis through Quantitative Objectives    
    21th Int. Conf. on Computer-Aided Verification (CAV), Grenoble, June 26 - July 2, 2009
    Most specification languages express only qualitative constraints. However, among two implementations that satisfy a given specification, one may be preferred to another. For example, if a specification asks that every request is followed by a response, one may prefer an implementation that generates responses quickly but does not generate unnecessary responses. We use quantitative properties to measure the ``goodness'' of an implementation. Using games with corresponding quantitative objectives, we can synthesize ``optimal'' implementations, which are preferred among the set of possible implementations that satisfy a given specification. In particular, we show how automata with lexicographic mean-payoff conditions can be used to express many interesting quantitative properties for reactive systems. In this framework, the synthesis of optimal implementations requires the solution of lexicographic mean-payoff games (for safety requirements), and the solution of games with both lexicographic mean-payoff and parity objectives (for liveness requirements). We present algorithms for solving both kinds of novel graph games.
    
    
14. Thomas Locher, Remo Meier, Roger Wattenhofer, and Stefan Schmid   [LocherMWS:09]   [published]
    Robust Live Media Streaming in Swarms    
    19th International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV), Williamsburg, 3-5 June 09
    
    
    
15. Lochmatter, Thomas; Martinoli, Alcherio   [LochmatterM:09]   [published]
    Theoretical Analysis of Three Bio-Inspired Plume Tracking Algorithms    
    2009 IEEE International Conference on Robotics and Automation (ICRA 2009); Kobe, Japan, May 12-17, 2009
    We derive the theoretical performance of three bio-inspired odor source localization algorithms (casting, surge-spiral and surge-cast) in laminar wind flow. Based on the geometry of the trajectories and the wind direction sensor error, we calculate the distribution of the distance overhead and the mean success rate using Bayes inference. Our approach is related to particle filtering and produces smooth output distributions. The results are compared to existing real-robot and simulation results, and a good match is observed.
    
    
16. Markus Waelchli, Reto Zurbuchen, Thomas Staub, Torsten Braun   [WaelchliZSB:09]   [published]
    Gravity-based Local Clock Synchronization in Wireless Sensor Networks    
    Networking 2009, Aachen, 11 - 16 May 2009
    Contention-based MAC protocols follow periodic listen/sleep cycles. These protocols face the problem of virtual clustering if different unsynchronized listen/sleep schedules occur in the network, which has been shown to happen in wireless sensor networks. To interconnect these virtual clusters, border nodes, which maintain all respective listen/sleep schedules, are required. This is however a waste of energy if locally a common schedule can be determined. We propose to achieve local synchronization with a mechanism that is similar to gravitation. Clusters represent the material, whereas synchronization messages sent by each cluster represent the gravitation force of the according cluster. Due to the mutual attraction caused by the clusters, all clusters merge finally. [pdf]
    
    
17. Lochmatter, Thomas; Heiniger, Nicolas; Martinoli, Alcherio   [LochmatterHM:09]   [published]
    Localizing an Odor Source and Avoiding Obstacles: Experiments in a Wind Tunnel using Real Robots    
    13th International Symposium on Olfaction and Electronic Nose; Brescia, Italy, April 15-17, 2009, p. 69-72
    We report on real-robot odor source localization experiments carried out in an environment with obstacles in the odor plume. The robot was equipped with an ethanol sensor and a wind direction sensor, and the experiments were carried out in a wind tunnel, i.e. in a controlled environment. An enhanced version of the surge-spiral algorithm was used, which was augmented with a dedicate behavior to manage obstacles (avoid them, or follow their contour). We compare the results in terms of distance overhead and success rate, and discuss the impact of obstacles on plume traversal.
    
    
18. Lochmatter, Thomas; Martinoli, Alcherio   [LochmatterM:08b]   [published]
    Simulation Experiments with Bio-Inspired Algorithms for Odor Source Localization in Laminar Wind Flow    
    Seventh International Conference on Machine Learning and Applications (ICMLA 2008); San Diego, CA, USA, December 11-13, 2008
    We compare three bio-inspired odor source localization algorithm (casting, surge-spiral and surge-cast) for environments with a main wind flow in simulation. The wind flow is laminar and the simulation setup similar to the setup in the wind tunnel in which we have carried out similar experiments with real robots. The algorithms are compared in terms of success rate and distance overhead when tracking the plume up to the source. We conclude that the algorithms based on upwind surge yield significantly better performance than pure casting.
    
    
19. Lochmatter, Thomas; Martinoli, Alcherio   [LochmatterM:08]   [published]
    Understanding the Potential Impact of Multiple Robots in Odor Source Localization    
    9th Symposium on Distributed Autonomous Robotic Systems (DARS 2008); Tsukuba, Japan, November 17-19, 2008
    
    
    
20. Christoph Lenzen, Thomas Locher, and Roger Wattenhofer.   [LenzenLW:08]   [published]
    Clock Synchronization with Bounded Global and Local Skew     
    49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Philadelphia, 26-28 Oct 08.
    We present a distributed clock synchronization algorithm that guarantees an exponentially improved bound of O(logD) on the clock skew between neighboring nodes in any graph G of diameter D. In light of the lower bound of (logD= log logD), this result is almost tight. Moreover, the global clock skew between any two nodes, particularly nodes that are not directly connected, is bounded by O(D), which is optimal up to a constant factor. Our algorithm further ensures that the clock values are always within a linear envelope of real time. A better bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. These results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specified bounds. [pdf]
    
    
21. Laurent Doyen, Thomas Henzinger, Barbara Jobstmann and Tatjana Petrov   [DoyenHJP:08]   [published]
    Interface Theories with Component Reuse    
    International Conference on Embedded Software (EMSOFT), Atlanta, 24-29 Oct 08
    Interface theories have been proposed to support incremental design and independent implementability. Incremental design means that the compatibility checking of interfaces can proceed for partial system descriptions, without knowing the interfaces of all components. Independent implementability means that compatible interfaces can be refined separately, maintaining compatibility. We show that these interface theories provide no formal support for component reuse, meaning that the same component cannot be used to implement several different interfaces in a design. We add a new operation to interface theories in order to support such reuse. For example, different interfaces for the same component may refer to different aspects such as functionality, timing, and power consumption. We give both stateless and stateful examples for interface theories with component reuse. To illustrate component reuse in interface-based design, we show how the stateful theory provides a natural framework for specifying and refining PCI bus clients.
    
    
22. Thomas Henzinger   [Henzinger:08]   [published]
    Two challenges in embedded systems design: Predictability and robustness    
    Philosophical Transactions of the Royal Society, Oct 08
    We discuss two main challenges in embedded systems design: the challenge to build predictable systems, and the challenge to build robust systems. We suggest how predictability can be formalized as a form of determinism, and robustness, as a form of continuity.
    
    
23. Lochmatter, Thomas; Roduit, Pierre; Cianci, Chris; Correll, Nikolaus; Jacot, Jacques; Martinoli, Alcherio   [LochmatterRCCJM:08]   [published]
    SwisTrack - A Flexible Open Source Tracking Software for Multi-Agent Systems    
    IEEE/RSJ 2008 International Conference on Intelligent Robots and Systems (IROS 2008); Nice, France, September 22-26, 2008, p. 4004-4010
    Vision-based tracking is used in nearly all robotic laboratories for monitoring and extracting of agent positions, orientations, and trajectories. However, there is currently no accepted standard software solution available, so many research groups resort to developing and using their own custom software. In this paper, we present Version 4 of SwisTrack, an open source project for simultaneous tracking of multiple agents. While its broad range of pre- implemented algorithmic components allows it to be used in a variety of experimental applications, its novelty stands in its highly modular architecture. Advanced users can therefore also implement additional customized modules which extend the functionality of the existing components within the provided interface. This paper introduces SwisTrack and shows experiments with both marked and marker-less agents.
    
    
24. Fabian Kuhn, Thomas Locher, and Roger Wattenhofer   [KuhnLW:08]   [published]
    Distributed Selection: A Missing Piece of Data Aggregation     
    Communications of the ACM, Volume 51, Number 9, September 2008
    In this article, we study the problem of distributed selection from a theoretical point of view. Given a general connected graph of diameter D consisting of n nodes in which each node holds a numeric element, the goal of a k-selection algorithm is to determine the kth smallest of these elements. We prove that distributed selection indeed requires more work than other aggregation functions such as, e.g., the computation of the average or the maximum of all elements. On the other hand, we show that the kth smallest element can be computed efficiently by providing both a randomized and a deterministic k-selection algorithm, dispelling the misconception that solving distributed selection through in-network aggregation is infeasible. [pdf]
    
    
25. Heinrich Luecken, Thomas Zasowski, Christoph Steiner, Florian Troesch, and Armin Wittneben   [LueckenZSTW:08]   [published]
    Location-aware Adaptation and Precoding for Low Complexity IR-UWB Receivers    
    IEEE International Conference on Ultra-Wideband (ICUWB 2008), Hannover, 10-12 Sep 08
    An environment is considered with many low complexity wireless mobile stations communicating to higher complexity stationary cluster heads. The cluster heads can determine the rough position of the mobile stations using geo-regioning. The mobile stations are not able to perform a channel estimation due to complexity reasons. We present two approaches to utilize regional channel knowledge available at the cluster head for improvement of the data detection performance at the mobile station. First, by feeding back the average power delay profile of the channel from the cluster head to the mobile station, the mobile station can adapt a filter according to this information. Second, at cluster head side the covariance matrix of the channel impulses response vectors is used for precoding optimization. Based on channel impulse responses measured in a realistic environment the performance of both approaches is evaluated. Performance gains of 1 to 3 dB compared to energy detection can be obtained. [pdf]
    
    
26. Krishnendu Chatterjee, Thomas Henzinger and Barbara Jobstmann   [ChatterjeeHJ:08]   [published]
    Environment Assumptions for Synthesis    
    Conference on Concurrency Theory (CONCUR), Toronto, 19-22 Aug 08
    The synthesis problem asks to construct a reactive finite-state system from an $\omega$-regular specification. Initial specifications are often unrealizable, which means that there is no system that implements the specification. A common reason for unrealizability is that assumptions on the environment of the system are incomplete. We study the problem of correcting an unrealizable specification $\varphi$ by computing an environment assumption $\psi$ such that the new specification $\psi\rightarrow\varphi$ is realizable. Our aim is to construct an assumption $\psi$ that constrains only the environment and is as weak as possible. We present a two-step algorithm for computing assumptions. The algorithm operates on the game graph that is used to answer the realizability question. First, we compute a safety assumption that removes a minimal set of environment edges from the graph. Second, we compute a liveness assumption that puts fairness conditions on some of the remaining environment edges. We show that the problem of finding a minimal set of fair edges is computationally hard, and we use probabilistic games to compute a locally minimal fairness assumption.
    
    
27. Fabian Kuhn, Thomas Locher and Stefan Schmid   [KuhnLS:08]   [published]
    Distributed Computation of the Mode    
    27th Annual Symposium on Principles of Distributed Computing (PODC); Toronto, Canada, 18-21 August 2008
    
    
    
28. Olga Goussevskaia, Thomas Moscibroda, and Roger Wattenhofer.   [GoussevskaiaMW:08]   [published]
    Local Broadcasting in the Physical Interference Model     
    ACM SIGACT-SIGOPT International Workshop on Foundations of Mobile Computing (DialM-POMC), Toronto, August 2008.
    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 there are in its geographical proximity, and another, which makes no assumptions about topology knowledge. We show that, if the transmission probability of each node meets certain characteristics, the analysis can be decoupled from the global nature of the physical interference model, and each node performs a successful local broadcast in time proportional to the number of neighbors in its physical proximity. We also provide worst-case optimality guarantees for both algorithms and demonstrate their behavior in average scenarios through simulations. [pdf]
    
    
29. Nicholas D. Matsakis and Thomas R. Gross   [MatsakisG:08]   [published]
    Thread Safety Through Partitions and Effect Agreements    
    LCPC 2008, Alberta, 31 July - 2 Aug 08
    This paper describes a safety analysis for a multithreaded system based upon transactional memory. The analysis guarantees that shared data is always read and written from within a transaction, while allowing for unsynchronized access to thread-local and (shared) read-only data, as well as the migration of data between threads. The analysis is based on a type and effect system for object-oriented programs called partitions. Programmers specify a partitioning of the heap into disjoint regions at a field-level granularity, and then use this partitioning to enforce safety properties in their programs. Our flow-sensitive effect system requires methods to disclose which partitions of the heap they will read or write, and also allows them to specify an effect agreement which can be used to limit the conditions in which a method can be called. [pdf]
    
    
30. Lochmatter, Thomas; Martinoli, Alcherio   [LochmatterM:08]   [published]
    Tracking Odor Plumes in a Laminar Wind Field with Bio-Inspired Algorithms    
    11th International Symposium on Experimental Robotics 2008 (ISER 2008); Athens, Greece, July 14-17, 2008, vol. 54, p. 473-482
    We introduce a novel bio-inspired odor source localization algorithm (surge- cast) for environments with a main wind ?ow and compare it to two well-known algorithms. With all three algorithms, systematic experiments with real robots are carried out in a wind tunnel under laminar ?ow conditions. The algorithms are compared in terms of distance overhead when tracking the plume up to the source, but a variety of other experimental results and some theoretical considerations are provided as well. We conclude that the surge-cast algorithm yields signi?cantly better performance than the casting algorithm, and slightly better performance than the surge-spiral algorithm.
    
    
31. Susanne Cech Previtali and Thomas R. Gross   [PrevitaliG:08b]   [published]
    A Case Study for Aspect-Based Updating    
    5th ECOOP'2008 Workshop on Reflection, AOP and Meta-Data for Software Evolution, Paphos, 7 July 08
    Rather than upgrading a software system to the next version by installing a new binary, software systems could be updated ``on-the-fly'' during their execution. We are developing a software evolution system that leverages aspect technology. As changes typically spread across several classes, we can handle updates like other crosscutting concerns: we encapsulate all changes, constituting a logical update, in one aspect. In this paper, we evaluate our approach. We report on a case study about the evolution of a Java application. The analysis provides details about how classes change between versions, and how these changes would be expressed in terms of updating aspects. Unfortunately, not all kinds of changes can be expressed using the aspect model. The results of our study, however, reveal that many changes fit our aspect-based approach. [pdf]
    
    
32. Susanne Cech Previtali and Thomas R. Gross   [PrevitaliG:08c]   [published]
    Annotations for Seamless Aspect-Based Software Evolution    
    5th ECOOP'2008 Workshop on Reflection, AOP and Meta-Data for Software Evolution, Paphos, 7 July 08
    We are developing a dynamic software evolution system that leverages aspect technology to encapsulate software updates. Ideally, an evolution system provides as much automation as possible. Certain changes, however, defeat automation. For instance, field additions cannot be concisely captured without the feedback of the programmer. Rather than reconstructing the missing information in retrospect, we propose to gather the necessary meta-data along with the development process. We use Java annotations for that purpose: for instance, programmers may annotate added fields with their corresponding initialization. In some cases, the software development environment may even infer annotations from the actions taken by the programmer, and therefore, annotations enable a seamless software evolution cycle. [pdf]
    
    
33. Oliver Trachsel, Christian Fischlin, Thomas R. Gross   [TrachselFG:08]   [published]
    A Platform for Competitive Execution    
    ISCA '08 Workshop on Parallel Execution of Sequential Programs on Multi-core Architectures, Beijing, 22 June 08
    We propose competitive execution as an approach to leverage multi-core systems for sequential programs. Different variants of a program are executed competitively in parallel on multiple processor cores. Variants are generated by selecting different optimization strategies during compilation. The execution of a program is split into phases, and the variants compete in each phase. The fastest variant determines the execution time of the phase, thereby reducing the overall execution time of the program. This paper presents a software platform that enables competitive execution under Linux. The software system orchestrates the execution of the variants and performs state synchronization between variants. The usage of the system requires minimal modifications to existing programs, in the form of a set of system calls to define execution phases. We also propose a language-integrated extension of the competitive execution paradigm to define variant-selection based on metrics other than performance. [pdf]
    
    
34. Yang Su, Peter Steenkiste, Thomas Gross   [SuSG:08]   [published]
    Performance of TCP in Multi-Hop Access Networks    
    16th International Workshop on Quality of Service (IWQoS 2008), Enschede, 2-4 June 08
    Wireless multi-hop access networks are an increasingly popular option to provide cost-efficient last-mile Internet access. However, despite extensive research, performance of even basic communication services, such as TCP, is still problematic. Measurements collected on a wireless testbed indicate that the poor performance of multi-hop access networks is caused by poor interactions between TCP congestion control and link-layer bit-rate adaptation resulting in severely reduced network efficiency even over short wireless paths ($< 6$ hops). However, bit-rate adaptation improves fairness across TCP flows. The same principal observations hold for hybrid wireless/wireline paths. To investigate approaches to improve TCP performance, we present a simple model that captures the cause for the inefficiency of TCP over autorate links. We then examine several techniques at both the TCP level and the link layer (TCP Vegas, clamping, limiting the buffer size at the wireless routers) to alleviate contention. None of these techniques works for all scenarios, but the simple approach to limit the buffer size is attractive in many settings that include four or more wireless hops. [pdf]
    
    
35. Gerald Wagenknecht, Markus Anwander, Torsten Braun, Thomas Staub, James Matheka, Simon Morgenthaler   [WagenknechtAEBSMM:08]   [published]
    MARWIS: A Management Architecture for Heterogeneous Wireless Sensor Networks    
    6th International Conference on Wired/Wireless Internet Communications (WWIC'08) , Tampere, 28-30 May 08
    In this paper we present a new management architecture for heterogeneous wireless sensor networks (WSNs) called MARWIS. It supports common management tasks such as monitoring, (re)configuration, and updating program code in a WSN and considers specific characteristics of WSNs and restricted physical resources of the nodes such as battery, computing power, memory or network bandwidth and link quality. To handle large heterogeneous WSN we propose to subdivide it into smaller sensor subnetworks (SSNs), which contains sensor node of one type. A wireless mesh network (WMN) operates as backbone and builds the communication gateway between these SSNs. We show that the packet loss and the round trip time are decreased significantly in such an architecture. The mesh nodes operate also as a communication gateway between the different SSNs and perform the management tasks. All management tasks are controlled by a management station located in the Internet. [pdf]
    
    
36. Lochmatter, Thomas; Raemy, Xavier; Matthey, Loïc; Indra, Saurabh; Martinoli, Alcherio   [LochmatterRMIM:08]   [published]
    A Comparison of Casting and Spiraling Algorithms for Odor Source Localization in Laminar Flow    
    2008 IEEE International Conference on Robotics and Automation; Pasadena, California, May 19-23, 2008, p. 1138-1143
    We compare two well-known algorithms for locating odor sources in environments with a main wind flow. Their plume tracking performance is tested through systematic experiments with real robots in a wind tunnel under laminar flow condition. We present the system setup and show the wind and odor profiles. The results are then compared in terms of time and distance to reach the source, as well as speed in upwind direction. We conclude that the spiral- surge algorithm yields significantly better results than the casting algorithm, and discuss possible rationales behind this performance difference.
    
    
37. Krishnendu Chatterjee, Rupak Majumdar, and Thomas A. Henzinger   [ChatterjeeMH:08]   [published]
    Controller Synthesis with Budget Constraints    
    International Workshop on Hybrid Systems: Computation and Control (HSCC), St Louis, 22-24 Apr 08
    We study the controller synthesis problem under budget constraints. In this problem, there is a cost associated with making an observation, and a controller can make only a limited number of observations in each round so that the total cost of the observations does not exceed a given fixed budget. The controller must ensure some omega-regular requirement subject to the budget constraint. Budget constraints arise in designing and implementing controllers for resource-constrained embedded systems, where a controller may not have enough power, time, or bandwidth to obtain data from all sensors in each round. They lead to games of imperfect information, where the unknown information is not fixed a priori, but can vary from round to round, based on the choices made by the controller how to allocate its budget. We show that the budget-constrained synthesis problem for omega-regular objectives is complete for exponential time. In addition to studying synthesis under a fixed budget constraint, we study the budget optimization problem, where given a plant, an objective, and observation costs, we have to find a controller that achieves the objective with minimal average cost (or minimal peak cost). We show that this problem is reducible to a game of imperfect information where the winning objective is a conjunction of an omega-regular condition and a long-run average condition (or a least max-cost condition), and this again leads to an exponential-time algorithm. Finally, we extend our results to games over infinite state spaces, and show that the budget-constrained synthesis problem is decidable for infinite-state games with stable quotients of finite index. Consequently, the discrete-time budget-constrained synthesis problem is decidable for rectangular hybrid automata.
    
    
38. Susanne Cech Previtali and Thomas R. Gross   [PrevitaliG:08]   [published]
    Extracting Updating Aspects from Version Differences    
    4th International Linking Aspect Technology and Evolution workshop (LATE'08), Brussels, 1 Apr 08
    Dynamic software evolution represents a viable technique to update software systems at run-time. On-the-fly updating is particularly helpful for systems that must be continuously available and up-to-date. Updates consist of several incremental changes that must be applied to a system. These individual changes exhibit symptoms similar to crosscutting concerns: they are typically scattered across several classes. We therefore leverage aspect technology and use aspects to encapsulate the changes constituting an update. In addition, dynamic aspect systems can serve as a practicable platform to inject updates at run-time. In this paper, we present how we extract the updating aspects for a dynamic aspect system. We detail the algorithms necessary to generate such updating aspects that rely on the computation of the dependences between the changes to determine the granularity of an aspect. [pdf]
    
    
39. Krishnendu Chatterjee, Arkadeb Ghosal, Thomas A. Henzinger, Daniel Iercan, Christoph M. Kirsch, Claudio Pinello, and Alberto Sangiovanni-Vincentelli   [ChatterjeeGHIKPS:08]   [published]
    Logical Reliability of Interacting Real-Time Tasks    
    International Conference on Design, Automation, and Test in Europe (DATE), Munich, 10-14 Mar 08
    We propose the notion of logical reliability for real-time program tasks that interact through periodically updated program variables. We describe a reliability analysis that checks if the given short-term (e.g., single-period) reliability of a program variable update in an implementation is sufficient to meet the logical reliability requirement (of the program variable) in the long run. We then present a notion of design by refinement where a task can be refined by another task that writes to program variables with less logical reliability. The resulting analysis can be combined with an incremental schedulability analysis for interacting real-time tasks proposed earlier for the Hierarchical Timing Language (HTL), a coordination language for distributed real-time systems. We implemented a logical-reliability-enhanced prototype of the compiler and runtime infrastructure for HTL.
    
    
40. Cianci, Christopher M.; Lochmatter, Thomas; Pugh, Jim; Martinoli, Alcherio   [CianciLPM:07]   [published]
    Toward Multi-Level Modeling of Robotic Sensor Networks: A Case Study in Acoustic Event Monitoring    
    International Conference on Robot Communication and Coordination (ROBOCOMM); Athens, Greece, October 15-17, 2007, p. 1-8
    Modeling and simulation can be powerful tools for analyzing multi-agent systems, such as networked robotic systems and sensor networks. In this paper, it is shown concretely how instances of both these elements fit into a general methodology for multi-level modeling, providing insight into system dynamics. Use of the resulting general framework is illustrated through application to a specific sample case study involving a robotic wireless sensor network engaged in an acoustic detection task. We then compare and contrast the resulting family of models, highlighting explicitly the trade-off between realism and simplicity.
    
    
41. Thomas Locher, Remo Meier, Stefan Schmid, and Roger Wattenhofer   [LocherMSW:07]   [published]
    Push-to-Pull Peer-to-Peer Live Streaming     
    21st International Symposium on Distributed Computing (DISC), Lemesos, 24-26 Sep 07
    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 faces, e.g., the need to meet real-time playback deadlines, or the increased demands on robustness under churn. This paper presents and evaluates novel neighbor selection and data distribution schemes for peer-to-peer live streaming. Concretely, in order to distribute data efficiently and with minimal delay, our algorithms combine low-latency push operations along a structured overlay with the flexibility of pull operations. The protocols ensure that all peers are able to obtain the required data blocks of a live stream in time, and that due to the loop-free dissemination paths, the overhead is low. [pdf]
    
    
42. Thomas Locher, Stefan Schmid, and Roger Wattenhofer.   [LocherSW:07]   [published]
    Rescuing Tit-for-Tat with Source Coding     
    7th IEEE International Conference on Peer-to-Peer Computing (P2P), Galway, 2-5 Sep 07
    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 environments such as peer-topeer networks is marginal, as peers can rapidly end up in a deadlock situation. Many proposed solutions to this problem are either less resilient to freeloading behavior or induce a computational overhead that cannot be sustained by regular peers. In contrast, we retain tit-fortat, but enhance the system with a novel form of source coding and an effective scheme to prevent peers from freeloading from seeding peers. We show that our system performs well without the risk of peer starvation and without sacrificing fairness. The proposed solution has a reasonably low overhead, and may hence be suitable for fully distributed content distribution applications in real networks. [pdf]
    
    
43. Krishnendu Chatterjee, Thomas Henzinger and Nir Piterman   [ChatterjeeHP:07b]   [published]
    Strategy Logic    
    Conference on Concurrency Theory (CONCUR), Lisbon, 3-8 Sep 07
    We introduce strategy logic, a logic that treats strategies in two-player games as explicit first-order objects. The explicit treatment of strategies allows us to specify properties of nonzero-sum games in a simple and natural way. We show that the one-alternation fragment of strategy logic is strong enough to express the existence of Nash equilibria and secure equilibria, and subsumes other logics that were introduced to reason about games, such as ATL, ATL*, and game logic. We show that strategy logic is decidable, by constructing tree automata that recognize sets of strategies. While for the general logic, our decision procedure is nonelementary, for the simple fragment that is used above we show that the complexity is polynomial in the size of the game graph and optimal in the size of the formula (ranging from polynomial to 2EXPTIME depending on the form of the formula). [pdf]
    
    
44. Stephanie Balzer, Thomas R. Gross, Patrick Eugster   [BalzerGE:07]   [published]
    A Relational Model of Object Collaborations and its Use in Reasoning about Relationships    
    21st European Conference on Object-Oriented Programming (ECOOP'07), Berlin, 30.7-3.8.07
    Understanding the \emph{collaborations} that exist between the instances of classes in an object-oriented program is difficult: the collaborations are expressed through \emph{references} and consequently are often buried in the implementation. Relationships have been proposed as a programming language construct to allow an explicit representation of these object collaborations. This paper introduces a model that uses \emph{mathematical relations} as an abstraction of relationships. The notion of a relation allows us to link programs composed of classes \emph{and} relationships to discrete mathematics and to specify their behavior in terms of the properties of their mathematical abstractions. The specification of such programs relies in particular on \emph{member interposition} (facilitates the declaration of relationship-dependent members of classes) and on \emph{relationship invariants} (facilitate the declaration of the consistency constraints imposed on object collaborations). This model then allows not only the representation of object collaborations but also provides a foundation to reason about these collaborations. Throughout the paper, we employ a set-oriented view of the specification of programs composed of classes and relationships. This view notably influences the design of any programming language that allows the programmer to express specifications as introduced in this paper.
    
    
45. Stephanie Balzer, Thomas R. Gross   [BalzerG:07b]   [published]
    Member Interposition: How Roles Can Define Class Members    
    2nd Workshop on Roles and Relationships in Object Oriented Programming, Multiagent Systems, and Ontologies (Roles 2007), Berlin, 30-31 July 07
    Explicit relationships are a means to make the collaborations that arise between objects explicit. In previous work, we introduce a mathematical model that fosters the specification of such relationships. The model relies in particular on member interposition, a mechanism that facilitates the specification of relationship-dependent members of classes. In this position paper we highlight the interdependence between relationships and role models and introduce generic relationships, an extension to support explicit roles.
    
    
46. Markus Anwander, Gerald Wagenknecht, Thomas Staub, and Torsten Braun   [AnwanderWSB:07]   [published]
    Management of Heterogeneous Wireless Sensor Networks    
    6. GI/ITG KuVS Fachgespräch "Drahtlose Sensornetze", Aachen, 16-17 July 07
    Wireless sensor networks (WSNs) are taking a big step forward to productive deployments. Heterogeneous WSNs are gaining importance. Complex problem settings consisting of different environmental conditions require specific sensor nodes for the individual tasks resulting in heterogeneous networks. As the different types of sensor nodes may be incompatible, a more general management architecture for these heterogeneous environments is a necessity. Individual nodes have to be reconfigured and updated during their lifetime. Our WSN management framework supports common management tasks such as monitoring the WSN, configuration of the WSN, code updates, and managing sensor data. Our management architecture consists of the following infra-structural elements: a management station, a number of management nodes and a high number of heterogeneous sensor nodes. All management tasks are controlled by the management station. Management nodes are implemented as wireless mesh nodes.
    
    
47. Thomas Brihaye, Thomas Henzinger, Vinayak Prabhu and Jean-Francois Raskin   [BrihayeHPR:07]   [published]
    Minimum-Time Reachability in Timed Games    
    International Colloquium on Automata, Languages, and Programming (ICALP), Wroclaw, 9-13 Jul 07
    We consider the minimum-time reachability problem in concurrent two-player timed automaton game structures. We show how to compute the minimum time needed by a player to reach a target location against all possible choices of the opponent. We do not put any syntactic restriction on the game structure, nor do we require any player to guarantee time divergence. We only require players to use receptive strategies which do not block time. The minimal time is computed in part using a fixpoint expression, which we show can be evaluated on equivalence classes of a non-trivial extension of the clock-region equivalence relation for timed automata. [pdf]
    
    
48. Beyer, Dirk; Henzinger, Thomas A.; Théoduloz, Grégory   [BeyerHT:07]   [published]
    Configurable Software Verification: Concretizing the Convergence of Model Checking and Program Analysis    
    Computer Aided Verification; Berlin, Germany, July 3-7, 2007, p. 504-518
    In automatic software verification, we have observed a theoretical convergence of model checking and program analysis. In practice, however, model checkers are still mostly concerned with precision, e.g., the removal of spurious counterexamples; for this purpose they build and refine reachability trees. Lattice-based program analyzers, on the other hand, are primarily concerned with efficiency. We designed an algorithm and built a tool that can be configured to perform not only a purely tree-based or a purely lattice-based analysis, but offers many intermediate settings that have not been evaluated before. The algorithm and tool take one or more abstract interpreters, such as a predicate abstraction and a shape analysis, and configure their execution and interaction using several parameters. Our experiments show that such customization may lead to dramatic improvements in the precision-efficiency spectrum.
    
    
49. Dirk Beyer, Thomas Henzinger and Vasu Singh   [BeyerHS:07]   [published]
    Algorithms for Interface Synthesis (invited tutorial)    
    19th Int. Conf. on Computer-Aided Verification (CAV), Berlin, 3-7 Jul 07
    A temporal interface for a software component is a finite automaton that specifies the legal sequences of calls to functions that are provided by the component. We compare and evaluate three different algorithms for automatically extracting temporal interfaces from program code: (1) a game algorithm that computes the interface as a representation of the most general environment strategy to avoid a safety violation; (2) a learning algorithm that repeatedly queries the program to construct the minimal interface automaton; and (3) a CEGAR algorithm that iteratively refines an abstract interface hypothesis by adding relevant program variables. For comparison purposes, we present and implement the three algorithms in a unifying formal setting. While the three algorithms compute the same output and have similar worst-case complexities, their actual running times may differ considerably for a given input program. On the theoretical side, we provide for each of the three algorithms a family of input programs on which that algorithm outperforms the two alternatives. On the practical side, we evaluate the three algorithms experimentally on a variety of Java libraries. [pdf]
    
    
50. Marc Heissenbüttel, Torsten Braun, Markus Waelchli, Thomas Bernoulli   [HeissenbüttelBWB:07]   [published]
    Evaluating the Limitations of and Alternatives in Beaconing    
    Ad-Hoc Networks (Elsevier), Volume 5, Issue 5, July 2007
    In position-based routing protocols, each node periodically transmits a short hello message (called beacon) to announce its presence and position. Receiving nodes list all known neighbor nodes with their position in the neighbor table and remove entries after they have failed to receive a beacon for a certain time from the corre- sponding node. In highly dynamic networks, the information stored in the neighbor table is often outdated and does no longer re°ect the actual topology of the net- work causing retransmissions and rerouting that consume bandwidth and increase latency. An analysis on the possible impact of beacons due outdated and inaccu- rate neighbor tables is needed. We quantify by analytical and simulation means the possible performance loss and explore the limitations of position-based routing protocols which use beaconing. In highly mobile ad-hoc networks, the delay can in- crease by a factor of 20. The neighbor table inaccuracy is the main source of packet loss in uncongested networks.We propose and evaluate several concrete mechanisms to improve the accuracy of neighborhood information, e.g., by dynamic adaptation of the timer values when beacons are broadcasted, and show their e®ectiveness by extensive simulation. [pdf]
    
    
51. Florian T. Schneider, Mathias Payer, Thomas Gross   [SchneiderPG:07]   [published]
    Online Optimizations Driven by Hardware Performance Monitoring    
    Conference on Programming Language Design and Implementation (PLDI 2007), San Diego, 10-13 June 07
    Hardware performance monitors provide detailed direct feedback about application behavior and are an additional source of information that a compiler may use for optimization. A JIT compiler is in a good position to make use of such information because it is running on the same platform as the user applications. As hardware platforms become more and more complex, it becomes more and more difficult to model their behavior. Profile information that captures general program properties (like execution frequency of methods or basic blocks) may be useful, but does not capture sufficient information about the execution platform. Machine-level performance data obtained from a hardware performance monitor can not only direct the compiler to those parts of the program that deserve its attention but also determine if an optimization step actually improved the performance of the application. This paper presents an infrastructure based on a dynamic compiler+runtime environment for Java that incorporates machine-level information as an additional kind of feedback for the compiler and runtime environment. The low-overhead monitoring system provides fine-grained performance data that can be tracked back to individual Java bytecode instructions. As an example, the paper presents results for object co-allocation in a generational garbage collector that optimizes spatial locality of objects on-line using measurements about cache misses. In the best case, the execution time is reduced by 14\% and L1 cache misses by 28\%. [pdf]
    
    
52. Fabian Kuhn, Thomas Locher, and Roger Wattenhofer   [KuhnLW:07]   [published]
    Tight Bounds for Distributed Selection    
    19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, 9-11 June 07
    
    
    
53. Thomas Staub, Daniel Balsiger, Michael Lustenberger, Torsten Braun   [StaubBLB:07]   [published]
    Secure Remote Management and Software Distribution for Wireless Mesh Networks    
    7th International Workshop on Applications and Services in Wireless Networks (ASWN 2007) , Santander, 24 - 26 May 07
    Wireless mesh networks (WMN) are usually spread over large physical areas. They can include node locations that are difficult to reach, e.g., roof tops. Physical access to certain nodes can even be unfeasible depending on bureaucratic or technical problems. During the life time of a WMN it is necessary to process reconfigurations and software updates. Configuration errors and faulty software updates may then destroy the access to individual nodes. Costly on-site reconfiguration is required. We propose a secure management architecture for WMNs handling configuration errors as well as faulty software updates and avoiding on-site repairs. The architecture is tailored to productive and extensive testbed networks, in which reconfiguration is even more frequent. It is a fully distributed management solution and provides fallback solutions for configuration errors, and kernel panics. The paper presents our architecture and its implementation including the Linux image, the development system and the management console. [pdf]
    
    
54. Thomas Moscibroda, Yvonne Anne Oswald, and Roger Wattenhofer   [MoscibrodaOW:07]   [published]
    How Optimal are Wireless Scheduling Protocols    
    Infocom 2007, Anchorage, 6-12 May 07
    
    
    
55. Val Naumov, Thomas Gross   [NaumovG:07]   [published]
    Connectivity-Aware Routing (CAR) in Vehicular Ad Hoc Networks    
    Infocom 2007, Anchorage, 6-12 May 07
    
    
    
56. Martin Hell, Thomas Johansson, Willi Meier   [HellJM:07]   [published]
    Grain: a stream cipher for constrained environments    
    International Journal of Wireless and Mobile Computing, 2007, Vol. 2, No.1
    A new stream cipher, Grain, is proposed. The design targets hardware environments where gate count, power consumption and memory is very limited. It is based on two shift registers and a non-linear output function. The cipher has the additional feature that the speed can be increased at the expense of extra hardware. The key size is 80 bits and no attack faster than exhaustive key search has been identified. The hardware complexity and throughput compares favorably to other hardware oriented stream ciphers like E0 and A5/1.
    
    
57. K. Chatterjee, T.A. Henzinger, and N. Piterman   [ChatterjeeHP:07]   [published]
    Generalized Parity Games    
    10th International Conference on Foundations of Software Science and Computation Structures, Braga, 24 Mar - 1 Apr 07
    We consider games where the winning conditions are disjunctions (or dually, conjunctions) of parity conditions; we call them \emph{generalized} parity games. These winning conditions, while $\omega$-regular, arise naturally when considering fair simulation between parity automata, secure equilibria for parity conditions, and determinization of Rabin automata. We show that these games retain the computational complexity of Rabin and Streett conditions; i.e., they are NP-complete and co-NP-complete, respectively. The (co-)NP-hardness is proved for the special case of a conjunction/disjunction of two parity conditions, which is the case that arises in fair simulation and secure equilibria. However, considering these games as Rabin or Streett games is not optimal. We give an exposition of Zielonka's algorithm when specialized to this kind of games. The complexity of solving these games for $k$ parity objectives with $d$ priorities, $n$ states, and $m$ edges is $O(n^{2 k d} \cdot m) \cdot \frac{(k\cdot d)!}{d!^k}$, as compared to $O(n^{2 k d} \cdot m) \cdot (k\cdot d)!$ when these games are solved as Rabin/Streett games. We also extend the subexponential algorithm for solving parity games recently introduced by Jurdzi{\'n}ski, Paterson, and Zwick to generalized parity games. The resulting complexity of solving generalized parity games is $n^{O(\sqrt{n})} \cdot \frac{(k\cdot d)!}{d!^k}$. As a corollary we obtain an improved algorithm for Rabin and Streett games with $d$ pairs, with time complexity $n^{O(\sqrt{n})} \cdot d!$.
    
    
58. Krishnendu Chatterjee and Thomas Henzinger   [ChatterjeeH:07]   [published]
    Assume-Guarantee Synthesis    
    Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), Braga, 24.3-1.4.07
    The classical synthesis problem for reactive systems asks, given a proponent process A and an opponent process B, to refine A so that the closed-loop system A||B satisfies a given specification p. The solution of this problem requires the computation of a winning strategy for proponent A in a game against opponent B. We define and study the co-synthesis problem, where the proponent A consists itself of two independent processes, A=A1||A2, with specifications p1and p2, and the goal is to refine both A1 and A2 so that A1||A2||B satisfies p1∧p2. For example, if the opponent B is a fair scheduler for the two processes A1 and A2, and p-i specifies the requirements of mutual exclusion for A-i (e.g., starvation freedom), then the co-synthesis problem asks for the automatic synthesis of a mutual-exclusion protocol. We show that co-synthesis defined classically, with the processes A1 and A2 either collaborating or competing, does not capture desirable solutions. Instead, the proper formulation of co-synthesis is the one where process A1 competes with A2 but not at the price of violating p1, and vice versa. We call this assume-guarantee synthesis and show that it can be solved by computing secure-equilibrium strategies. In particular, from mutual-exclusion requirements the assume-guarantee synthesis algorithm automatically computes Peterson's protocol. [pdf]
    
    
59. Lochmatter, Thomas; Raemy, Xavier; Martinoli, Alcherio   [LochmatterRM:07b]   [published]
    Geruchslokalisation mit mobilen Robotern    
    IT Business, num. 1 (2007), p. 40-41
    Hunde werden aufgrund ihrer exzellenten Nase oft zur Suche von Minen, Bomben, Drogen oder verschütteten Menschen eingesetzt. Mit elektronischen Geruchssensoren könnten für solche Anwendungen bald auch mobile Roboter zum Einsatz kommen. Neben guten Geruchssensoren und passenden Robotern sind aber auch entsprechende Suchalgorithmen notwendig - und die komplexe Ausbreitung von Rauch und Duftmolekülen in der Luft macht die Suche nach Geruchsquellen zu einer grossen Herausforderung. [pdf]
    
    
60. Markus Wälchli, Thomas Bernoulli and Torsten Braun   [WälchliBB:07]   [published]
    Receiver-based Backbone Construction and Maintenance for Wireless Sensor or Multi-Hop Networks    
    4th International Workshop on Mobile Ad-Hoc Networks (WMAN'07), Bern, 26 Feb - 2 Mar 07
    Energy savings and topology control are needed tasks of many sensor network applications. Sensors are assumed to be randomly deployed and shall organize themselves independently after deployment. Moreover, sensor networks shall operate as long as possible warranting network connectivity. To support these tasks we propose the maintenance of a virtual backbone. Nodes not participating in the backbone shutdown their radios and go to sleep for a certain time. The backbone nodes are adaptively altered according to the current network conditions. The backbone thus is able to deal with node failures and/or movements. The non-backbone nodes follow long sleep cycles during which they frequently wake up to check the network conditions. After a long sleep period the backbone is reestablished by the base station. The algorithm shows good performance approximating the minimum number of nodes in the backbone possible for the initial backbone setups as well as the ability to repair link breaks on demand with short delays and low message overhead. [pdf]
    
    
61. Lochmatter, Thomas; Raemy, Xavier; Martinoli, Alcherio   [LochmatterRM:07]   [published]
    Odor Source Localization with Mobile Robots    
    Bulletin of the Swiss Society for Automatic Control, num. 46 (2007), p. 11-14
    Because of their excellent olfactory sense, dogs are often used to find bombs, mines, drugs, or people buried by avalanches. For such applications, autonomous mobile robots could be used in the future. Electronic sensors already exist for a wide variety of substances, and are still being actively researched. Mobile robots are an important area of research, too. But beyond a good sensor and a suitable robotic platform, a third component is required: odor source localization algorithms – and due to the complex propagation of odor molecules in the air, tracking down odor sources is still a big challenge. [pdf]
    
    
62. Matthias Dyer, Jan Beutel, Lothar Thiele, Thomas Kalt, Patrice Oehen, Kevin Martin, Philipp Blum   [DyerBTKOMB:07]   [published]
    Deployment Support Network - A Toolkit for the Development of WSNs    
    4th European Conference on Wireless Sensor Networks (EWSN'07), Delft, 29-31 Jan 07
    In this paper, we present the Deployment Support Network (DSN), a new methodology for developing and testing wireless sensor networks (WSN) in a realistic environment. With an additional wireless backbone network a deployed WSN can be observed, controlled, and reprogrammed completely over the air. The DSN provides visibility and control in a similar way as existing emulation testbeds, but overcomes the limitations of wired infrastructures. As a result, development and experiments can be conducted with realistic in- and outdoor deployments. The paper describes the new concept and methodology. Additionally, an architecture-independent implementation of the toolkit is presented, which has been used in an industrial case-study. [pdf]
    
    
63. Thomas A. Henzinger   [Henzinger:07]   [published]
    Games, Time, and Probability: Graph Models for System Design and Analysis    
    33rd International Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, 20-26 Jan 07
    Digital technology is increasingly deployed in safety-critical situations. This calls for systematic design and verification methodologies that can cope with three major sources of system complexity: concurrency, real time, and uncertainty. We advocate a two-step process: formal modeling followed by algorithmic analysis (or, "model building" followed by "model checking"). We model the concurrent components of a reactive system as potential collaborators or adversaries in a multi-player game with temporal objectives, such as system safety. The real-time aspect of embedded systems requires models that combine discrete state transitions and continuous state evolutions. Uncertainty in the environment is naturally modeled by probabilistic state changes. As a result, we obtain three orthogonal extensions of the basic state-transition graph model for reactive systems --game graphs, timed graphs, and stochastic graphs-- as well as combinations thereof. In this short text, we provide a uniform exposition of the underlying definitions. For verification algorithms, we refer the reader to the literature.
    
    
64. Thomas Moscibroda, Roger Wattenhofer, and Yves Weber   [MoscibrodaWW:06]   [published]
    Protocol Design Beyond Graph-Based Models    
    5th Workshop on Hot Topics in Networks (HotNets), Irvine, 29-30 Nov 06
    
    
    
65. Arkadeb Ghosal, Thomas A. Henzinger, Christoph M. Kirsch, Daniel Iercan, and Alberto Sangiovanni-Vincentelli   [GhosalHKIS:06]   [published]
    A Hierarchical Coordination Language for Interacting Real-Time Tasks    
    Sixth Annual Conference on Embedded Software, Seoul, 22-25 Oct 06
    We designed and implemented a new programming language called Hierarchical Timing Language (HTL) for hard real-time systems. Critical timing constraints are specified within the language, and ensured by the compiler. Programs in HTL are extensible in two dimensions without changing their timing behavior: new program modules can be added, and individual program tasks can be refined. The mechanism supporting time invariance under parallel composition is that different program modules communicate at specified instances of time. Time invariance under refinement is achieved by conservative scheduling of the top level. HTL is a coordination language, in that individual tasks can be implemented in "foreign" languages. As a case study, we present a distributed HTL implementation of an automotive steer-by-wire controller.
    
    
66. Thomas Locher, Stefan Schmid, and Roger Wattenhofer   [LocherSW:06]   [published]
    eQuus: A Provably Robust and Locality-Aware Peer-to-Peer System    
    6th IEEE International Conference on Peer-to-Peer Computing (P2P), Cambridge, 2-4 Oct 06
    
    
    
67. Susanne Cech Previtali, Thomas R. Gross   [PrevitaliG:06]   [published]
    Dynamic Updating of Software Systems Based on Aspects    
    22nd IEEE International Conference on Software Maintenance (ICSM'06), Philadelphia, 24-27 Sep 06
    Long-running applications such as network services require continuous uptime but also frequent changes to the software. To avoid downtime for software maintenance, applications must be updated at run-time. We describe a system based on the ideas of aspect-oriented programming (AOP) to manage such updates. Join points as defined by AOP establish locations for code modification in a program. We use these join points to guide software updates. Updating a system is a two-step process: the original (old) and new (updated) versions of a software system are compared and a list of update actions and pointcuts is constructed. We present a case-study to evaluate the applicability of this approach. [pdf]
    
    
68. Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, and Jean-Francois Raskin   [ChatterjeeDHR:06]   [published]
    Algorithms for Omega-regular Games with Imperfect Information    
    International Conference for Computer Science Logic, Szeged, 25-29 Sep 06
    We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller that does not see the private state of the plant. Our main results are twofold. First, we give a fixed-point algorithm for computing the set of states from which a player can win with a deterministic observation-based strategy for any omega-regular objective. The fixed point is computed in the lattice of antichains of state sets. This algorithm has the advantages of being directed by the objective and of avoiding an explicit subset construction on the game graph. Second, we give an algorithm for computing the set of states from which a player can win with probability 1 with a randomized observation-based strategy for a Buchi objective. This set is of interest because in the absence of perfect information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds.
    
    
69. Thomas A. Henzinger and Nir Piterman   [HenzingerP:06]   [published]
    Solving Games without Determinization    
    International Conference for Computer Science Logic, Szeged, 25-29 Sep 06
    The synthesis of reactive systems requires the solution of two-player games on graphs with omega-regular objectives. When the objective is specified by a linear temporal logic formula or nondeterministic Buchi automaton, then previous algorithms for solving the game require the construction of an equivalent deterministic automaton. However, determinization for automata on infinite words is extremely complicated, and current implementations fail to produce deterministic automata even for relatively small inputs. We show how to construct, from a given nondeterministic Buchi automaton, an equivalent nondeterministic parity automaton N that is good for solving games with objective N. The main insight is that a nondeterministic automaton is good for solving games if it fairly simulates the equivalent deterministic automaton. In this way, we omit the determinization step in game solving and reactive synthesis. The fact that our automata are nondeterministic makes them surprisingly simple, amenable to symbolic implementation, and allows an incremental search for winning strategies.
    
    
70. Thomas A. Henzinger and Vinayak Prabhu   [HenzingerP:06b]   [published]
    Timed Alternating-Time Temporal Logic    
    Fourth International Conference on Formal Modeling and Analysis of Timed Systems, Paris, 25-27 Sep 06
    We add freeze quantifiers to the game logic ATL in order to specify real-time objectives for games played on timed structures. We define the semantics of the resulting logic TATL by restricting the players to physically meaningful strategies, which do not prevent time from diverging. We show that TATL can be model checked over timed automaton games. We also specify timed optimization problems for physically meaningful strategies, and we show that for timed automaton games, the optimal answers can be approximated to within any degree of precision.
    
    
71. Thomas Locher and Roger Wattenhofer   [LocherW:06]   [published]
    Oblivious Gradient Clock Synchronization    
    20th International Symposium on Distributed Computing (DISC), Stockholm, 18-20 Sep 06
    
    
    
72. Krishnendu Chatterjee, Luca de Alfaro, and Thomas A. Henzinger   [ChatterjeeAH:06]   [published]
    Strategy Improvement for Concurrent Reachability Games    
    Third Annual Conference on Quantitative Evaluation of Systems, UC Riverside, 11-14 Sep 06
    A concurrent reachability game is a two-player game played on a graph: at each state, the players simultaneously and independently select moves; the two moves determine jointly a probability distribution over the successor states. The objective for player 1 consists in reaching a set of target states; the objective for player 2 is to prevent this, so that the game is zero-sum. Our contributions are two-fold. First, we present a simple proof of the fact that in concurrent reachability games, for all ε>0, memoryless ε-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an ε-optimal strategy achieves the objective with probability within ε of the value of the game. In contrast to previous proofs of this fact, which rely on the limit behavior of discounted games using advanced Puisieux series analysis, our proof is elementary and combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration) algorithm for concurrent games with reachability objectives.
    
    
73. Krishnendu Chatterjee, Luca de Alfaro, Marco Faella, Thomas A. Henzinger, Rupak Majumdar, and Marielle Stoelinga   [ChatterjeeAFHMS:06]   [published]
    Compositional Quantitative Reasoning    
    Third Annual Conference on Quantitative Evaluation of Systems, UC Riverside, 11-14 Sep 06
    We present a compositional theory of system verification, where specifications assign real-numbered costs to systems. These costs can express a wide variety of quantitative system properties, such as resource consumption, price, or a measure of how well a system satisfies its specification. The theory supports the composition of systems and specifications, and the hiding of variables. Boolean refinement relations are replaced by real-numbered distances between descriptions of a system at different levels of detail. We show that the classical boolean rules for compositional reasoning have quantitative counterparts in our setting. While our general theory allows costs to be specified by arbitrary cost functions, we also consider a class of linear cost functions, which give rise to an instance of our framework where all operations are computable in polynomial time.
    
    
74. Thomas A. Henzinger and Joseph Sifakis   [HenzingerS:06]   [published]
    The embedded systems design challenge    
    14th International Symposium on Formal Methods, Hamilton, 21-27 Aug 06
    We summarize some current trends in embedded systems design and point out some of their characteristics, such as the chasm between analytical and computational models, and the gap between safety-critical and best-effort engineering practices. We call for a coherent scientific foundation for embedded systems design, and we discuss a few key demands on such a foundation: the need for encompassing several manifestations of heterogeneity, and the need for constructivity in design. We believe that the development of a satisfactory Embedded Systems Design Science provides a timely challenge and opportunity for reinvigorating computer science.
    
    
75. Beyer, Dirk; Henzinger, Thomas A.; Théoduloz, Grégory   [BeyerHT:06]   [published]
    Lazy Shape Analysis    
    Computer Aided Verification; Seattle, WA, USA, August 16-20, 2006, p. 532-546
    Many software model checkers are based on predicate abstraction. If the verification goal depends on pointer structures, the approach does not work well, because it is difficult to find adequate predicate abstractions for the heap. In contrast, shape analysis, which uses graph-based heap abstractions, can provide a compact representation of recursive data structures. We integrate shape analysis into the software model checker BLAST. Because shape analysis is expensive, we do not apply it globally. Instead, we ensure that, like predicates, shape graphs are computed and stored locally, only where necessary for proving the verification goal. To achieve this, we extend lazy abstraction refinement, which so far has been used only for predicate abstractions, to three-valued logical structures. This approach does not only increase the precision of model checking, but it also increases the efficiency of shape analysis. We implemented the technique by extending BLAST with calls to TVLA. [pdf]
    
    
76. Thomas Moscibroda, Stefan Schmid, and Roger Wattenhofer   [MoscibrodaSW:06b]   [published]
    When Selfish Meets Evil: Byzantine Players in a Virus Inoculation Game    
    25th Annual Symposium on Principles of Distributed Computing (PODC), Denver, 23-26 July 06
    
    
    
77. Thomas Moscibroda   [Moscibroda:06]   [published]
    Locality, Scheduling, and Selfishness: Algorithmic Foundations of Highly Decentralized Networks    
    PhD thesis ETH Zurich No. 16740 (Prof. R. Wattenhofer)
    
    
    
78. Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer   [KuhnMW:06b]   [published]
    Fault-Tolerant Clustering in Ad Hoc and Sensor Networks    
    26th International Conference on Distributed Computing Systems (ICDCS), Lisboa, 4-7 July 2006
    
    
    
79. Thomas Staub, Thomas Bernoulli, Markus Anwander , Markus Waelchli and Torsten Braun   [StaubBAEWB:06]   [published]
    Experimental Lifetime Evaluation for MAC Protocols on Real Sensor Hardware    
    ACM Workshop on Real-World Wireless Sensor Networks (REALWSN'06), Uppsala, 19 June 06
    In this paper we present our experimental lifetime measurements for two implementations of MAC protocols designed for wireless sensor networks. We have implemented the TDMA based LMAC and the contention-based TEEM on the ESB nodes developed at FU Berlin. We show the energy requirements of these protocols on the respective hardware and also present figures for the trade off between robustness and energy consumption of these protocols. The main contribution of this paper consists in real world measurements giving an idea of energy conserving MAC protocols' potential to extend node lifetime.
    
    
80. Marc Heissenbüttel, Torsten Braun, David Jörg, Thomas Huber   [HeissenbüttelBJH:06]   [published]
    A Framework for Routing in Large Ad-hoc Networks with Irregular Topologies    
    International Journal of Ad Hoc & Sensor Wireless Networks (AHSWN), Volume 2, Number 2, June 2006
    In this paper, we consider routing in large wireless multihop networks with possibly irregular topologies. Existing position-based routing pro- tocols have de¯ciencies in such scenarios as they always forward pack- ets directly towards the destination. This greedy routing frequently fails and costly recovery mechanisms have to be applied. We propose the Ants-based Mobile Routing Architecture (AMRA) for optimized routing, which combines position-based routing, topology abstraction, and swarm intelligence. AMRA routes packets along paths with high connectivity and short delays by memorizing past tra±c and by using ant-like pack- ets to discover shorter paths. The geographic topology abstraction allows AMRA to cope with high mobility and large networks. Simulative eval- uation indicate that AMRA ¯nds signi¯cantly shorter paths with only marginal overhead compared to other position-based routing protocols.
    
    
81. Thomas Moscibroda, Roger Wattenhofer, Aaron Zollinger   [MoscibrodaWZ:06]   [published]
    Topology Control Meets SINR: The Scheduling Complexity of Arbitrary Topologies    
    7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Florence, 22-25 May 2006
    
    
    
82. Valery Naumov, Rainer Baumann, Thomas Gross    [NaumovBG:06]   [published]
    An Evaluation of Inter-Vehicle Ad Hoc Networks on Realistic Vehicular Traces    
    7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Florence, 22-25 May 2006
    Vehicular ad hoc networks (VANETs) using WLAN technology have recently received considerable attention. The evaluation of VANET routing protocols often involves simulators since management and operation of a large number of real vehicular nodes is expensive. We study the behavior of routing protocols in VANETs by using mobility information obtained from a microscopic vehicular traffic simulator that is based on the on the real road maps of Switzerland. The performance of AODV and GPSR is significantly influenced by the choice of mobility model, and we observe a significantly reduced packet delivery ratio when employing the realistic traffic simulator to control mobility of nodes. To address the performance limitations of communication protocols in VANETs, we investigate two improvements that increase the packet delivery ratio and reduce the delay until the first packet arrives. The traces used in this study are available for public download. [pdf]
    
    
83. Beyer, Dirk; Henzinger, Thomas A.; Singh, Vasu   [BeyerHS:06]   [published]
    Three Algorithms for Interface Synthesis: A Comparative Study    
    Technical report EPFL MTC-REPORT-2006-001, May 2006
    A temporal interface for a system component is a finite automaton that specifies the legal sequences of input events. We evaluate and compare three different algorithms for automatically extracting the temporal interface from the transition graph of a component: (1) a game algorithm that computes the interface as a representation of the most general environment strategy to avoid a safety violation; (2) a learning algorithm that repeatedly queries the component to construct the minimal interface automaton; and (3) a CEGAR algorithm that iteratively refines an abstract interface hypothesis by adding relevant state information from the component. Since algorithms (2) and (3) have been published in different software contexts, for comparison purposes, we present the three algorithms in a uniform finite-state setting. We furthermore extend the three algorithms to construct maximally permissive interface automata, which accept all legal input sequences. While the three algorithms have similar worst-case complexities, their actual running times differ greatly depending on the component whose interface is computed. On the theoretical side, we provide families of components that exhibit exponential differences in the performance of the three algorithms. On the practical side, we evaluate the three algorithms experimentally on a variety of real world examples. Not surprisingly, the experimental evaluation confirms the theoretical expectation: learning performs best if the minimal interface automaton is small; CEGAR performs best if only few component variables are needed to prove an interface hypothesis safe and permissive; and the direct (game) algorithm outperforms both approaches if neither is the case. [pdf]
    
    
84. Christoph Angerer, Thomas Gross   [AngererG:06]   [published]
    Model and Architecture of a Timing Service for Adaptive Policy-Based Management Systems    
    First IEEE Workshop on Adaptive Policy-Based Management in Network Management and Control (A-PBM), co-located with IEEE INFOCOM, Barcelona, 28 Apr 06
    Policy-Based Management (PBM) is a promising approach to realize adaptivity in networks that would be hard --- if not impossible --- for administrators to configure manually. In PBM systems, the network configuration is not directly expressed in terms of low-level properties, such as IP or MAC addresses; rather, complex business entities, such as users or departments, can be defined and allow the administrators to specify high-level network policies. Even though PBM can reduce the effort for managing complex networks significantly, today's solutions lack a generic way for expressing adaptive policies. A PBM system can be called adaptive if the decision of when and in which order policies are activated is not only based on fixed predefined dates but the system also takes environmental and internal events into account. In this paper we describe a model of adaptive timing constraints and introduce an architecture for executing timing specifications (sets of constraints). Within a timing specification, the administrator usually creates single constraints only implicitly by defining the lifetime of managed resources, sequences of events, and high-level temporal relationships between them. Because each timing constraint defines a relation between two single events, a timing specification can be described as a partial ordering of events over the event space. During execution, a Timing Service triggers PBM systems to activate, inactivate, or adapt management policies according to the timing specification. [pdf]
    
    
85. Oliver Trachsel, Christoph von Praun, Thomas R. Gross   [TrachselPG:06]   [published]
    On the Effectiveness of Speculative and Selective Memory Fences    
    20th International Parallel and Distributed Processing Symposium (IPDPS '06), Rhodes, 25-29 Apr 06
    Memory fences inhibit the reordering of memory accesses in modern microprocessors; fences are useful to implement synchronization and strong shared memory semantics in multi-threaded programs. A naive implementation of memory fences can result in a significant performance penalty for processors with deep pipelines supporting multiple concurrent memory accesses. The paper compares three techniques to reduce the impact of memory fences: (1) Read-speculation allows reads that follow a fence to be issued while the fence is being processed; (2) Write-ahead additionally allows writes following a fence to proceed early; (3) Selective fences distinguish between memory accesses to thread-local and shared memory and enforce ordering only among accesses to shared memory. We evaluate and compare the effectiveness of these techniques with a simulator derived from the Pentium 4 architecture. We report data for a storage model that uses memory fences to enforce the memory semantics at monitor boundaries. [pdf]
    
    
86. Marc Heissenbüttel, Torsten Braun, Markus Waelchli and Thomas Bernoulli   [HeissenbuettelBWB:05]   [published]
    Optimized Stateless Broadcasting in Wireless Multi-hop Networks    
    IEEE Infocom 2006, Barcelona, 23-29 Apr 06
    In this paper we present a simple and stateless broadcasting protocol called Dynamic Delayed Broadcasting (DDB) which allows locally optimal broadcasting without any prior knowledge of the neighborhood. As DDB does not require any transmissions of control messages, it conserves critical network resources such as battery power and bandwidth. Local optimality is achieved by applying a principle of Dynamic Forwarding Delay (DFD) which delays the transmissions dynamically and in a completely distributed way at the receiving nodes ensuring nodes with a higher probability to reach new nodes transmit first. An optimized performance of DDB over other stateless protocols is shown by analytical results. Furthermore, simulation results show that, unlike stateful broadcasting protocols, the performance of DDB does not suffer in dynamic topologies caused by mobility and sleep cycles of nodes. These results together with its simplicity and the conservation of network resources, as no control message transmissions are required, make DDB especially suited for sensor and vehicular ad-hoc networks.
    
    
87. Thomas Moscibroda, Pascal von Rickenbach, Roger Wattenhofer   [MoscibrodaRW:06]   [published]
    Analyzing the Energy-Latency Trade-off during the Deployment of Sensor Networks    
    IEEE Infocom 2006, Barcelona, 23-29 Apr 06
    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 spend a large portion of their lifetime in an energyefficient sleep mode during which they do neither receive nor send messages. On the other hand, the longer nodes stay in sleep mode, the slower will be the reaction time for disseminating an external event. The trade-off is prominently exhibited during the deployment phase of sensor networks, if some nodes are deployed earlier than others. In this paper, we study this fundamental trade-off by giving a formal model that enables us to compare the performance of different protocols and algorithms. Based on this model, we propose, analyze, and simulate two novel algorithms which significantly outperform existing solutions. [pdf]
    
    
88. Thomas Moscibroda, Roger Wattenhofer   [MoscibrodaW:06]   [published]
    The Complexity of Connectivity in Wireless Networks    
    IEEE Infocom 2006, Barcelona, 23-29 Apr 06
    We define and study the scheduling complexity in wireless networks, which expresses the theoretically achievable efficiency of MAC layer protocols. Given a set of communication requests in arbitrary networks, the scheduling complexity describes the amount of time required to successfully schedule all requests. The most basic and important network structure in wireless networks being connectivity, we study the scheduling complexity of connectivity, i.e., the minimal amount of time required until a connected structure can be scheduled. In this paper, we prove that the scheduling complexity of connectivity grows only polylogarithmically in the number of nodes. Specifically, we present a novel scheduling algorithm that successfully schedules a strongly connected set of links in time O(log4n) even in arbitrary worst-case networks. On the other hand, we prove that standard MAC layer or scheduling protocols can perform much worse. Particularly, any protocol that either employs uniform or linear (a node’s transmit power is proportional to the minimum power required to reach its intended receiver) power assignment has a ­(n) scheduling complexity in the worst case, even for simple communication requests. In contrast, our polylogarithmic scheduling algorithm allows many concurrent transmission by using an explicitly formulated non-linear power assignment scheme. Our results show that even in large-scale worst-case networks, there is no theoretical scalability problem when it comes to scheduling transmission requests, thus giving an interesting complement to the more pessimistic bounds for the capacity in wireless networks. All results are based on the physical model of communication, which takes into account that the signal-tonoise plus interference ratio (SINR) at a receiver must be above a certain threshold if the transmission is to be received correctly. [pdf]
    
    
89. Thomas Henzinger and Slobodan Matic   [HenzingerM:06]   [published]
    An interface algebra for real-time components    
    IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), San Jose, 4-7 Apr 06
    We present an assume-guarantee interface algebra for real-time components. In our formalism a component implements a set of task sequences that share a resource. A component interface consists of an arrival rate function and a latency for each task sequence, and a capacity function for the shared resource. The interface specifies that the component guarantees certain task latencies depending on assumptions about task arrival rates and allocated resource capacities. Our algebra defines compatibility and refinement relations on interfaces. Interface compatibility can be checked on partial designs, even when some component interfaces are yet unknown. In this case interface composition computes as new assumptions the weakest constraints on the unknown components that are necessary to satisfy the specified guarantees. Interface refinement is defined in a way that ensures that compatible interfaces can be refined and implemented independently. Our algebra thus formalizes an interface-based design methodology that supports both the incremental addition of new components and the independent stepwise refinement of existing components. We demonstrate the flexibility and efficiency of the framework through simulation experiments. [pdf]
    
    
90. Thomas Moscibroda, Stefan Schmid, and Roger Wattenhofer   [MoscibrodaSW:06]   [published]
    On the Topologies Formed by Selfish Peers    
    5th International Workshop on Peer-to-Peer Systems (IPTPS), Santa Barbara, 27-28 Feb 06
    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. However, the selfish behavior of peers has aspects which go beyond resource sharing. This paper studies the effects on the topology of a P2P network if peers selfishly select the peers to connect to. In our model, a peer exploits locality properties in order to minimize the latency (or response times) of its lookup operations. At the same time, the peer aims at not having to maintain links to too many other peers in the system. We show that the resulting topologies can be much worse than if peers collaborated. Moreover, the network may never stabilize, even in the absence of churn. [pdf]
    
    
91. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer   [KuhnMW:06]   [published]
    The Price of Being Near-Sighted    
    17th ACM-SIAM Symposium on Discrete Algorithms (SODA), Miami, 22-24 Jan 06
    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 tight classification of the possible tradeoff between the amount of local information and the quality of the global solution for general covering and packing problems. Specifically, we give a distributed algorithm using only small messages which obtains an (½¢)1/k-approximation for general covering and packing problems in time O(k2), where ½ depends on the LP’s coefficients. If message size is unbounded, we present a second algorithm that achieves an O(n1/k) approximation in O(k) rounds. Finally, we prove that these algorithms are close to optimal by giving a lower bound on the approximability of packing problems given that each node has to base its decision on information from its k-neighborhood. [pdf]
    
    
92. Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, and Roger Wattenhofer   [KuhnMNW:05]   [published]
    Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs    
    19th International Symposium on Distributed Computing (DISC'05), Cracow, 26-29 Sep 05
    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 algorithm for general graphs [20], no deterministic polylogarithmic algorithm is known. In this paper, we study the problem in graphs with bounded growth, an important family of graphs which includes the well-known unit disk graph and many variants thereof. Particularly, we propose a deterministic algorithm that computes a maximal independent set in time O(log¢¢log¤n) in graphs with bounded growth, where n and ¢ denote the number of nodes and the maximal degree in G, respectively. [pdf]
    
    
93. Florian T. Schneider, Thomas Gross   [SchneiderG:05]   [published]
    Using Platform-Specific Performance Counters for Dynamic Compilation    
    International Workshop on Languages and Compilers for Parallel Computing (LCPC 2005), New York, 20-22 Sep 05
    Hardware performance counters provide information about events in the hardware platform (e.g., cache misses, pipeline stalls), in contrast to profiles that capture program properties (e.g., execution frequencies for basic blocks, methods, function calls). As platform architectures become more complex and also more diverse, it is important for a compiler to exploit platform-specific information. A dynamic (JIT) compiler is in the unique position to run on the same platform as the target application, but in practice, exploiting the wealth of information available through performance counters is far from easy. If a JIT compiler is to use performance counter information, this information must be fine-grained (e.g., attributing cache misses to a single load instruction) and must be obtainable without undue overhead. We present a runtime+compiler framework to tie hardware performance counter information to a dynamic compiler and argue that the overhead is low and fine-grained. As parallel architectures or multi-core architectures proliferate, performance issues will play a crucial role in all compilation engines, and our paper reports on a modular approach to make such counter information available to the compiler. [pdf]
    
    
94. Thomas Moscibroda and Roger Wattenhofer   [MoscibrodaW:05e]   [published]
    Minimizing Interference in Ad Hoc and Sensor Networks    
    3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, 2 Sep 05
    Reducing interference is one of the main challenges in wire- less communication, and particularly in ad hoc networks. The amount of interference experienced by a node v cor- responds to the number of other nodes whose transmis- sion range covers v. At the cost of communication links being dropped, interference can be reduced by decreasing the node's transmission power. In this paper, we study the problem of minimizing the average interference while still maintaining desired network properties, such as connectiv- ity, point-to-point connections, or multicast trees. In par- ticular, we present a greedy algorithm that computes an O(log n) approximation to the interference problem with connectivity requirement, where n is the number of nodes in the network. We then show the algorithm to be asymp- totically optimal by proving a corresponding ­(log n) lower bound that holds even in a more restricted interference model. Finally, we show how the algorithm can be generalized to- wards solving the interference problem for network proper- ties that can be formulated as a 0-1 proper function. [pdf]
    
    
95. Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, and Roger Wattenhofer   [KuhnMNW:05b]   [published]
    Local Approximation Schemes for Ad Hoc and Sensor Networks    
    3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, 2 Sep 05
    We present two local approaches that yield polynomial-time approximation schemes (PTAS) for the Maximum Indepen- dent Set and Minimum Dominating Set problem in unit disk graphs. The algorithms run locally in each node and com- pute a (1 + ")-approximation to the problems at hand for any given " > 0. The time complexity of both algorithms is O(TMIS + log¤n="O(1)), where TMIS is the time required to compute a maximal independent set in the graph, and n de- notes the number of nodes. We then extend these results to a more general class of graphs in which the maximum num- ber of pair-wise independent nodes in every r-neighborhood is at most polynomial in r. Such graphs of polynomially bounded growth are introduced as a more realistic model for wireless networks and they generalize existing models, such as unit disk graphs or coverage area graphs. [pdf]
    
    
96. Fabian Kuhn, Thomas Moscibroda and Roger Wattenhofer   [KuhnMW:05]   [published]
    On the Locality of Bounded Growth    
    24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2005), Las Vegas, 17-20 July 05
    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 neighborhoods of increasing size. Due to this bounded volume growth, one could expect that distributed algorithms are able to solve many problems more e±ciently than on general graphs. The goal of this paper is to help understanding the distributed complexity of problems on bounded growth graphs. We show that on the widely used unit disk graph, covering and packing linear programs can be approximated by constant factors in constant time. For a more general network model which is based on the assumption that nodes are in a metric space of constant doubling dimension, we show that in O(log^* n) rounds it is possible to construct a (O(1),O(1))-network decomposition. This results in asymptotically optimal O(log^* n) time algorithms for many important problems. [pdf] [ps]
    
    
97. Thomas Moscibroda, Roger Wattenhofer   [MoscibrodaW:05]   [published]
    Facility Location: Distributed Approximation    
    24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2005), Las Vegas, 17-20 July 05
    In this paper, we initiate the study of the approximability of the facility location problem in a distributed setting. In particular, we explore a trade-o® between the amount of communication and the resulting approximation ratio. We give a distributed algorithm that, for every constant k, achieves an O(sqrt(k)(m rho)^(1/sqrt(k)) log(m + n)) approximation in O(k) communication rounds where message size is bounded to O(log n) bits. The number of facilities and clients are m and n, respectively, and rho is a coefficient that depends on the cost values of the instance. Our technique is based on a distributed primal-dual approach for approximating a linear program, that does not form a covering or packing program. [pdf] [ps]
    
    
98. Thomas Moscibroda, Roger Wattenhofer   [MoscibrodaW:05b]   [published]
    Maximal Independent Sets in Radio Networks    
    24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2005), Las Vegas, 17-20 July 05
    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 available. Specifically, we propose a novel randomized algorithm that computes a MIS in time O((log n)^2) with high probability, where n is the number of nodes in the network. This significantly improving on the best previously known solutions. A lower bound of ­Omega((log n)^2/(log log n)) given in [11] implies that our algorithm's running time is close to optimal. Our result shows that the harsh radio network model imposes merely an additional O(log n) factor compared to Luby's MIS algorithm in the message passing model. This has important implications in the context of ad hoc and sensor networks whose charac- teristics are closely captured by the radio network model. [pdf] [ps]
    
    
99. Thomas Moscibroda and Roger Wattenhofer   [MoscibrodaW:05d]   [published]
    Coloring Unstructured Radio Networks    
    17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Las Vegas, 17-20 July 05
    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 reasonable communication can take place, nodes must come up with an initial structure that can serve as a foundation for more sophisticated algorithms. In this paper, we consider the problem of obtaining a vertex coloring as such an initial structure. We propose an algorithm that works under the unstructured radio network model. This model captures the characteristics of newly deployed ad hoc and sensor networks, i.e. asynchronous wake-up, no collision-detection, and scarce knowledge about the network topology. Our algorithm produces a correct coloring with O(Delta) colors in time O(Delta log n) with high probability in a unit disk graph, where n and Delta are the number of nodes in the network and the maximum degree, respectively. Furthermore, the number of locally used colors depends only on the local node density. [pdf] [ps]
    
    
100. Marc Heissenbüttel, Torsten Braun, Tobias Roth, Thomas Bernoulli   [HeissenbuettelBRB:05]   [published]
     GNU/Linux Implementation of a Position-based Routing Protocol    
     IEEE ICPS Workshop on Multi-hop Ad hoc Networks: from theory to reality (REALMAN), Santorini, 14 July 05
     The Beacon-Less Routing protocol (BLR) is a position-based routing protocol for mobile ad-hoc networks that makes use of location information to reduce routing overhead. However, unlike other position-based routing protocols, BLR does not require nodes to periodically broadcast hello messages and thus avoids drawbacks such as extensive use of scarce battery-power, interferences with regular data transmission, and performance degradation. In this paper, we describe the implementation of BLR on a GNU/Linux platform comprising laptops equipped with 802.11b WLAN cards and GPS receivers. We present results of BLR’s performance obtained from laboratory experiments, which were conducted to validate the implementation for future planned outdoor experiments. [pdf]
     
     
101. Yang Su and Thomas Gross   [SuG:05]   [published]
     WXCP: Explicit Congestion Control for Wireless Multi-Hop Networks    
     Thirteenth International Workshop on Quality of Service (IWQoS 2005), Passau, 21-23 June 05
     TCP experiences serious performance degradation in wireless multi-hop networks with its probe-based, loss-driven congestion control scheme. We describe the Wireless eXplicit Congestion control Protocol (WXCP), a new explicit flow control protocol for wireless multi-hop networks based on XCP. We highlight the approaches taken by WXCP to address the difficulties faced by the current TCP implementation in wireless multi-hop networks. Simulations with ns-2 show that WXCP outperforms current TCP implementations in terms of efficiency and fairness. [pdf]
     
     
102. Marc Heissenbüttel, Torsten Braun, David Joerg, Thomas Huber   [HeissenbuettelBJH:05]   [published]
     A Framework for Routing in Large Ad-hoc Networks with Irregular Topologies    
     Fourth Annual Mediterranean Ad Hoc Networking Workshop, Porquerolles, 21-24 June 05
     In this paper, we consider routing in large wireless multihop networks with possibly irregular topologies. Existing position-based routing protocols have deficiencies in such scenarios as they always forward packets directly towards the destination. Greedy routing frequently fails and costly recovery mechanisms have to be applied. We propose the Ants-based Mobile Routing Architecture (AMRA) for optimized routing, which combines position-based routing, topology abstraction, and swarm intelligence. AMRA routes packets along paths with high connectivity and short delays by memorizing past traffic and by using ant-like packets to discover shorter paths. The geographic topology abstraction allows AMRA to cope with high mobility and large networks. Simulative evaluation indicate that compared to other position-based routing AMRA finds significantly shorter paths with only marginal overhead protocols. [pdf]
     
     
103. Peyrin, Thomas; Vaudenay, Serge   [PeyrinV:05]   [published]
     The Pairing Problem with User Interaction    
     Security and Privacy in the Age of Ubiquitous Computing, the 20th International Information Security Conference, SEC'05; Chiba, Japan, May 30 - June 1, 2005, p. 251-265
     Bluetooth-like applications face the pairing problem: two devices want to establish a relationship between them without any prior private information. Hoepman studied the ephemeral pairing problem by regarding the human operator of the devices as a messenger in an authenticated and/or private low-bandwidth channel between the nodes. Here we study the pairing problem with user interaction in which the operator can participate by doing extra (simple) computations.
     
     
104. Thomas Locher, Roger Wattenhofer, and Aaron Zollinger   [LocherWZ:05]   [published]
     Received-Signal-Strength-Based Logical Positioning Resilient to Signal Fluctuation    
     1st ACIS International Workshop on Self-Assembling Wireless Sensor Networks (SAWN), Baltimore, 23-25 May 05
     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 received signal strengths fluctuate significantly over time due to noise and interference. Unlike most of the related work our approach does not rely on the presence of a priori information about base station positions, objects influencing radio signal propagation, and signal propagation characteristics. Instead of trying to compute the current position defined by \emph{coordinates}, the goal of our system is to infer a user's present \emph{logical} position. In addition, our system particularly differs from previous work in the chosen statistical approach, which explicitly copes with signal strength fluctuation over time and allows control over system accuracy by means of specification of confidence intervals. [pdf] [ps]
     
     
105. Marc Heissenbüttel, Torsten Braun, Thomas Huber and David Jörg   [HeissenbüttelBHJ:05]   [published]
     Routing in Large Wireless Multihop Networks with Irregular Topologies    
     5th Scandinavian Workshop on Wireless Ad-hoc Networks (ADHOC ´05), Stockholm, 3-4 May 2005
     Position-based routing protocols forward packets solely based on geographical information about nodes. Therefore, in irregular topologies where routing along a straight line to the destination is not feasible due to voids, they choose suboptimal paths. In this paper, we propose a position-based protocol MRA that tries to capture the global network topology on a large scale from overheard data packets and, if necessary, actively transmits explorer packets to find shorter paths. The required additional memory at the nodes can be kept small by applying a fish-eye like view on the network, where distant areas are aggregated to zones. A node does only forward packets in a certain direction for a given destination zone when it also has previously received packets from this direction and originating in that destination zone. Thus, MRA does not route packets along infeasible paths where packets cannot be forwarded directly to the destination due to voids. Simulation results show that MRA is able to find up to 40\% shorter paths than other position-based protocol in irregular network topologies. [pdf]
     
     
106. Irina Chihaia Tuduce and Thomas Gross   [ChihaiaG:05]   [published]
     Adaptive Main Memory Compression    
     USENIX'05 Annual Technical Conference, Anaheim, 10-15 April 2005
     

     Applications that use large data sets frequently exhibit poor performance because the size of their working set exceeds the real memory, causing excess page faults, and ultimately exhibit thrashing behavior.

     This paper describes a memory compression solution to this problem that adapts the allocation of real memory between uncompressed and compressed pages and also manages fragmentation without user involvement. The system manages its resources dynamically on the basis of the varying demands of each application and also on the situational requirements that are data dependent. The technique used to localize page fragments in the compressed area allows the system to reclaim or add space easily if it is advisable to shrink or grow the size of the compressed area.

     The design is implemented in Linux, runs on both 32-bit and 64-bit architectures, and has been demonstrated to work in practice under complex workload conditions and memory pressure. The benefits from our approach depend on the relationship between the size of the compressed area, the application's compression ratio, and the access pattern of the application. For a range of benchmarks and applications, the system shows an increase in performance by a factor of 1.3 to 55. [pdf]
     
     

107. Thomas Moscibroda and Roger Wattenhofer   [MoscibrodaW:05c]   [published]
     Maximizing the Lifetime of Dominating Sets    
     5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, 4-8 Apr 05
     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 restrictions that forces the designers to impose a judicious power management and scheduling. For the purpose of saving energy, dominating set based clustering has turned out to be a useful and generic concept in such networks. In data gathering applications, for example, only nodes in the dominating set must be active, while all other nodes can remain in the energy-efficient sleep mode. Prolonging the duration of such a dominating set based clustering is a key algorithmic challenge. In this paper, we define the maximum cluster-lifetime problem which asks for a schedule that maximizes the time the network is clustered by a dominating set. We give approximation algorithms with an approximation ratio of O(log n) for several variants of the maximum cluster-lifetime problem. Our approach is based on results given in a paper by Feige, Halld´orsson, Kortsarz, and Srinivasan on the domatic partition problem. [pdf]
     
     
108. Cristian Tuduce and Thomas Gross   [TuduceG:05]   [published]
     A Mobility Model Based on WLAN Traces and its Validation    
     IEEE INFOCOM 2005, Miami, 13-17 March 05
     The simulation of mobile networks calls for a mobility model to generate the trajectories of the mobile users (or nodes). It has been shown that the mobility model has a major influence on the behavior of the system. Therefore, using a realistic mobility model is important if we want to increase the confidence that simulations of mobile systems are meaningful in realistic settings.
     
     In this paper we present an executable mobility model that uses real-life mobility characteristics to generate mobility scenarios that can be used for network simulations. We present a structured framework for extracting the mobility characteristics from a WLAN trace, for processing the mobility characteristics to determine a parameter set for the mobility model, and for using a parameter set to generate mobility scenarios for simulations. To derive the parameters of the mobility model, we measure the mobility characteristics of users of a campus wireless network. Therefore, we call this model the WLAN mobility model. Mobility analysis confirms properties observed by other research groups. The validation shows that the WLAN model maps the real-world mobility characteristics to the abstract world of network simulators with a very small error.
     
     For users that do not have the possibility to capture a WLAN trace, we explore the value space of the WLAN model parameters and show how different parameters sets influence the mobility of the simulated nodes.
     [pdf]
     
     
109. Marc Heissenbüttel, Torsten Braun, Markus Waelchli, Thomas Bernoulli   [HeissenbüttelBWB:04]   [published]
     Broadcasting in Wireless Multihop Networks with the Dynamic Forwarding Delay Concept    
     Technical Report, IAM-04-010, University of Bern, Dec 2004
     In this report we present a simple and stateless broadcasting protocol called Dynamic Delayed Broadcasting (DDB) which allows locally optimal broadcasting without any knowledge about the neighborhood. As DDB does not require any transmissions of control messages, it conserves critical network resources such as battery power and bandwidth. Local optimality is achieved by applying a principle of Dynamic Forwarding Delay (DFD) which delays the transmissions dynamically and in a complete distributed way at the receiving nodes such that nodes with a higher probability to reach new nodes transmit first. An optimized performance of DDB over other stateless protocols is shown by analytical results. Furthermore, simulation results show that, unlike stateful broadcasting protocols, the performance of DDB does not suffer in dynamic topologies caused by mobility and sleep cycles of nodes. These results together with its simplicity and the conservation of network resources, as no control message transmissions are required, make DDB especially suited for sensor and vehicular ad-hoc networks.
     
     
110. Avoine, Gildas; Monnerat, Jean; Peyrin, Thomas   [AvoineMP:04]   [published]
     Advances in Alternative Non-Adjacent Form Representations    
     The 5th International Conference on Cryptology in India - Indocrypt 2004; Chennai, India, December 20-22, 2004, vol. 3348, p. 260-274
     From several decades, non-adjacent form (NAF) representations for integers have been extensively studied as an alternative to the usual binary number system where digits are in {0,1}. In cryptography, the non-adjacent digit set (NADS) {-1,0,1} is used for optimization of arithmetic operations in elliptic curves. At SAC 2003, Muir and Stinson published new results on alternative digit sets: they proposed infinite families of integers x such that {0,1,x} is a NADS as well as infinite families of integers x such that {0,1,x} is not a NADS, so called a NON-NADS. Muir and Stinson also provided an algorithm that determines whether x leads to a NADS by checking if every integer n in [0, [-x/3]] has a {0,1,x}-NAF. In this paper, we extend these results by providing generators of NON-NADS infinite families. Furthermore, we reduce the search bound from [-x/3] to [-x/12]. We introduce the notion of worst NON-NADS and give the complete characterization of such sets. Beyond the theoretical results, our contribution also aims at exploring some algorithmic aspects. We supply a much more efficient algorithm than those proposed by Muir and Stinson, which takes only 343 seconds to compute all x's from 0 to -10^7 such that {0,1,x} is a NADS.
     
     
111. Kay Römer, Thomas Schoch, Friedemann Mattern, Thomas Dübendorfer   [RoemerSMD:04]   [published]
     Smart identification frameworks for ubiquitous computing applications    
     Wireless Networks (Springer), Vol. 10, Issue 6, Nov 04
     We present our results of the conceptual design and the implementation of ubiquitous computing applications using smart identification technologies. First, we describe such technologies and their potential application areas, then give an overview of some of the applications we have developed. Based on the experience we have gained from developing these systems, we point out design concepts that we have found useful for structuring and implementing such applications. Building upon these concepts, we have created two frameworks based on Jini (i.e., distributed Java objects) and Web Services to support the development of ubiquitous computing applications that make use of smart identification technology. We describe our prototype frameworks, discuss the underlying concepts and present some lessons learned. [pdf]
     
     
112. Thomas Moscibroda, Roger Wattenhofer   [MoscibrodaW:04]   [published]
     Efficient Computation of Maximal Independent Sets in Unstructured Multi-Hop Radio Networks    
     1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), Fort Lauderdale, 24-27 Oct 2004
     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 and immediately after the deployment of such networks. Computing a good initial clustering facilitates this task and is therefore a vital part of the initialization process. A clustering based on a maximal independent set provides several highly desirable properties. Besides yielding a dominating set of good quality, such a clustering avoids interference between clusterheads, thus allowing efficient communication. We propose a novel algorithm that works under a model capturing the characteristics of the initialization phase of unstructured radio networks, i.e., asynchronous wake-up, scarce knowledge about the topology of the network graph, no collision detection, and the hidden terminal problem. We show that even under these hard conditions, the algorithm computes a maximal independent set in polylogarithmic time. [pdf] [ps]
     
     
113. Thomas Moscibroda, Regina O'Dell, Mirjam Wattenhofer, Roger Wattenhofer   [MoscibrodaOWW:04]   [published]
     Virtual Coordinates for Ad hoc and Sensor Networks    
     Dial M-POMC 2004, Mobicom Joint Workshop on Foundations of Mobile Computing, Philadelphia, 1 Oct 04
     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 sufficient to have virtual coordinates, rather than real coordinates. In this paper, we address the problem of obtaining virtual coordinates based on connectivity information. In particular, we propose the first approximation algorithm for this problem and discuss implementational aspects. [pdf] [ps]
     
     
114. Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer   [KuhnMW:04c]   [published]
     Unit Disk Graph Approximation    
     Dial M-POMC 2004, Mobicom Joint Workshop on Foundations of Mobile Computing, Philadelphia, 1 Oct 04
     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 embedding can be used to obtain virtual coordinates. In this paper, we prove a non-approximability result for the problem of embedding a given unit disk graph. Particularly, we show that if non-neighboring nodes are not allowed to be closer to each other than distance 1, then two neighbors can be as far apart as sqrt(3/2)-epsilon, where epsilon goes to 0 as n goes to infinity, unless P = NP. We further show that finding a realization of a d-quasi unit disk graph with d>=1/sqrt(2) is NP-hard. [pdf] [ps]
     
     
115. Risse, Thomas; Aberer, Karl; Wombacher, Andreas; Surridge, M.; Taylor, S.   [RisseAWST:04]   [published]
     Configuration of distributed message converter systems    
     Performance Evaluation, vol. 58, no 1, p. 43-80
     
     
     
116. Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer   [KuhnMW:04d]   [published]
     Initializing Newly Deployed Ad Hoc and Sensor Networks    
     MOBICOM 2004, Philadelphia, 26 Sep - 1 Oct 2004
     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 initialization phase of ad hoc and sensor networks. Particularly, we model the network as a multi-hop quasi unit disk graph and allow nodes to wake up asynchronously at any time. Further, nodes do not feature a reliable collision detection mechanism, and they have only limited knowledge about the network topology. We show that even for this restricted model, a good clustering can be computed efficiently. Our algorithm efficiently computes an asymptotically optimal clustering. Based on this algorithm, we describe a protocol for quickly establishing synchronized sleep and listen schedule between nodes within a cluster. Additionally, we provide simulation results in a variety of settings. [pdf] [ps]
     
     
117. Matteo Corti and Thomas Gross   [CortiG:04b]   [published]
     Approximation of the Worst-Case Execution Time Using Structural Analysis    
     EMSOFT2004, 4th ACM International Conference on Embedded Software, Pisa, 27-29 Sep 04
     We present a technique to approximate the worst-case execution time that combines structural analysis with a loop-bounding algorithm based on local induction variable analysis. Structural analysis is an attractive foundation for several reasons: it delivers better bounds on the number of executions for each basic block than previous approaches, its complexity is well understood, and it allows the compiler to easily work on Java bytecode without requiring access to the original program source. There are two major steps. We first compute (min, max) bounds on the number of iterations for each loop. Then we use precise structural information to propagate these bounds to the whole control-flow graph and compute a bound for each basic block. Such a fine-grained result eases the identification of infeasible paths and improves the approximation of the worst-case execution time of a function or method. This analysis was successfully implemented in an ahead-of-time Java bytecode to native compiler and produces input for a worst-case execution time estimator. We describe the effectiveness in reducing the worst-case execution time for a number of programs from small kernels and soft-real-time applications.
     
     
118. Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer   [KuhnMW:04b]   [published]
     Radio Network Clustering from Scratch    
     12nd Annual European Symposium on Algorithms (ESA), Bergen, Norway, September 2004
     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 characteristics of the set-up phase of such multi-hop radio networks: asynchronous wake-up, the hidden terminal problem, and scarce knowledge about the topology of the network graph. When modelling the network as a unit disk graph, the algorithm computes a dominating set in polylogarithmic time and achieves a constant approximation ratio. [pdf] [ps]
     
     
119. Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer   [KuhnMW:04a]   [published]
     What Cannot be Computed Locally!    
     23rd ACM Symposium on Principles of Distributed Computing (PODC), St. John's, Canada, 25-28 July 2004
     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 approximated by factors Omega(n^(c/k^2)/k) and Omega(Delta^(1/k)/k) for some constant c, where n and Delta denote the number of nodes and the largest degree in the graph. The number of rounds required in order to achieve a constant or even only a polylogarithmic approximation ratio is at least Omega(sqrt(log n/(log log n))) and Omega(sqrt(log Delta/(log log Delta))). By a simple reduction, the latter lower bounds also hold for the construction of maximal matchings and maximal independent sets. [pdf] [ps]
     
     
120. Marc Heissenbüttel, Torsten Braun, Thomas Bernoulli, and Markus Waelchli   [HeissenbuettelBBW:04a]   [published]
     BLR: Beacon-Less Routing Algorithm for Mobile Ad-Hoc Networks    
     Elsevier's Computer Communications Journal, Volume 27, Issue 11, 1 July 2004
     Routing in mobile ad-hoc networks with a large number of nodes or with high mobility is a very difficult task and current routing protocols do not really scale well with these scenarios. The Beacon-Less Routing Algorithm (BLR) presented in this paper is a routing protocol that makes use of location information to reduce routing overhead. But as opposed to other position-based routing protocols, BLR does not require nodes to broadcast periodically Hello-messages with their position (called beaconing), and thus avoids all the associated drawbacks such as the use of scarce battery-power, interferences with regular data transmission what leads to an overall decrease in the network performance. In BLR, a forwarding node is selected in a distributed way among the neighboring nodes without having information about their positions even about their existence. Data packets are just broadcasted and the protocol takes care that just one of the receiving nodes eventually forwards the packet by introducing an additional delay at each node. Consequently, the node which introduces the smallest delay relays the packet first. This forwarding is detected by the other nodes and suppresses them to relay the packet any further. Analytical results and simulation experiments indicate that BLR is most appropriate for dense networks and provides efficient and robust routing in highly dynamic mobile ad-hoc networks. [pdf]
     
     
121. Irina Chihaia and Thomas Gross   [ChihaiaG:04b]   [published]
     An Analytical Model for Software-Only Main Memory Compression    
     3rd Workshop on Memory Performance Issues (WMPI-2004), Munich, 20 June 2004
     Many applications with large data spaces that cannot run on a typical workstation (due to page faults) call for techniques to expand the effective memory size. One such technique is memory compression. Understanding what applications under what conditions can benefit from main memory compression is complicated due to various tradeoffs and the dynamic characteristics of applications. For instance, a large area to store compressed data increases the effective memory size considerably but also decreases the amount of memory that can hold uncompressed data. This paper presents an analytical model that states the conditions for a compressed-memory system to yield performance improvements. Parameters of the model are the compression algorithm efficiency, the amount of data being compressed, and the application memory access pattern. Such a model can be used by an operating system to compute the size of the compressed-memory level that can improve an application's performance. [ps]
     
     
122. Cristian Tuduce and Thomas Gross   [TuduceG:04]   [published]
     Resource Monitoring Issues in Ad Hoc Networks    
     International Workshop on Wireless Ad-hoc Networks (IWWAN'04), Oulu, Finland, 1-3 June 04
     In this paper we explore the solution space for resource monitoring systems for mobile ad hoc networks. To cope with the range of parameters of interest to an application, we separate the resource monitoring system into an extensible infrastructure and specific sensors, which record network parameters of interest. The monitoring infrastructure includes two abstractions that capture a node's environment, the neighborhood and the swath. Whereas in a wire-line network information about the nodes along the path from source to destination is sufficient to characterize the connection between source and destination, in mobile networks other nodes within transmit range may have an impact. The paper concludes with a discussion of our experience obtained with a prototype implementation and a summary of preliminary results. [pdf]
     
     
123. Matteo Corti and Thomas Gross   [CortiG:04]   [published]
     Instruction Duration Estimation by Partial Trace Evaluation    
     WIP Session of the 10th Real-Time and Embedded Technology and Applications Symposium (RTAS'04), Toronto, 25-28 May 2004
     Hard and soft real time systems require, for each process, the worst-case execution time (WCET), which is needed by the scheduler's admission tests and subsequently limits a task's execution time during operation. A worst-case execution time analysis is usually performed in two distinct steps: first the program is analyzed to extract semantic information and determine maximal bounds on the number of iterations for each basic block. In a second step the duration of the different program's instructions is computed with respect to the used hardware platform. Modern systems with preemption and modern architectures with non-constant instruction duration (due to pipelining, branch prediction and different level of caches) hinder a fast and precise computation of a program's WCET. We present a technique to approximate the instruction duration on modern processors using precise block bounds. Instead of simulating the CPU behavior on all the possible paths we apply the principle of locality limiting the effects of a given instruction to a restricted time allowing us to analyze large applications in linear time. [pdf]
     
     
124. Karl Aberer, Philippe Cudré-Mauroux and Aris M. Ouksel (editors); Tiziana Catarci Mohand-Said Hacid, Arantza Illarramendi, Vipul Kashyap, Massimo Mecella, Eduardo Mena, Erich J. Neuhold, Olga De Troyer, Thomas Risse, Monica Scannapieco, Fèlix Saltor, Luca de Santis, Stefano Spaccapietra, Steffen Staab and Rudi Studer    [AbererCO:04]   [published]
     Emergent Semantics Principles and Issues    
     Proceedings of the 9th International Conference on Database Systems for Advanced Applications (DASFAA 2004), Jeju Island, Korea, 17-19 Mar 04
     Information and communication infrastructures underwent a rapid and extreme decentralization process over the past decade: From a world of statically and partially connected central servers rose an intricate web of millions of information sources loosely connecting one to another. Today, we expect to witness the extension of this revolution with the wide adoption of meta-data standards like RDF or OWL underpinning the creation of a semantic web. Again, we hope for global properties to emerge from a multiplicity of pair-wise, local interactions, resulting eventually in a self-stabilizing semantic infrastructure. This paper represents an eort to summarize the conditions under which this revolution would take place as well as an attempt to underline its main properties, limitations and possible applications. [pdf]
     
     
125. Irina Chihaia and Thomas Gross   [ChihaiaG:04]   [published]
     Effectiveness of Simple Memory Models for Performance Prediction    
     IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS'04), Austin, 10-12 March 04
     Many situations call for an estimation of the execution time of applications, e.g., during design or evaluation of computer systems. In this paper we focus on large applications where the execution times heavily depend on the performance of the memory system. Since such applications are computationally expensive, direct simulation is not an option and an analytical model is called for. This paper addresses this problem by developing and evaluating two simple analytical models. These models focus on an application's interaction with the memory system. Applications are characterized by their memory access types. A regular application has continuous and strided memory accesses. An irregular application has three memory access types: continuous accesses, accesses within the same L1/L2 cache line, and random accesses. The analytical models are combined with results from micro-benchmarking or with appropriate performance estimates of memory accesses to predict application performance, either on real or future machines. We apply these models to executions of CHARMM (Chemistry at HARvard Molecular Mechanics) - a scientific application written in FORTRAN, SMV (Symbolic Model Verifier) - coded in C, and NS2 (Network Simulator) - coded in C++. For all three applications, the approaches described here produce results with 5% accuracy on average (compared to the effective run-time measured on a real SPARC system). [pdf]
     
     
126. Thomas Gross, Levente Szekrenyes, Cristian Tuduce   [GrossST:03]   [published]
     Increasing Student Participation in a Networked Classroom    
     Frontiers in Education (FIE2003), 5-8 Nov 2003, Boulder, USA
     
     
     
127. Christoph von Praun, Florian Schneider, Thomas Gross   [PraunSG:03]   [published]
     Load Elimination in the Presence of Side Effects, Concurrency and Precise Exceptions    
     International Workshop on Languages and Compilers for Parallel Computing (LCPC 2003), Texas, 2-4 Oct 03
     Partial redundancy elimination can reduce the number of loads corresponding to field and array accesses in Java programs. The reuse of values loaded from memory at subsequent occurrences of load expressions must be done with care: Precise exceptions and the potential of side effects through method invocations and concurrent updates in multi-threaded programs must be considered. This work focuses on the effect of concurrency on the load optimization. Unlike previous approaches, our system determines accurate information about side effects and concurrency through a whole-program analysis. Partial redundancy elimination is extended to exploit this information and to broaden the optimization scope. There are three main results: (1) Load elimination is effective even in the most conservative variant without side effect and concurrency analysis (avg. dynamic reduction of loads 21.1%, max. 55.6%). (2) Accurate side effect information can significantly increase the number of optimized expressions (avg. dynamic reduction of loads 26.4%, max. 66.1%). (3) Information about concurrency can make the optimization independent of the memory model, enables aggressive optimization across synchronization statements, and improves the number of optimization opportunities compared to an uninformed optimizer that is guided by a (weak) memory model (avg. dynamic reduction of loads 30.1%, max. 70.3%). [pdf]
     
     
128. Christoph von Praun and Thomas Gross   [VonPraunG:03b]   [published]
     Static Detection of Atomicity Violations in Object-Oriented Programs    
     ECOOP Workshop on Formal Techniques for Java-like Programs (FTfJP), 21 July 2003
     
     
     
129. Christoph von Praun, Thomas Gross   [VonPraunG:03a]   [published]
     Static Conflict Analysis for Multi-Threaded Object-Oriented Programs    
     ACM/SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2003), 8-11 June 2003, San Diego
     A compiler for multi-threaded object-oriented programs needs information about the sharing of objects for a variety of reasons: to implement optimizations, to issue warnings, to add instrumentation to detect access violations that occur at runtime. An Object Use Graph (OUG) statically captures accesses from different threads to objects. An OUG extends the Heap Shape Graph (HSG), which is a compile-time abstraction for runtime objects (nodes) and their reference relations (edges). An OUG specifies for a specific node in the HSG a partial order of events relevant to the corresponding runtime object(s). Relevant events include read and write access, object escape, thread start and join. OUGs have been implemented in a Java compiler. Initial experience shows that OUGs are effective to identify object accesses that potentially conflict at runtime and isolate accesses that never cause a problem at runtime. The capabilities of OUGs are compared with an advanced program analysis that has been used for lock elimination. For the set of benchmarks investigated here, OUGs report only a fraction of shared objects as conflicting and reduce the number of compile-time reports in terms of allocation sites of conflicting objects by 28-92% (average 64%). For benchmarks of up to 30 KLOC, the time taken to construct OUGs is, with one exception, in the order of seconds. The information collected in the OUG has been used to instrument Java programs with checks for object races. OUGs provide precise information about object sharing and static protection, so runtime instrumentation that checks those cases that cannot be disambiguated at compile-time is sparse, and the total runtime overhead of checking for object races is only 3-86% (average 47%).
     
     
130. Roger P. Karrer, Thomas Gross   [KarrerG:03]   [published]
     Multipath Streaming in Best-Effort Networks    
     IEEE ICC 2003, Anchorage, 11-15 May 2003
     Multipath streaming is used by resource intensive applications to stream th eir data over multiple, disjoint paths, thereby cumulating the resources of the different subpaths. The trend towards application-layer implementations of communication protoc ols allows the deployment of a multipath streaming protocol in the current Inte rnet. However, because resource availability fluctuates in the Internet, a multipath strea ming protocol must be combined with other mechanisms, e.g., adaptation, to address these fluctuations. This paper describes two approaches to combine adaptation and multipath streaming. The first approach separates the two mechanisms and th ereby allows multipath streaming to be transparent to the application, whereas the other approach combines the two mechanisms in the application context. This paper compares the two approaches along various parameters. It shows t hat the first approach is easier to deploy from an engineering point of view, but the separation of multipath streaming and adaptation yie lds significant drawbacks. Especially, synchronization problems due to differen t latencies along the paths that form the multipath setup may lead to a significant drop in the quality of the data.
     
     
131. Cristian Tuduce, Thomas Gross   [TuduceG:03]   [published]
     Organizing a distributed application in a mobile ad hoc network    
     2nd IEEE International Symposium on Network Computing and Applications (NCA-03), Cambridge, Mass., 16-18 April 2003
     A distributed application that operates in an ad hoc network formed by mobile nodes must limit its use of all-to-all communication since the overall capacity of such a network is severely constrained. To address this problem, we describe an algorithm that allows an application to impose a hierarchical structure on the participating nodes. A simple tree is maintained as hosts join and leave the ad hoc network. We evaluate this algorithm in the context of a collaboration tool for a network of Linux laptops using IEEE 802.11b network cards. Preliminary performance results from our mobile test-bed indicate that the application responds well to connectivity changes and is sufficiently agile to run in a highly mobile environment.
     
     
132. Kay Römer, Friedemann Mattern, Thomas Dübendorfer, Jürg Senn   [RoemerMDS:03]   [published]
     Smart Identification Frameworks for Ubiquitous Computing Applications     
     PerCom 2003 (IEEE International Conference on Pervasive Computing and Communications), March 2003
     In this paper, we present our results in the conceptual design and the implementation of ubiquitous computing applications using smart identification technologies. First, we describe such technologies and their potential application areas, followed by an overview of some applications we have developed. Based on the experiences we gained from the development of these systems, we point out design concepts that we find useful for structuring and implementing such applications. Building upon these concepts, we have created two frameworks based on distributed Java objects and Web Services to support the development of ubiquitous computing applications that make use of smart identification technology. We describe our prototype frameworks, discuss the underlying concepts and present some lessons learned. [pdf]
     
     
133. Christoph von Praun and Thomas Gross   [VonPraunG:03c]   [published]
     Compiling Multi-Threaded Object-Oriented Programs    
     International Workshop on Compilers for Parallel Computers (CPC), Amsterdam, 8-10 Jan 2003
     
     
     
134. Nicolae Chiurtu, Thomas Marzetta   [ChiurtuM:02]   [published]
     Random Coding Exponents for Unitary Space-Time Modulation    
     IEEE 2002 International Symposium on Information Theory - ISIT'02, Lausanne, June 30-July 5, 2002
     In this work we investigate a multiple antenna wireless link subject to flat Rayleigh block-fading, with no channel-state information available either to the transmitter or to the receiver. Computing the capacity of this channel is still an open problem. Recent work took an important step towards this by obtaining in close-form the probability density of the received signal when transmitting isotropically-random unitary matrices. The technique used for doing this -- which involves taking expectations with respect to the isotropically random unitary matrix -- has other interesting ramifications. In this paper we make use of this technique to obtain a variety of new bounds on the random coding exponent, which provide improved estimates, compared with the simple union bound, of the autocoding performance of codebooks of isotropically random unitary signals. [ps]
     
     
135. Samarjit Chakraborty, Thomas Erlebach, Simon Künzli, Lothar Thiele   [ChakrabortyEKT:02]   [published]
     Schedulability of Event-Driven Code Blocks in Real-Time Embedded Systems    
     39th Design Automation Conference (DAC), ACM Press, New Orleans, USA, 10-14 June 2002
     Real-Time systems are generally modeled as a collection of independent tasks, where each task generates a sequence of jobs, each of which is characterized by a ready-time, an execution requirement, and a deadline. The schedulability analysis of such a system is concerned with determining whether it is possible to assign to each job a processor time equal to its execution requirement, between its ready-time and its deadline. In the context of most real-time embedded systems, each such task is required to model an event-driven block of code, parts of which are triggered by external events and require to be executed within a given deadline from the triggering time. Such blocks of code are usually represented by their control flow graphs on some appropriate level of abstraction, where the vertices have associated deadlines and represent portions of code implementing some functionality, and the edges represent the flow of control. The vertices when triggered by external (or internal) events have to be executed within their associated deadlines. The schedulability analysis of such a collection of control flow graphs answers whether it is possible to execute all the vertices of all graphs within their deadlines, under all possible event triggering sequences. [pdf]
     
     
136. Kay Römer, Friedemann Mattern, Thomas Dübendorfer, Jürg Senn   [RoemerMDS:02]   [published]
     Infrastructure for Virtual Counterparts of Real World Objects    
     Technical Report ETHZ, 2002
     Based on our experience with a collection of prototypical ubiquitous computing applications, we have identified a number of common basic tasks which led to the design of some simple mechanisms that we have found useful for structuring and implementing such applications. Building upon these mechanisms, we have created a software infrastructure to support the development of tag-based ubiquitous computing applications. Our framework is targeted at applications where objects are tagged with Radio Frequency Identification tags (RFIDs), a simple but powerful means of bridging the gap between the physical and the virtual world. A central feature of our infrastructure are virtual counterparts. They form augmented representations of real world objects and encapsulate their state and behavior. This paper presents the rationale, design, and implementation of our prototype infrastructure. [pdf]
     
     
137. Hubaux, Jean-Pierre; Gross, Thomas; Le Boudec, Jean-Yves; Vetterli, Martin   [HubauxGLV:01]   [published]
     Towards self-organized mobile ad hoc networks: The terminodes project    
     IEEE Communications Magazine, vol. 39, no 1, p. 118-124
     This article provides a technical overview of mobile ad hoc networks and describes their long-term potential. It covers current research, and describes major technical challenges, including networking, real-time services, and software. It shows that by their very nature, mobile ad hoc networks can bring a paradigm shift in the way networks are organized and operated, and can even lead to a fundamental change in the relationships between information technology and societal organization. As an illustration of these concepts, the article also contains an overall description of our long-term research project, called terminodes [pdf]