# Embedded Systems Engineering Scientific Project (182.706)

### [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).

Course setup: The organization of this course is very similar to writing a (non-practical) Master/PhD thesis, albeit with much less size and tighter supervision.

### 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 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; exceptional papers can and shall be submitted to a conference or a journal. More details are available below.

**Prerequisites** are basic knowledge in some relevant area of computer engineering (like fault-tolerant distributed algorithms, real-time scheduling, asynchronous digital design, dependable VLSI circuits) and basic knowledge and interest in scientific work (level of 180.765 Wissenschaftliches Arbeiten).

There is no need to enroll into this course, but you do need to find a supervisor at our institute who is able and willing to take your topic.

Grading will be based on the following components:

*1st paper assessment*(20%): Assessment of the first version (= "submitted version") of your paper. In order to get some early feedback, you also have to present your paper; 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 and announced in the TI Research Presentations. All presentations will usually take place 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 approval of your supervisor, of course). Here is a list of sample topics related to (part of) the work of our research group that may serve as an appetizer:

- Krishnendu Chatterjee, Andreas Pavlogiannis, Alexander Kößler, and Ulrich Schmid. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. In Proceedings of the IEEE 35th IEEE Real-Time Systems Symposium, RTSS 2014, Rome, Italy, December 2-5, 2014, pages 118-127, 2014.
- Manfred Schwarz, Kyrill Winkler, and Ulrich Schmid. Fast consensus under eventually stabilizing message adversaries. In Proceedings of the 17th International Conference on Distributed Computing and Networking, ICDCN '16, pages 7:1-7:10, New York, NY, USA, 2016. ACM.

- 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).
- 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, Thomas Nowak, and Ulrich Schmid. Unfaithful glitch propagation in existing binary circuit models. IEEE Transactions on Computers, 65(3):964-978, March 2016.
- 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.

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. Some amount of work should go into the selection process. Your choice should focus on paper that have a significant theoretical component. An implementation-related topic is possible, however, 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 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 the foundations of a solution 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 (or some specific style for a targetet conference), 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 may be assigned some paper(s) for reviewing. Please be sure to adhere to some reasonable reviewing standards, as e.g. known from the seminar 180.765 Wissenschaftliches Arbeiten. 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].

**Milestones****:** The milestones can be individually chosen, even across semester boundaries.

**Topic assignment**: Choose your "starting" paper (please make sure to also send your supervisor the .pdf in case of a choice of your own).**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, your supervisor will not approve it, so it is best to talk with him in advance about your plans, in particular, 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 (if any).**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: