# Embedded Systems Engineering Scientific Project (182.743)

### [TISS-Seite] [Syllabus] [Aims and Scope] [Enrolling] [Grading] [Schedule] [The Project] [Other resources]

### Aim

This course permits first steps in own scientific work on selected topics of computer engineering. Based upon a (typically self-assigned) publications on some suitable topic in this field, a short paper shall be written and presented during the semester. In addition, the course is also an excellent opportunity to get in touch with our research projects and establishes a solid basis for related diploma thesises and dissertations.

### Subject

Possible topics (selection): Hybrid failure models, partially synchronous system models, self-stabilizing distributed algorithms; real-time scheduling, topology control and routing in dependable wireless networks; diverse limitations of the synchronous design paradigm, metastability and synchronizers, asynchronous design styles, delay models, testing and fault tolerance for asynchronous logic, self-healing circuits. An overview of current computer engineering research topics and potential supervisors at the contributing institutes/working groups is provided in the TI research presentations (http://ti.tuwien.ac.at/teaching/ti-research-presentations).

### Lecturer

Dipl.-Ing. Dr.techn. Schmid Ulrich

### Homepage

http://ti.tuwien.ac.at/ecs/teaching/courses/esescp/

This is a graduate-level optional course that aims at first steps in own scientific work in computer engineering. The goal is to find, select and read a few (theoretical) papers related to some individually assigned topic in the field, and to write and present a short LaTeX paper that unifies/integrates/extends the results in some way. More details are available below.

**Prerequisites** are basic knowledge in at least two areas of computer engineering (in particular, fault-tolerant distributed algorithms, real-time scheduling, asynchronous digital design, dependable VLSI circuits) and basic knowledge and interest in scientific work (level of 182.034 Seminar (mit Bakkalaureatsarbeit)).

Please enroll via myTI. All participants who are admitted to the course should also subscribe to the TUWIS LVA-Forum and News as some announcements may be posted there.

Grading will be based on the following components:

*1st paper assessment*(20%): Assessment of the first version (= "submitted version") of your paper (reviewed by myself and, maybe, by some of your colleagues). In order to get some early feedback, you have to present your paper before turning it in; note that this first presentation is not graded.- Reviews (10%): Quality of the reviews of the assigned papers.
*Paper presentation*(40%): Assessment of the performance in presenting the paper, according to usual (conference-type) criterions.*2nd paper assessment*(30%): Assessment of the final version of the paper.

In addition, attendance of at least three TI Research Presentations is mandatory.

Outstanding work may be submitted to a regular scientific conference in the field. In case of acceptance, the expenses for attending this conference will be paid!

The schedule is maintained dynamically. All presentations will be announced by email and usually take place on Tuesday (10:15-11:45) in the library of the Embedded Computing Systems Group (E182/2), Treitlstraße 3, 2nd floor.

**Purpose:** The project assignment has several purposes, namely,

- introduction to the scientific literature in the area,
- application of ideas and techniques presented in basic courses in a more extensive and open-ended environment than in homeworks,
- practice in writing technical documents (in LaTeX),
- practice in reviewing scientific papers,
- practice in presenting scientific papers.

**Assignment****:** Your project will be based upon some topic chosen by yourself (subject to my approval, of course). To help you in finding a suitable topic, there is a list of (typically recent) papers on "hot topics" related to the current work of our research group:

- Martin Biely, Peter Robinson and Ulrich Schmid. Solving k-Set Agreement with Stable Skeleton Graphs. Appeared in 16th IEEE Workshop on Dependable Parallel, Distributed and Network-Centric Systems, IPDPS'11 Workshop Proceedings p. 1488-1495.

- Peter Robinson and Ulrich Schmid. The Asynchronous Bounded-Cycle Model. In Proceedings of the 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'08), volume 5340 of Lecture Notes in Computer Science, pages 246-262, Detroit, USA, November 2008. Springer Verlag. (Best Paper Award).
- Matthias Függer, Ulrich Schmid, Gottfried Fuchs and Gerald Kempf. Fault-Tolerant Distributed Clock Generation in VLSI Systems-on-Chip. In Proceedings of the Sixth European Dependable Computing Conference (EDCC-6), pages 87-96. IEEE Computer Society Press, October 2006.
- Heinrich Moser and Ulrich Schmid. Optimal clock synchronization revisited: Upper and lower bounds in real-time systems. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS), LNCS 4305, pages 95-109, Bordeaux & Saint-Emilion, France, Dec 2006. Springer Verlag.
- Ulrich Schmid, Bettina Weiss, and Idit Keidar. Impossibility results and lower bounds for consensus under link failures. SIAM Journal on Computing, 38(5):1912-1951, 2009.
- Matthias Függer, Gottfried Fuchs, Ulrich Schmid, Andreas Steininger. On the Stability and Robustness of Non-Synchronous Circuits with Timing Loops. Proceedings 3rd Workshop on Dependable and Secure Nanocomputing, in conjunction with the 39th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'09), Lisabon, Portugal, June 2009.
- Gottfried Fuchs, Matthias Függer, Andreas Steininger. On the Threat of Metastability in an Asynchronous Fault-Tolerant Clock Generation Scheme 15th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC 2009), Chapel Hill, North Carolina, USA, May 2009.

Alternatively, you can get some inspiration from our list of current topics for practicals or this list of "classic" distributed computing papers, or even propose something of your own.

