Partially Synchronous Distributed Real-Time Systems

Project homepage

The ultimate goal of PSRTS (Partially Synchronous Distributed Real-Time Systems) has been to add a proper real-time systems perspective to fault-tolerant distributed algorithms, by establishing a sound scientific basis for fault-tolerant distributed real-time systems with a high degree of concurrency and, hence, relaxed synchrony-by-design.

Project duration: 2008-2012  (final project report)

Project head: Ulrich Schmid

Supported by the Austrian Science Fund (FWF) under project number P20529 fwf.giffonds.gif

Selected accomplishments

Given the often severe power & space constraints and the criticality of aerospace/automotive applications, for example, increasing the concurrency in the system in order to better utilize scarce computing resources and to reduce the system's vulnerability is important. PSRTS has been devoted to the development of the scientific basis for such systems, and provided the following major results:

  1. A comprehensive Real-Time Model, which is the first distributed computing model that reconciles fault-tolerant distributed algorithms with real-time analysis. Essentially, it replaces zero-time state transitions by non-zero non-preemptable time computing steps and thus allows queueing effects and scheduling issues to enter the picture.
  • Heinrich Moser. Towards a real-time distributed computing model. Theoretical Computer Science, 410(6–7):629–659, Feb 2009.
  • Heinrich Moser and Ulrich Schmid. Reconciling fault-tolerant distributed algorithms and real-time computing. In Proceedings 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO'11), LNCS 6796, pages 42–53, Berlin, Heidelberg, 2011. Springer-Verlag.
  • Several instances of partially synchronous system models, like the time-free Asynchronous Bounded Cycle model, which provide different relaxations of synchrony conditions, as well as related algorithms for fault-tolerant distributed agreement and proof techniques.
    • Peter Robinson and Ulrich Schmid. The Asynchronous Bounded-Cycle Model. Theoretical Computer Science, 412(40):5580–5601, 2011. http://dx.doi.org/10.1016/j.tcs.2010.08.001. (Best paper award SSS'08)
    • Martin Biely, Peter Robinson, and Ulrich Schmid. Agreement in directed dynamic networks. In Proceedings 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO’12), LNCS 7355, pages 73–84, Reykjavik, Iceland, 2012, Springer-Verlag.
  • Advanced (real-time) analysis techniques, primarily based on non-standard algebras, and their application to some network algorithms. Essentially, these methods allow to treat distributed systems as linear dynamic systems.
    • Bernadette Charron-Bost, Matthias Függer, Jennifer L. Welch, and Josef Widder. Full reversal routing as a linear dynamical system. In 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), LNCS 6796, pages 101–112, Berlin, Heidelberg, 2011. Springer-Verlag.

     Besides its primary research results, PSRTS also stimulated several follow-up projects, including transdisciplinary research in formal verification and digital integrated circuits.