[ main page ]

Paper Server : Real-Time Systems Group



Search documents

Search string

Search in
Title Authors Abstract Keywords

Show
Abstracts Bibtex Bibfile  Published documents only

18 documents found

49/2011 : Reconciling Fault-Tolerant Distributed Algorithms and Real-Time Computing
Heinrich Moser, Ulrich Schmid
Proceedings 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO'11)

Abstract: We present generic transformations, which allow to translate classic fault-tolerant distributed algorithms and their correctness proofs into a real-time distributed computing model (and vice versa). Owing to the non-zero-time, non-preemptible state transitions employed in our real-time model, scheduling and queuing effects (which are inherently abstracted away in classic zero step-time models, sometimes leading to overly optimistic time complexity results) can be accurately modeled. Our results thus make fault-tolerant distributed algorithms amenable to a sound real-time analysis, without sacrificing the wealth of algorithms and correctness proofs established in classic distributed computing research. By means of an example, we demonstrate that real-time algorithms generated by transforming classic algorithms can be competitive even w.r.t. optimal real-time algorithms, despite their comparatively simple real-time analysis.

Get transform.pdf (158.9922KB)


43/2010 : Real-Time Analysis of Round-based Distributed Algorithms
Alexander Kler, Heinrich Moser, Ulrich Schmid
Proceedings of the 1st International Real-Time Scheduling Open Problems Seminar (RTSOPS'10), in conjunction with 22nd Euromicro Conference on Real-Time Systems (ECRTS'10)

Abstract: Despite decades of research on networked fault-tolerant distributed systems, sound results on their real-time properties only exist for time-triggered synchronous systems: Given that classic distributed computing models are based on state machines with zero-time computing steps, queueing effects and scheduling are inherently abstracted away. We have developed a real-time distributed computing model based on non-zero-time jobs, which allows to reason about real-time properties of general distributed algorithms. In addition, we identified Min-Max-Plus algebra as a promising candidate for the real-time analysis of partially synchronous fault-tolerant distributed algorithms, where classic real-time analysis techniques are inapplicable as there are no time-triggered periodic job invocations.

Get main.pdf (52.9775KB)


11/2010 : Reconciling Fault-Tolerant Distributed Algorithms and Real-Time Computing
Heinrich Moser, Ulrich Schmid

Abstract: We present generic transformations, which allow to translate classic fault-tolerant distributed algorithms and their correctness proofs into a real-time distributed computing model (and vice versa). Owing to the non-zero-time, non-preemptible state transitions employed in our real-time model, scheduling and queuing effects (which are inherently abstracted away in classic zero step-time models, sometimes leading to overly optimistic time complexity results) can be accurately modeled. Our results thus make fault-tolerant distributed algorithms amenable to a sound real-time analysis, without sacrificing the wealth of algorithms and correctness proofs established in classic distributed computing research. By means of two examples, we demonstrate that real-time algorithms generated by transforming classic algorithms are competitive even w.r.t. optimal real-time algorithms, despite their comparatively simple real-time analysis.

Get RR.pdf (326.8887KB)


9/2010 : The Byzantine Generals' Round Duration
Heinrich Moser

Abstract: This research report analyzes the worst-case round duration of a fault-free run of the classic Byzantine Generals Algorithm in a distributed real-time system.

Get paper.pdf (60.5313KB)


/2009 : A Model for Distributed Computing in Real-Time Systems
Heinrich Moser

Get epsilon.pdf (851.1016KB)


77/2008 : Towards a real-time distributed computing model
Heinrich Moser
Theoretical Computer Science, Volume 410, Issues 6-7, 28 February 2009, Pages 629-659