**Selection****:** After acquiring (from the library or the internet, see the tips below) and reading your "starting" paper(s), you have to find, select and read a few related paper from the literature. A significant amount of work should go into the selection process. Your choice should concern distributed algorithms and have a significant theoretical component to it. An implementation-related topic is possible if it relates somehow to theory, for instance, a simulation to verify or discover the average case performance of some algorithm. Some general ideas for how to select a suitable paper:

- Read a few related theoretical distributed computing papers and choose one (maybe even two) that allows to either
- propose a simpler version of a problem presented in a paper and develop a simpler solution to your problem. OR
- discover a new connection between the papers; for instance, show how the results in one paper can be used to improve or simplify the results in another paper. OR
- develop a new notation and/or result that can simplify and/or unify the results in these papers and redo the results in your new notation. OR
- solve an open problem related to the papers.

- Come up with a new problem based on some application related to the "starting" paper and try to solve it.
- Study a distributed algorithm that is used as the basis of a commercial product somehow based on the "starting" paper (remember that the World Wide Web is a giant distributed system).

Some good places to look for distributed computing papers are:

**Journals:***Distributed Computing**Journal of the ACM**Information and Computation*(formerly*Information and Control*)- IEEE Transactions on Parallel and Distributed Systems
- Journal of Parallel and Distributed Computing
*Journal of Algorithms**SIAM Journal on Computing**Algorithmica**Theoretical Computer Science**Information Processing Letters**ACM Transactions on Computer Systems**Mathematical Systems Theory**Acta Informatica**Journal of Computer and Systems Sciences**IEEE Transactions on Computers**IEEE Transactions on Software Engineering*

**Conference proceedings:**- ACM Symposium on Principles of Distributed Computing (PODC)
- International Symposium on DIStributed Computing (DISC) -- formerly International Workshop on Distributed Algorithms (WDAG)
- Dependable Systems and Networks (DSN) -- formerly Symposium on Fault-Tolerant Computing (FTCS)
- ACM Symposium on Theory of Computing (STOC)
- IEEE Symposium on Foundations of Computer Science (FOCS)
- IEEE Conference on Distributed Computing Systems (ICDCS)
- International Conference on Principles of Distributed Systems (OPODIS)
- International Parallel and Distributed Processing Symposium (IPDPS)

**The world-wide-web:**Many people have copies of their papers available on line. Here are some very useful links:

**Paper:** The paper should summarize and critically review the selected work w.r.t. the "starting" paper(s), and either extend it in some way or simplify the results by making some simplifying assumptions. It must be self-contained in that ot should not be needed to consult the original papers for general understanding. The paper is to be typed in LaTeX using the IEEE conference style, and should be at most 10 pages long. Part of your grade will be based on the quality of your composition (including spelling, grammar, logical flow). The typical organization for a technical paper in this area is:

- introduction (informal explanation of problem, why it is important/interesting, overview of the paper contents)
- formal definitions
- results, including intuitive explanations
- conclusion (including open problems).

As a general rule, very little, if any, of your paper should consist of copying the contents of the papers you read, and of course if you do quote from a paper, be sure to credit the source.

[To understand the rationale of the above, it is very instructive to see how rigidly top US universities handle the issue of academic integrity, plagiarism, etc. Consult the Texas A&M University Code of Honors for an example.]

**Reviewing**: You will be assigned some paper(s) for reviewing. Please be sure to adhere to some reasonable reviewing standards, as e.g. known from the Proseminar "182.031 Grundlagen wissenschaftlichen Arbeitens". Note that the quality and appropriateness of your review will affect your grade, so please refrain from unduly praising a bad paper [or unduly rejecting a good paper], even if it is written by some colleague.

**Milestones****:** The milestones need not be synchronized with your colleagues but can rather be individually chosen, even across semester boundaries.

**Topic assignment**: Choose your "starting" paper (please make sure to also send me the .pdf in case of a choice of your own). Note that a single topic and/or "starting" paper may be chosen by several participants, but you need to convince me that there are sufficiently many disjoint project proposals for the same topic.**Project proposal due:**Turn in your project proposal. The proposal must consist of half a page describing what you plan to do, as well as the .pdf of your selected papers. Please note that if your plan is not sufficiently convincing, I will not approve it, so it is best to talk with me in advance about your plans if you are considering borderline topics**First presentation**: Make a first conference-style presentation of your intended paper (20-25 min. talk + 5-10 min. questions) to get some early feedback. Of course, you are free to ask other colleagues to help you improving your paper (e.g. proof-reading) before turning it in.**Paper due**: Turn in your paper. [This step corresponds to the submission of your paper to a conference.]**Reviews due**: Turn in your reviews. Since we are adhering to blind reviewing, there is no way for the author of a reviewed paper to know, without being told by yourself, who has been reviewing his/her paper.**Presentation**: Make a conference-style presentation of your paper (20-25 min. talk + 5-10 min. questions).

Recommended books & papers:

- Nancy Lynch.
*Distributed Algorithms*. Morgan Kaufmann, 1996 - Gerard Tel.
*Introduction to Distributed Algorithms*, Cambridge University Press, 2000 - Sape Mullender.
*Distributed Systems*. Addison-Wesley, 1993 - D. Peleg.
*Distributed Computing: A Locality-Sensitive Approach*, SIAM, Philadelphia, PA, 2000

A few LaTeX links:

Miscellaneous: