Seminar: Fault-Tolerant Distributed Real-Time Systems

Seminar (7CP)

Sommersemester 2013

Instructors: Björn Brandenburg & Allen Clement

Topic

Many safety-critical systems must be inherently distributed, are subject to stringent real-time constraints, and must remain fully functional in the face of transient and, to some extent, permanent subsystem failures. In particular, cyber-physical systems—systems in which computers closely monitor and interact with the physical environment—typically exhibit this combination of requirements.

Common examples from daily life include automotive systems (e.g., anti-lock brakes, drive-by-wire functionality, etc.), air traffic control, factory automation, and the monitoring and control of the power grid. In addition to satisfying highest reliability expectations, such safety-critical systems are also often subject to certification requirements and/or formal validation efforts. That is, not only must they work in practice, but it must also be possible to formally establish their correctness a priori.

The focus of this seminar is to explore the algorithmic foundations that allow the construction of analytically sound fault-tolerant distributed real-time systems.

Prerequisites

This is a research-oriented Masters-level course. Students are expected to have at least an undergraduate-level understanding of operating systems and distributed systems. Prior exposure to real-time systems is recommended but not required.

Students are expected to have had prior training in the principles of effective scientific communication (i.e., students should already know how to write a scientific report and how to give a proper talk). Students that do not satisfy this requirement should enroll in a “Proseminar” first. This seminar is not a public speaking class.

Signup

Due to the format of the seminar, there are only a small number of topics available. Students interested in participating in the seminar should register early using the signup form.

Organization

When: regular meetings every Tuesday from 16:00 (c.t.) to 18:00.

The first meeting is on April 23.

Where: room 005, E1 5 (MPI-SWS building, UdS Campus).

Attendance policy: Seminars thrive on lively discussions. Therefore, attendance is mandatory. Absences require prior approval by the instructors (with the obvious exception of medical emergencies).

Format

The course is split into two phases.

Initially, there will be a few lectures covering real-time and distributed systems basics to establish a common terminology and a common ground for discussion, followed by a (short) graded quiz.

• Slides: Introduction to multiprocessor real-time systems

In the second phase, topics covering a small number of research papers will be assigned to participating students. Students are expected to give a lecture presenting the key concepts and techniques and write a brief synopsis of their assigned topic (4–8 pages).

• Lecture: each student will present her/his assigned paper(s) in a 30–45 minute presentation. The presentation will be graded both on factual correctness and presentation style. The goal of the presentation is to teach your fellow students the key insights and techniques of the assigned paper(s). Do not attempt to provide a comprehensive summary, that is, you do not have to discuss every detail. Rather, convey the key ideas and the intuition underlying the solution.
• Synopsis: each student will summarize her/his assigned paper(s) in a 4–8 page abstract. The written summary is due a day before the presentation and will be handed out to all participants. It should convey the key points of the papers and will be graded on correctness of both language and content. All text must be your own words or clearly marked as a quote. Similarly, all figures and illustrations must be your own work or marked with a citation in the caption. This includes all material taken from the work(s) being summarized. Plagiarism is unacceptable.
• Participation: each participant is expected to actively participate in the discussion and to skim the paper(s) under discussion prior to class. (Bring a copy to class for reference during discussion.)

The instructors reserve the right to deduct grade points for repeated failure to contribute in class.

Covered Papers

We will cover six topic areas across seven meetings.

Time-Triggered Real-Time Systems

On May 28, presented by Björn Brandenburg and Allen Clement.

• H. Kopetz, A. Damm, C. Koza, M. Mulazzani, W. Schwabl, C. Senft, and R. Zainlinger (1989). Distributed fault-tolerant real-time systems: The Mars approach. IEEE Micro, 9(1):25–40.
• H. Koptez and G. Bauer (2003). The time-triggered architecture. Proceedings of the IEEE, 91(1):112–126.

Transient Faults in Real-Time Systems