Abstract: This paper introduces a simple real-time distributed computing model for message-passing systems, which reconciles the distributed computing and the real-time systems perspective: By just replacing instantaneous computing steps with computing steps of non-zero duration, we obtain a model that both facilitates real-time scheduling analysis, and retains compatibility with classic distributed computing analysis techniques and results. We provide general simulations and validity conditions for transforming algorithms from the classic synchronous model to our real-time model and vice versa, and investigate whether/which properties of real systems are inaccurately or even wrongly captured when resorting to zero step-time models. We revisit the well-studied problem of deterministic drift- and failure-free internal clock synchronization for this purpose, and show that no clock synchronization algorithm with constant running time can achieve optimal precision in our real-time model. Since such an algorithm is known for the classic model, this is an instance of a problem where the standard distributed computing analysis gives too optimistic results. We prove that optimal precision is only achievable with algorithms that take Ω(n) time in our model, and establish several additional algorithms and lower bounds.

Get journal.pdf (487.9033KB)


76/2008 : Topology Control for Fault-Tolerant Communication in Wireless Ad Hoc Networks
Bernd Thallner, Heinrich Moser, Ulrich Schmid
Wireless Networks (2010) 16:387-404, http://dx.doi.org/10.1007/s11276-008-0139-9

Abstract: Fault-tolerant communication and energy efficiency are important requirements for future-generation wireless ad hoc networks, which are increasingly being considered also for critical application domains like embedded systems in automotive and aerospace. Topology control, which enables multi-hop communication between any two network nodes via a suitably constructed overlay network, is the primary target for increasing connectivity and saving energy here. In this paper, we present a fault-tolerant distributed topology control algorithm that constructs and continuously maintains a k-regular and k-node-connected overlay for energy-efficient multi-hop communication. As a by-product, it also builds a hierarchy of clusters that reflects the node density in the network, with guaranteed and localized fault-tolerant communication between any pair of cluster members. The construction algorithm automatically adapts to a dynamically changing environment, is guaranteed to converge, and exhibits good performance as well.

Get journal.pdf (476.2061KB)


43/2008 : Optimal Deterministic Remote Clock Estimation in Real-Time Systems
Heinrich Moser, Ulrich Schmid
12th International Conference On Principles Of DIstributed Systems (OPODIS'08)

Abstract: In an OPODIS'06 paper, we laid down the foundations of a real-time distributed computing model (RT-Model) with non-zero duration computing steps, which reconciles correctness proofs and real-time scheduling analysis of distributed algorithms. By applying the RT-Model to the well-known drift-free internal clock synchronization problem, we proved that classic zero step-time analysis sometimes provides too optimistic results. The present paper provides a first step towards worst-case optimal deterministic clock synchronization with drifting clocks in real-time systems, which is an open problem even in classic distributed computing. We define and prove correct an optimal remote clock estimation algorithm, which is a pivotal function in both external and internal clock synchronization, and determine a matching lower bound for the achievable maximum clock reading error in the RT-Model. Moreover, we show how to combine our optimal clock estimation algorithm with existing clock synchronization algorithms.

Get paper.pdf (326.5723KB)


17/2007 : Towards a real-time distributed computing model
Heinrich Moser

Abstract: This paper introduces a simple real-time distributed computing model for message-passing systems, which reconciles the distributed computing and the real-time systems perspective: By just replacing instantaneous computing steps with computing steps of non-zero duration, we obtain a model that both facilitates real-time scheduling analysis and retains compatibility with classic distributed computing analysis techniques and results. We provide general simulations and validity conditions for transforming algorithms from the classic synchronous model to our real-time model and vice versa, and investigate whether/which properties of real systems are inaccurately or even wrongly captured when resorting to zero step-time models. We revisit the well-studied problem of deterministic drift- and failure-free internal clock synchronization for this purpose, and show that no clock synchronization algorithm with constant running time can achieve optimal precision in our real-time model. Since such an algorithm is known for the classic model, this is an instance of a problem where the standard distributed computing analysis gives too optimistic results. We prove that optimal precision is only achievable with algorithms that take Omega(n) time in our model, and establish several additional algorithms and lower bounds.

Get journal.pdf (391.8994KB)


123/2006 : Construction of a Fault-Tolerant Wireless Communication Topology Using Distributed Agreement
Heinrich Moser, Bernd Thallner
Proceedings of the 2006 Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS 2006)

