Elective in Computer Networks
II - Section 1
Models and methods for fully decentralized and ad-hoc
networks
Teacher:
Luca Becchetti
Syllabus
The
trend
towards
wireless
communication
affects
more
and
more electronic devices in almost every sphere of life.
Conventional networks rely on base stations, and the mobile
devices exchange the data in a star-like fashion. In contrast, current
research is mainly focused on networks that are completely
unstructured, but are nevertheless able to communicate (via several
hops), despite the low coverage of their antennas. A prominent example
is that of networks consisting of thousands of tiny computers,
equipped with sensors, which might be used to monitor
activities of interest: traffic in a city, ground humidity in
agricolture, evidence of a possible vulcano explosion. These networks
are self-organized and the standard paradigms for routing,
disseminating information and processing information have to be
revisited. The goal of this course is to provide an overview of
the most relevant aspects and research directions in the area.
Topics
- Introduction
- Vertex colouring
- Tree algorithms
- Dynamic networks
- Maximal independent set
- Synchronizers
Material
Textbook
[T] R.Wattenhofer
F. Kuhn.
Principles of distributed computing. Free download (thanks
to the authors!), available at
http://dcg.ethz.ch/lectures/podc_allstars/lecture/podc.pdf
Other
references
- [R1] Yehuda Afek, Noga Alon, Omer
Barad, Eran Hornstein, Naama
Barkai, Ziv Bar-Joseph.
A
Biological Solution to a Fundamental Distributed Computing
Problem. Science, Vol. 331
no. 6014 pp. 183-185, 2011.
Paper available at http://www.sciencemag.org/content/331/6014/183.full.pdf,
supplementary
material with proofs is available here
Parts covered in this course (tentative list):
- [T] Chapter
1 (no algorithms 5, 6 and 7)
- [T] Chapter
2
- [T]
Chapter 3
- [T]
Chaper 7: 7.1 - 7.3 (no proof for Thm. 7.3)
- [T]
Chapter 10: 10.1 and 10.3; [R1]: main
paper and proofs of main result given in supplementary material
- [T]
Chapter 12
Slides
Course slides and other references are available at http://dcg.ethz.ch/lectures/podc_allstars/index.html
Other slides that
were used by the instructor:
Notes: 1. The above slides contain snapshots
from Wattenhofer and Kuhn's textbook. These are simply the texts of
some propositions given in the textbook; 2. Slides are necessarily
succint and are mainly intended as a reference for the instructor. As
such, they may contain errors and inconsistencies. Using them to
prepare the exam is strongly discouraged.
Netlogo
Netlogo's web
site and download page is here: http://ccl.northwestern.edu/netlogo/. Here you can also
find the user manual. Tutorials are available here
Students
have to take a written exam and have to present a project.
Written Exam
The
written exam will consist of 2 or 3 assignments.
Project
Students
should participate to a project. The project will consist in an
assignment in which a group of maximum two students will
cooperate to performa simulation study (using Netlogo) on a
topic of choice (mostly but not necessarily among those
considered during the course), previously agreed with the
instructor. The outcome of the project will consist in i) the
Netlogo code produced to perform the experiments; ii) the data
(statistics) produced during the experiments; iii) a technical
report describing the work done and the results obtained. The
technical report should have the form of a conference paper. It
should be between 4 and 5 pages long and follow the ACM SIGs
proceedings format. Word and LateX templates are available at http://www.acm.org/sigs/publications/proceedings-templates#aL.
In particular, the report should contain an introduction, a
section describing the experimental setting (the dataset, the
problem studied, the performance indices considered etc.), one
section describing and commenting on the results obtained and a
conclusion section, highlighting significant aspects (positive
or negative) of the results you obtained, and pointing to
directions that in your opinion deserve further
investigation. The introduction should provide an overview
of the problem studied, the methods/approach used and the result
obtained. It should also point to and comment some key
references on the topic (e.g., the main papers in which the
approach you are using was proposed/used before).
It is expected that you devote some effort to the writeup of the
technical report. The way you present the material is important.
Your report should help me understand what you have done, the
critical decisions you hade to take etc. Reading or simply
browsing some well-written scientific paper will definitely help
you improve the presentation. To this purpose, a good idea is
reading the suggested references listed above!
Tools
You are expected to perform simulations of some of the
algorithms you saw during the course using Netlogo simulation
tool. Netlogo is one of the most prominent agent-based
simulation tools. It is freely available at Northwestern
University's Web site for download. On the Web site, you
also have access to other resources, such as manuals and
tutorials.
Grades
Each student will receive at most 20 points for the written exam
and at most 10 for the project.
Forming a group
Please contact me by email to notify the names of the members of
your team and receive your assignment. You can propose a topic
you liked and I will try to assign a related project to you.
Discussing your project
Each student should arrange an appointment and discuss the
project s/he participated in before taking part to the written
exam. Before that, I should receive by email (at least 3 days
before the appointment) a pdf copy of the report describing your
work. This means that I should receive this before any
participant to a group discusses his/her project with me.