Germany

This work will demonstrate a new flavor of the RA-TDMA set of protocols, namely RA-TDMAs+, which uses IEEE-802.11 (WiFi) COTS hardware in ad-hoc mode to set up a dynamic mesh network of mobile nodes with high-bandwidth. The protocol uses topology tracking to configure the TDMA frame and robust relative synchronization to define the TDMA slots without resorting to a global clock and in the presence of interfering traffic. The demo will set up a small-scale testbed using COTS hardware, thus evidencing the feasibility of the approach, and it will show “live plots” of the temporal (synchronization) and topological views of the network.

IEEE RTSS 2021

Demonstrating RA-TDMAs+ for robust communication in WiFi mesh networks

**BQIT is a three day annual workshop** aimed at enabling leading UK and international academics and industrial partners to come together; to explore and discuss future ambitions and challenges in the field of **Quantum Information Technologies.** Since our conception in 2014 we have had 230 speakers and panellists who have presented their work and opinions on a range of topics, from quantum theory to innovation in industry.


### Welcome Message
The BQIT:21 team welcomes you to the eighth Bristol Quantum Information Technologies workshop! 

Last year was the first time in our workshop's history that we had gone fully virtual. The global circumstances that continue to impact us all professionally and personally have forced BQIT once again to be delivered as an all-virtual workshop for 2021. The access this creates to colleagues across the world who would otherwise be unable to join us, as well as being able to make the workshop free for all attendees due to the lower costs involved in delivering an online workshop, are just a couple of the extraordinary benefits of meeting online. This also means that we can welcome three times as many attendees to BQIT than previous years.   

We take this opportunity to thank each of our speakers and poster presenters for contributing their technical content, this year's sponsors, whose support this year enabled BQIT:21 to be free to all attendees, and to all of our attendees for joining us online this year. We recognise the extra energy required to stay connected and motivated during these difficult times, and are hugely encouraged to see so many of you willing to continue to connect with us on an online platform. 

It is our hope that you have a productive and enjoyable time while you engage and interact with BQIT:21, and to everyone that has helped take BQIT:21 online, thank you! 

**The BQIT board and organisation team **