Abstract: This paper presents a proven correct implementation of a distributed topology construction algorithm based upon agreement on minimal-weight clusters for creating a k-regular, k-node connected fault-tolerant communication network. It adapts to crashing nodes, moving nodes and changing communication cost and is guaranteed to converge. We analyze the requirements imposed upon the system model by this class of agreement-based algorithms and show that our implementation works in asynchronous distributed systems augmented with unreliable failure detectors.

Get paper.pdf (181.7842KB)


109/2006 : Optimal Clock Synchronization Revisited: Upper and Lower Bounds in Real-Time Systems
Heinrich Moser, Ulrich Schmid
Proceedings of the International Conference on Principles of Distributed Systems (OPODIS'06)

Abstract: This paper introduces a simple real-time distributed computing model for message-passing systems, which reconciles the distributed computing and the real-time systems perspective: By just replacing instantaneous computing steps with computing steps of non-zero duration, we obtain a model that both facilitates real-time scheduling analysis and retains compatibility with classic distributed computing analysis techniques and results. As a by-product, it also allows us to investigate whether/which properties of real systems are inaccurately or even wrongly captured when resorting to zero step-time models. We revisit the well-studied problem of deterministic internal clock synchronization for this purpose, and show that, contrary to the classic model, no clock synchronization algorithm with constant running time can achieve optimal precision in our real-time model. We prove that optimal precision is only achievable with algorithms that take Omega(n) time in our model, and establish several additional lower bounds and algorithms.

Get paper.pdf (179.1797KB)


106/2006 : Reconciling Distributed Computing Models and Real-Time Systems
Heinrich Moser, Ulrich Schmid
Real-Time Systems Symposium 2006 (RTSS'06)

Abstract: This paper presents a simple real-time distributed computing model for message-passing systems, which reconciles the distributed computing and the real-time systems perspective: By just replacing instantaneous computing steps with computing steps of non-zero duration, we obtain a model that both facilitates real-time scheduling analysis and retains compatibility with classic distributed computing analysis techniques and results. So far, we have developed general simulations and validity conditions for transforming algorithms from the classic synchronous computing model (without clock drift) to our real-time model and vice versa, and have started investigating whether/which properties of real systems are inaccurately or even wrongly captured when resorting to zero step-time models. One example is the Omega(1) time complexity lower bound for optimal deterministic internal clock synchronization, which turned out to be Omega(n) in the real-time model.

Get paper.pdf (124.0186KB)


75/2006 : Construction of a Fault-Tolerant Wireless Communication Topology Using Distributed Agreement
Heinrich Moser, Ulrich Schmid
Junior Scientist Conference 2006

Abstract: This paper presents a proven correct implementation of a distributed topology construction algorithm based upon agreement on minimal-weight clusters for creating a Delta-regular, Delta-node connected fault-tolerant communication network. It adapts to crashing nodes, moving nodes and changing communication cost. We analyze the requirements imposed upon the system model by this class of agreement-based algorithms and show that our implementation works in asynchronous distributed systems augmented with unreliable failure detectors.

Get abstract.pdf (89.2051KB)


71/2006 : Optimal clock synchronization revisited: Upper and lower bounds in real-time systems
Heinrich Moser, Ulrich Schmid

Abstract: This paper introduces a simple real-time distributed computing model for message-passing systems, which reconciles the distributed computing and the real-time systems perspective: By just replacing instantaneous computing steps with computing steps of non-zero duration, we obtain a model that both facilitates real-time scheduling analysis and retains compatibility with classic distributed computing analysis techniques and results. We provide general simulations and validity conditions for transforming algorithms from the classic synchronous model (without clock drift) to our real-time model and vice versa, and investigate whether/which properties of real systems are inaccurately or even wrongly captured when resorting to zero step-time models. We revisit the well-studied problem of deterministic internal clock synchronization for this purpose, and show that no clock synchronization algorithm with constant running time can achieve optimal precision in our real-time model. Since such an algorithm is known for the classic model, we have found an instance of a problem where the standard distributed computing analysis gives too optimistic results. We prove that optimal precision is only achievable with algorithms that take Omega(n) time in our model, and establish several additional lower bounds and algorithms.

Get epsilon.pdf (337.9082KB)


78/2005 : Topology Control for Fault-Tolerant Communication in Wireless Ad-Hoc Networks
Bernd Thallner, Heinrich Moser, Ulrich Schmid

Abstract: Energy efficiency and fault-tolerance are the most important issues in the development of next-generation wireless ad hoc networks and sensor networks. Topology control as a low level service (typically below classic network layers) governs communication among all nodes and is hence the primary target for increasing connectivity and saving energy. In this paper, we present a fault-tolerant topology construction algorithm for energy-efficient and fault-tolerant multi-hop communication in a two-tier network consisting of a large number of wireless nodes and a few gateway nodes (e.g. base stations responsible for exchanging data with other networks). Using only local information, like distance/channel attenuation to neighbors, our fully distributed algorithm efficiently constructs and continuously maintains a k-regular overlay graph that guarantees low total transmission power, is k-node-connected and ensures failure locality. It automatically adapts to a dynamically changing environment, is guaranteed to converge and exhibits good performance as well. As a by-product, our algorithm builds a hierarchy of clusters that reflects the node density in the network, with guaranteed and localized fault-tolerant communication between any pair of cluster members.

Get journal.pdf (301.8545KB)


9/2005 : Topology Control for Fault-Tolerant Communication in Highly Dynamic Wireless Networks
Bernd Thallner, Heinrich Moser
The Third International Workshop on Intelligent Solutions in Embedded Systems (WISES 2005)

Abstract: Energy efficiency and fault-tolerance are the most important issues in the development of next-generation wireless ad hoc networks and sensor networks. {em Topology control} as a low level service (typically below the traditional layer structure) governs communication among all nodes and is hence the primary target for increasing connectivity and saving energy. In this paper, we present an improvement of our topology control algorithm for very dynamic networks and low power devices (e.g. sensor nodes). The algorithm constructs a fault-tolerant topology for energy-efficient and fault-tolerant multi-hop communication in a two-tier network consisting of a large number of wireless nodes and a few gateway nodes (e.g. base stations responsible for exchanging data with other networks). Using only local information, like distance/channel attenuation to neighbors, our fully distributed algorithm efficiently constructs and continuously maintains a $mydelta$-regular overlay graph that guarantees low total transmission power, is $mydelta$-node-connected and ensures failure locality. It automatically adapts to a dynamically changing environment, is guaranteed to converge, builds a hierarchy of clusters that reflects the node density and exhibits good performance as well.

Get paper_wises05.pdf (174.3965KB)


/2005 : Distributed Construction of a Fault-Tolerant Wireless Communication Topology for Networked Embedded Systems
Heinrich Moser

Abstract: This master's thesis presents a proven-correct implementation of a distributed topology construction algorithm based upon the Thallner topology construction method for creating a minimal Delta-node connected fault-tolerant overlay graph. The algorithm works in asynchronous fault-tolerant distributed systems augmented with failure detectors. A detailed proof shows that given a perfect propose module and a period of network stability, the unique minimal overlay graph is built. This thesis also contains a solvability analysis examining how the algorithm can be implemented in the presence of simple crash failures, in the crash-recovery model and in the presence of lossy links.

Get da-moser.pdf (445.2656KB)


39/2004 : Distributed Construction of Fault-Tolerant Overlay Networks: Construction Algorithm
Heinrich Moser, Bernd Thallner

Get RR39-2004.pdf (221.2285KB)



[ main page ]