On June 4, presented by Ufuoma Bright Ighoroje and Manohar Vanga.

• F. Many and D. Doose (2011), Scheduling Analysis under Fault Bursts. In Proccedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 113–122.

• I. Broster, A. Burns, and G. Rodriguez-Navas (2005). Timing Analysis of Real-Time Communication Under Electromagnetic Interference. Real-Time Systems, 30(1–2):55–81.

Further reading:

Optionally, read Burns et al. (1996) for a gentle introduction to the topic, and Davis et al. (2007) for some corrections pertaining to the schedulability analysis of CAN.

• A. Burns, R. Davis, and S. Punnekkat (1996). Feasibility Analysis of Fault-Tolerant Real-Time Task Sets. In Proceedings of the Eighth Euromicro Workshop on Real-Time Systems, pages 29–33.

• R. Davis, A. Burns, R. Bril, and J. Lukkien (2007). Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised. Real-Time Systems, 35(3):239–272.

Reliable Broadcast / Agreement

On June 11, presented by Aastha Mehta and Mennan Selimi.

• L. Lamport, R. Shostak, and M. Pease (1982). The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382–401.
• J. Rufino, P. Verissimo, G. Arroz, C. Almeida, and L. Rodrigues (1998). Fault-tolerant broadcasts in CAN. In: Digest of Papers of the 28th Annual International Symposium on Fault-Tolerant Computing, pages 150–159.

Clock Synchronization

On June 25, presented by Xioafan Zhang and Xiao Chen.

• L. Lamport and P.M. Melliar-Smith (1985). Synchronizing Clocks in the Presence of Faults. Journal of the ACM, 32(1):52–78.
• H. Kopetz and W. Ochsenreiter (1987). Clock Synchronization in Distributed Real-Time Systems. IEEE Transactions on Computers, (36)8:933–940.

Further reading:

• L. Lamport (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565.
• J. L. Welch and Nancy Lynch (1988). A new fault-tolerant algorithm for clock synchronization. Information and Computation, 77(1):1–36.
• M. Malekpour (2006). A Byzantine-Fault Tolerant Self-Stabilizing Protocol for Distributed Clock Synchronization Systems. In Proceedings of the Eighth International Symposium on Stabilization, Safety, and Security of Distributed Systems, pages 411–427.

Consensus (1)

On July 16, presented by Felipe Cerqueira and Raul Fernandes.

• A. Clement, E. Wong, L. Alvisi, M. Dahlin, and M. Marchetti (2009). Making Byzantine fault tolerant systems tolerate Byzantine faults. In Proceedings of the 6th USENIX symposium on Networked systems design and implementation, pages 153–168.
• G. Lima and A. Burns (2003). A consensus protocol for CAN-based systems. In Proceedings of the 24th IEEE Real-Time Systems Symposium, pages 420–429.

Consensus (2)

On July 23, Arpan Gujarati and Konstantin Kuznetsov.

• J. Burman, T. Herman. S. Kutten, and B. Patt-Shamir (2006). Asynchronous and Fully Self-Stabilizing Time-Adaptive Majority Consensus. In Proceedings of the 9th International Conferences on the Principles of Distributed Systems, pages 146–160.
• G. Lima and A. Burns (2007). A Priority-Based Consensus Protocol. In Proceedings of the 25th Brazilian Symposium on Computer Networks and Distributed Systems, pages 353–366.

Systems

On July 25, presented by Nicholas Merritt.

• H.-M. Huang and C. Gill (2006). Design and performance of a fault-tolerant real-time CORBA event service. In Proceedings of the 18th Euromicro Conference on Real-Time Systems, pages 42–51.
• K. Junsung, G. Bhatia, R. Rajkumar, and M. Jochim (2012). SAFER: System-level Architecture for Failure Evasion in Real-time Applications. In Proceedings of the 33rd Real-Time Systems Symposium, pages 227–236.