CPSC 689-608: Special Topics in Discrete Algorithms
for Mobile and Wireless Networks
Spring 2009
[Announcements]
[Syllabus]
[Calendar]
[Reading List]
[Assignments]
[Useful Links]
- 3/26: Class on Wednesday, Apr 1 is replaced with
the Parasol seminar by Prof. Hagit Attiya on the same
day, 10:00 - 11:00 AM, in room 307 HRBB.
- 2/6: I have added information about the project (more
information is here) and added
the due dates to the calendar.
Back to beginning
Instructor:
Prof. Jennifer Welch
Office: 425G Bright Bldg
Office Hours: TBA;
other times by appointment
Email: welch@cse.tamu.edu
Office Phone: 845-5076
Lecture:
Mondays, Wednesdays, Fridays,
11:30 - 12:20, ARCC (Langford Architecture Center, Bldg C) room 206
Textbook:
None. We will use papers from the research literature.
Prerequisite:
CPSC 629 (Analysis of Algorithms) or equivalent, or permission
of the instructor.
At least one of
CPSC 619 (Networks and Distributed Computing),
CPSC 662 (Distributed Processing Systems), or
CPSC 668 (Distributed Algorithms and Systems)
is recommended.
This is a theoretical course.
We will be focusing on algorithms that have provable properties
of correctness, complexity and/or optimality.
A background in distributed systems or networking would be helpful in
appreciating possible applications of the results in the course, but is not
essential.
This course is based on the course
6.885 at MIT
, taught by Prof. Nancy Lynch and Dr. Fabian Kuhn in Fall 2008.
Course Goals:
This course will cover distributed algorithms for mobile (and some
non-mobile) wireless ad hoc networks, including networks with
interesting interactions with the real world.
We will focus on algorithms that can be described precisely, and that
have relatively well-defined correctness, fault-tolerance, and
performance requirements.
Our aim is to understand the existing theory of wireless network
algorithms and contribute to its further development.
Thus, we would like to:
-
Understand the nature of wireless ad hoc network settings. What are
typical correctness, reliability, and performance properties that can
be assumed? What are the ``right'' complexity measures to use for
evaluating algorithms?
-
Identify important, well-defined problems and subproblems that must
be solved by distributed algorithms in wireless ad hoc networks.
These will include problems of low-level and higher-level
communication, time synchronization, localization, network
configuration, resource allocation, tracking, and data management.
-
Learn about the most important existing algorithms for many of these
problems, and identify places where additional algorithmic work is
needed.
-
Identify some inherent limitations (lower bound and other
impossibility results) on the solvability of problems in wireless
networks.
-
Identify useful abstraction layers for programming wireless
networks.
The course is aimed at theoretically-inclined graduate students
with a strong interest in mobile and/or wireless networks, and at graduate
students working in systems and application areas who are interested
in algorithm design and analysis.
Course Content:
The course will cover the following topics.
We will proceed roughly through the ``layers'' of a wireless
network design:
- Part I: Basics
- physical layer, MAC layer, time synchronization, localization
- Part II: Communication
- global broadcast, routing, location services
- Part III: Building and maintaining network structures
- topology control, clustering, unit-disk graphs and related
models, wakeup problem, maximal independent sets, coloring
- Part IV: Middleware
- local infrastructure, token circulation, leader election,
resource allocation, group communication, compulsory
protocols, virtual node layers
- Part V: Applications
- data aggregation, population protocols, implementing atomic
memory, robot and vehicle motion coordination
Assignments and Grading:
Students in the
course will be required to read one or two papers before each class,
to turn in a short report on the papers read,
to participate in the class discussions, and to do a project.
Your grade will be based on these components:
- paper summaries 50%: One or two papers will be assigned
for you to read for each class. For each paper you must turn
in a typed summary and critique of the paper at the beginning
of class. Some questions may be assigned for you to answer
as well. More information is here.
- term project 30%: For your project, you can
either go into more depth on a topic covered in the class,
or work on an original research idea, or write a survey.
Due dates are listed in the calendar.
More information is here.
- class participation 20%: based on attendance and your
level of participation (quality and quantity) in the class discussions.
Course grades will be assigned according to this scale:
| percent of total points
| 90-100
| 80-89
| 70-79
| 60-69
| < 60
|
| letter grade
| A
| B
| C
| D
| F
|
Academic Integrity:
The Aggie Honor Code states
"An Aggie does not lie, cheat or steal or tolerate those who do".
More information on academic integrity, plagiarism, etc. is available at
the Aggie Honor System Office web site
http://www.tamu.edu/aggiehonor,
including:
(Look under "Student Rules".) Please review this material.
For the assignments in this class, discussion of concepts with others
is encouraged, but all assignments must be done on your
own, unless otherwise instructed.
If you use any source, reference it/him/her,
whether it be a person, a paper, a book, a solution set, a web page or
whatever.
You MUST write up the assignments in your own words.
Copying is strictly forbidden.
Every assignment must be turned in with
this
cover sheet, which lists all sources you used.
Americans with Disabilities Act (ADA) Policy Statement:
The Americans with Disabilities Act (ADA) is a federal
antidiscrimination
statute that provides comprehensive civil rights protection for
persons
with disabilities. Among other things, this legislation requires that
all students with disabilities be guaranteed a learning
environment that provides for reasonable accommodation of their
disabilities. If you believe you have a disability requiring an
accommodation, please contact the Department of Student Life,
Services for Students with
Disabilities in Cain Hall, Rm. B118,
or call 845-1637.
Back to beginning
| Date
| Topic
| Reading and Assignments Due
|
| Part I: Basics |
| Wed, 1/21
| Introduction
| .
|
| Fri, 1/23
| Physical Layer; MAC Layer (part 1)
| Summaries of Balakrishnan Ch 11, and Vaidya Chs 1-2
|
| Mon, 1/26
| MAC Layer (part 2)
| Summaries of Bharghavan et al. and Chockler et al.
|
| Wed, 1/28
| Collision Detection
| Summaries of Gallager (sec I and IV) and Komlos & Greenberg
|
| Fri, 1/30
| Multi-Access Channels
| .
|
| Mon, 2/2
| Time Synchronization
| Summaries of Elson et al. and Karp et al.
|
| Wed, 2/4
| Time Synchronization Lower Bounds
| Summaries of Attiya et al. and Fan & Lynch
|
| Fri, 2/6
| Time Synchronization Lower Bounds
| .
|
| Mon, 2/9
| Localization
| Summary of Priyantha et al. (Cricket)
|
| Wed, 2/11
| More Localization
| Summaries of Savvides et al. and Moore et al.
|
| Fri, 2/13
| Yet More Localization
| Summary of Aspnes et al.
|
| Part II:
Communication |
| Mon, 2/16
| Network-Wide Broadcast
| Project proposal due (topic + 3 references)
|
| Wed, 2/18
| More Network-Wide Broadcast
| Summaries of Bar-Yehuda et al. (JCSS), Bar-Yehuda et al. (DC),
and http://www.wisdom.weizmann.ac.il/~oded/p_bgi.html
|
| Fri, 2/20
| Routing
| Summaries of Johnson & Maltz and Perkins & Royer
|
| Mon, 2/23
| Link Reversal
| Summary of Gafni & Bertsekas
|
| Wed, 2/25
| Link Reversal Routing
| Summary of Park & Corson
|
| Fri, 2/27
| Routing with Synthetic Distances
| Summaries of Rao et al. and Fang et al.
|
| Mon, 3/2
| Location Services
| Summary of Awerbuch & Peleg
|
| Wed, 3/4
| More Location Services
| Summary of Abraham et al.
|
| Fri, 3/6
| Yet More Location Services
| Summaries of Kranakis et al. and Karp & Kung
|
| Mon, 3/9
| Location-Based Routing
| .
|
| Part III:
Building and Maintaining Network Structures |
| Wed, 3/11
| Topology Control
| Summaries of Li et al. and Bahramgiri et al.
|
| Fri, 3/13
| More Topology Control
| Summaries of Wang & Li and von Rickenbach et al.
|
| Mon, 3/23
| Distributed Dominating Sets
| Project status report due; Summary of Jia et al.
|
| Wed, 3/25
| Lower Bounds for Distributed Dominating Sets
| Summary of Kuhn et al., "What Cannot Be Computed Locally"
|
| Fri, 3/27
| Sparse Partitions
| Summaries of Awerbuch & Peleg and Luby
|
| Mon, 3/30
| NO CLASS
| .
|
| Wed, 4/1
| Parasol seminar by Prof. Hagit Attiya, 10-11 AM, 307 HRBB
| .
|
| Fri, 4/3
| Quasi-Unit Disk Graphs
| Summaries of Attiya lecture and Kuhn et al.,
"Ad-Hoc Networks Beyond Unit Disk Graphs"
|
| Mon, 4/6
| Maximal Independent Sets
| Summary of Schneider & Wattenhofer, "A Log-Star..."
|
| Part IV:
Middleware |
| Wed, 4/8
| Local Infrastructure
| Summaries of Luo & Hubaux and Welsh & Mainland
|
| Fri, 4/10
| NO CLASSES
| .
|
| Mon, 4/13
| Token Circulation
| Summary of Malpani et al.
|
| Wed, 4/15
| Mutual Exclusion and Leader Election
| Summary of Ingram et al.
|
| Fri, 4/17
| Compulsory Protocols
| Summaries of Hatzis et al. and
Chatzigiannakis, Nikoletseas & Spirakis
|
| Mon, 4/20
| Virtual Infrastructure
| Project rough draft due; summaries of
Dolev et al. (virtual mobile nodes)
Chockler & Gilbert (virtual infrastructure)
|
| Part V:
Applications |
| Wed, 4/22
| More on Virtual Infrastructure
| Summary of Dolev et al. (GeoQuorums)
|
| Fri, 4/24
| Atomic Memory
| .
|
| Mon, 4/27
| Data Aggregation
| Summaries of
Shrivastava et al.;
Nath et al.
|
| Wed, 4/29
| Robot Coordination
| Summaries of
Walter, Welch, & Amato;
Defago & Konagaya
|
| Fri, 5/1
| Summary
| Project final draft due
|
| Mon, 5/4
| Project presentations
| .
|
| Tue, 5/5
| ATTEND FRIDAY CLASSES; Project presentations
| .
|
Here is the
course reading list.
It is a comprehensive bibliography; we will not be reading
all these papers. The calendar section will indicate which
papers to read for which class.
Back to beginning
Daily Paper Summaries:
For each class, one or two papers will be identified as mandatory readings;
others may be listed as supplemental.
For each mandatory paper, turn in a one or two page typed report
consisting of the following clearly marked sections:
- Complete bibliographic reference
- Summary of the main points of the paper,
including, but not limited to, key assumptions made
concerning the model of computation
- Why are the results new/interesting/significant
- Open questions: include some of your own, in addition to any
mentioned by the authors
- Your critique of the paper (is it relevant/interesting/correct
and why or why not; does it make good/bad/weird modeling choices;
how would you have done things differently; how does it relate
to other work; what is confusing, etc.)
Don't forget the cover page.
[Purpose]
[Topic]
[Approaches]
[Written Report]
[Oral Presentation]
[Deadlines]
Purpose: This assignment has several purposes:
- introduction to the technical literature in the area,
- application of ideas and techniques presented in class in a more
extensive and open-ended environment than in the homework,
- practice in writing technical documents,
- practice in making oral presentations
I encourage you to discuss your project with me as often as you like,
and at any stage, especially early on.
Topic:
Your project can be either a survey paper, an attempt to solve
an open problem in the literature or simplify an existing result
(perhaps by making some simplifying assumptions), or your own
research (subject to your advisor's approval).
Your topic should concern distributed algorithms for mobile and/or
wireless networks and
have a significant theoretical component (i.e., at least one
theorem) to it.
Implementations are only appropriate as an auxiliary to
some more theoretical results.
The course reading list is a good place to start looking for
ideas.
Approaches:
Some general ideas for approaches to take in your project:
- Read a few related papers and
- 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.
- Read a larger number of related papers (at least 10)
and write a survey paper.
There should be significant added value in your survey.
At minimum the papers should be well-organized, and for more
credit you should provide the reader with some new insights into
the papers and how they relate to each other.
For some good examples, see papers published in ACM Computing
Surveys, e.g., the paper by Androutsellis-Theotokis and Spinellis
on peer-to-peer content distribution technologies, vol. 36, no. 4,
2004. You must also come up with a list of at least five
open problems relating to your surveyed papers.
- Come up with a new problem based on some application area known
to you (perhaps through your own research) and try to solve it.
The problem and your approach must
be relevant to the course topic and goals!
Written Report:
The report is to be typed, at least 10 pages long and no more than
20 pages long.
Part of your grade will be based on the quality of your composition
(including spelling, grammar, logical flow).
Typical organization for a (nonsurvey) technical paper in this area is:
- introduction: informal explanation of problem, why it
is important/interesting, overview of the paper contents
- survey of related work
- definitions giving model of computation and precise problem statement
- results with proofs, including intuitive explanations
- conclusion, including open problems.
Your report must be written in your own words!
If you feel the need to quote directly from another paper, be sure
to put the quote inside quotation marks and cite the source; very
little, if any, of your paper should consist of direct quotations.
Oral Presentation:
You will have 20 minutes to present your work to the class
on the last week. Part of your grade will be based on the quality
of your presentation.
Deadlines:
- Mon, Feb 16: Proposal due: topic plus three relevant references.
- Mon, Mar 23: Status report due.
- Mon, Apr 20: Rough draft due.
- Fri, May 1: Final draft due.
- Mon, May 4 and Tue 5: 20-minute oral presentations
Back to beginning
Back to beginning