![](https://assets.underline.io/uploads/markdown_image/1/image/a12e0c1ad3410144cb48557690e4ecaf.png)
### This year's workshop agenda is available here: [Virtual BQIT:21](https://drive.google.com/file/d/1QwsSM0ztnxC_lgUKf3TbO3GvnI44AQkY/view?usp=sharing)
For further information, please contact us at: **bqit-admin@bristol.ac.uk**

![](https://assets.underline.io/uploads/markdown_image/1/image/a12e0c1ad3410144cb48557690e4ecaf.png)

Bristol Quantum Information Technologies Workshop

technical paper

 **RTSS 2021** has successfully concluded. Hope you have enjoyed it, and look forward to seeing you next year in person.
    Announcement for the Awards:
 * Best Paper Award goes to: Monte Carlo Response-Time Analysis, Sergey Bozhko, Georg von der Brüggen, and Björn Brandenburg
 * Best Student Paper Award goes to: Automatic Energy-Hotspot Detection and Elimination in Real-Time Deeply Embedded Systems, Mohsen Shekarisaz, Lothar Thiele, and Mehdi Kargahi.
 * Best Solution Award for Industry Session goes to: Toward Real-Time Guaranteed Scheduling for Autonomous Driving Systems. Jinghao Sun, Tianyi Wang, Kailu Duan, Bin Lu, Jiankang Ren, Zhishan Guo, and Guozhen Tan.



The IEEE Real-Time Systems Symposium (RTSS) is the premier conference in the field of real-time systems, and is a venue for researchers and practitioners to showcase innovations covering all aspects of real-time systems, including theory, design, analysis, implementation, evaluation, and experience. 

Global scheduling of real time tasks with precedence constraints has received significant attention recently. Specifically, on multiprocessor systems, the directed acyclic graph (DAG) model well-represents parallelizable workloads with precedence constraints. Hence, many studies have recently been published analyzing DAG structures using decomposition and window-based analysis methods. We identified a set of schedulable DAG taskets that are hard-to-analyze using state-of-the-art window-based schedulability tests. Additionally, we observe that the window-based test solely depends on one structural feature of the DAG taskset, which raises concerns about its pessimism in many settings. In this paper, to address these concerns, for hard real-time sporadic implicit-deadline DAG tasksets, we perform LAG-based schedulability analysis, which offers a more holistic view of the taskset than the window-based analysis. We present a companion utilization-based schedulability test to the state-of-the-art, which considers additional structural features of DAGs. Our results show that by considering such features, our LAG-based test empirically dominates the state-of-the-art test on over 80% of the evaluated DAG tasksets. Moreover, combining our LAG-based test in conjunction with the window-based tests can achieve high schedulability in many cases.

LAG-based Analysis Techniques for Scheduling Multiprocessor Hard Real-Time Sporadic DAGs

Probabilistic timing guarantees enable a tradeoff between system safety and hardware costs in embedded real-time systems. A key metric for assessing whether timing requirements can be satisfied with sufficiently high probability is the worst- case deadline failure probability (WCDFP). This paper studies the WCDFP under earliest-deadline first (EDF) scheduling for tasks with several probabilistic execution modes (e.g., a low-needs “typical” mode and a resource-intensive “exceptional” mode). Under EDF, no known approach can bound the WCDFP for practically sized workloads since the time complexity of prior approaches is exponential in the number of jobs. This paper examines the structure of the EDF WCDFP problem and establishes a safe, efficiently computable over- approximation by restricting the analysis to a set of specific intervals and providing a criterion to stop the derivation early without risking under-approximation. The analysis first assumes independent jobs and is then extended to handle dependencies (i.e., acyclic task chains). An evaluation shows that (i) even if 99.9999% of the jobs must meet their deadlines, a significantly higher utilization is possible than in the deterministic case, (ii) the analysis is scalable to 30 tasks with more than 10 60 jobs in the hyperperiod, and (iii) assuming independence in the presence of dependent tasks can severely under-estimate the WCDFP.

Efficiently Approximating the Worst-Case Deadline Failure Probability under EDF

Real-time applications with high computational demand, e.g., autonomous driving, are emerging and their complex nature conforms to a DAG(directed acyclic graph) structure. We propose a conditionally optimal parallelization for real-time DAG tasks for global EDF, ensuring complete execution of all tasks within the deadline. To achieve this, we formalize a monotonic increasing property of both tolerance and interference to the parallelization option. Using such properties, we develop a unidirectional search algorithm that can assign parallelization options in polynomial time, which we formally prove the optimality. We observe significant improvement of schedulability through simulation experiment, and then in the following implementation experiment, we demonstrate that the algorithm is practically applicable for real-world use-cases.

Conditionally Optimal Parallelization of Real-Time DAG Tasks for Global EDF

Prior algorithms that have been proposed for the uniprocessor scheduling of systems of elastic real-time tasks have computational complexity quadratic (O(n^2)) in the number of tasks n, for both initialization and for admitting new tasks during run-time. In our work-already-published [1], we present a more efficient implementation in which initialization takes quasilinear (O(n log n)), and on-line admission control, linear (O(n)), time.

Linear-time admission control for elastic scheduling

In this paper, we report on the ongoing development of POET, the first foundational and automated response-time analysis tool. The certificates produced by POET are short, readable, and fully commented Coq files that can be machine-checked in (usually) minutes. Moreover, we describe the mechanisms implemented in POET to ensure the validity of the generated certificates. Finally, we report on a preliminary evaluation of the effectiveness and practicality of our approach on synthetic task sets.

Automatically Generated Response-Time Proofs as Evidence of Timeliness

Numerical simulations often play an important role when evaluating and comparing the performance of schedulability tests, as they allow to empirically demonstrate their applicability using synthesized task sets under various configurations. In order to provide a fair comparison of various schedulability tests, von der Brüggen et al. presented the first version of an evaluation framework for self-suspending task sets. In this work-in-progress, we further enhance the framework by providing more features to ease the use, e.g., Python 3 support, an improved GUI, multiprocessing, Gurobi optimization, and external task evaluation. In addition, we integrate the state-of-the-arts we are aware of into the framework. Moreover, the documentation is improved significantly to simplify the application in further research and development. To the best of our knowledge, the framework contains all suspension-aware schedulability tests for uniprocessor systems and we aim to keep it up-to-date.

Evaluation Framework for Self-Suspending Schedulability Tests

The temporal correctness of safety-critical systems is typically guaranteed via a response-time analysis (RTA). However, as the systems become complex (e.g., parallel tasks running on a multicore platform), most existing RTAs either become pessimistic or do not scale with respect to e.g., the number of tasks or period values. To make a trade-off between accuracy and scalability, recently, a new reachability-based RTA called schedule-abstraction graph (SAG) has been introduced by Nasri et al. It explores the space of possible decisions that a scheduling policy can take while dispatching a set of tasks or jobs on processing resources. The analysis is at least three orders of magnitude faster than other exact RTAs and is able to identify many more schedulable task sets than the existing fixed-point iteration-based analyses. One fundamental limitation of the SAG analysis is that in its reachability graph, each edge can only account for a single scheduling decision. Therefore, the graph grows exponentially when there are large uncertainties in the release time or execution time of the jobs. In this paper, we improve the scalability of the SAG analysis by introducing partial-order reduction (POR) rules that allow combining multiple scheduling decisions on one edge and hence avoiding combinatorial exploration of all possible scheduling decisions. An empirical evaluation shows that our solution is able to reduce the runtime by five orders of magnitude and the number of explored states by 98%.

Partial-Order Reduction in Reachability-based Response-Time Analyses

Measurement-based WCET methods are reliable as long as we know all the application behaviors at design-time. In particular, we need to observe all the possible execution time behaviors before the actual system run-time to get a reliable estimation. This is, unfortunately, difficult to achieve. In this work, we propose an online monitoring framework with the goal to detect, at run-time, unexpected application behaviors and trigger the probabilistic-WCET re-estimation when needed. The online monitoring and estimation framework allows dealing with unexpected situations, such as never-seen applications, faults, or incorrect offline estimations. The proposed approach is tested with simulated and real data.

Run-time pWCET estimation and quality monitoring

Intersections are critical elements of urban traffic management and are identified as bottlenecks prone to traffic congestion and accidents. Intelligent intersection management plays a significant role in improving traffic efficiency and safety determining, among other metrics, the waiting time that vehicles incur when crossing an intersection. This work presents a preliminary analysis of the worst-case response time of intersection management protocols that handle mixed traffic with autonomous and human-driven vehicles. We deduce theoretical bounds for such time considered as the interval between the injection of a vehicle in the road system and its departure from the intersection, considering different intersection management protocols for mixed traffic, namely the Synchronous Intersection Management Protocol (SIMP) and several configurations of the conventional Round-Robin (RR) policy. Simulation results validate the analytical bounds partially. Ongoing work addresses the queue dynamics and its reliable detection by traffic simulators.

Worst-Case Response Time of Intersection Management Protocols

In this paper, we propose to use Schedule Abstraction Graphs (SAGs) to determine exact worst-case latency of packets at an egress port of an Ethernet TSN switch with Time-aware Shapers (TASs). We briefly sketch how to apply the existing SAG framework in a TSN context and extend the framework with FIFO-queues and TASs.

Demonstrating RA-TDMAs+ for robust communication in WiFi mesh networks

Downloads

Next from IEEE RTSS 2021

LAG-based Analysis Techniques for Scheduling Multiprocessor Hard Real-Time Sporadic DAGs

Similar lecture

Robustness of Noisy Quantum Networks

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES