CPSC 689-608: Special Topics in Discrete Algorithms for Mobile and Wireless Networks
Spring 2009

[Announcements] [Syllabus] [Calendar] [Reading List] [Assignments] [Useful Links]


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: 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:

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:

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 .

Reading List

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:
  1. Complete bibliographic reference
  2. Summary of the main points of the paper, including, but not limited to, key assumptions made concerning the model of computation
  3. Why are the results new/interesting/significant
  4. Open questions: include some of your own, in addition to any mentioned by the authors
  5. 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:

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:

  1. Read a few related papers and

  2. 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.

  3. 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:

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.


Back to beginning

Useful Links

Back to beginning