Course Overview

Description

The formal study of algorithms for wireless networks has been an active research topic since the 1970s. Recently, however, it has received renewed interest, spurred by the increasing availability of cheap and versatile wireless chips. The question of what problems you can and cannot solve efficiently when communicating over the airwaves is now in urgent need of answers.

In this course, we will tackle the current state of the art research on this question. The field has been moving fast enough that there's no good survey available of what we know about these algorithms and what we need to know. The goal of this course is to produce such a survey. As detailed below, students will read and present research papers (guided by the professor). The class will culminate with the students synthesizing what we learned into a survey paper that will be submitted to a major computer science journal.

Along the way, we will identify multiple compelling research projects for those students interested in pursuing additional publications in the area over the summer.

Prerequisites

This course is open to all graduate students. Any specific technique needed to understand the papers will be taught as needed.

Goals

This course is intended to help new graduate students transition to a research-oriented mindset, and help more senior graduate students jump start their publication count. In more detail, there are three specific goals for this course:

The student will learn how to efficiently survey computer science research literature. (Techniques for tackling papers, including one-on-one instruction from the professor, is a major component of the course.)
The student will gain an expert-level knowledge on the current state of wireless algorithm research.
The student will be a co-author on a submitted journal paper and be exposed to several potential research projects to pursue, if interested, after the course concludes.

Student Responsibilities

As detailed in the syllabus below, we will cover two research papers in each class. Every student will be responsible for answering some basic questions about every paper we cover, due by the beginning of the class discussing the papers. As also detailed below, students will be responsible for answering a short lecture summary questions about each lecture, which will be sent out at the end of class and must be answered, via e-mail, the same day. In addition, most classes will led by a student who will be responsible for providing a more detailed presentation about the results and techniques from that day's papers. At the end of the semester, each student will be responsible for writing up a detailed summary in LaTex -- following a template and set of guidelines provided by the professor -- of the papers he or she presented in class.

Attendance in class and participation in our discussions is an important student responsibility. Absences should be rare and approved in advance, when possible.

Academic Integrity

Students are expected to work on their reading response questions on their own. It is okay to discuss papers with your classmates or the professor when working on your presentations. The presentations and associated write-ups, however, must be your own original work. No copy and pasting of existing text, or editing of existing text, is allowed. All writing must be done by the student from scratch.

Course Mechanics

Paper Reading Method

Below is the method we will use in this course for tackling research papers. It describes three levels of detail at which you can understand a paper. The key idea driving this course is that you must learn how to dive down to just enough detail when faced with a paper, but not more than you need at the moment. As described below, your reading response questions will help you practice the first level of detail, your presentations will help you practice the second, and we will practice the third level together in class.

Level 1: Identify what time complexity results are proved in the paper and how they compare to existing results. This process requires that you understand the problems being studied and the model, so that the parameters in the time complexities make sense. When comparing results to existing results be careful to match up model assumptions: Are the existing results making the same assumptions, or are their differences in the model they assume? What is the significance of these differences (do they make the problem harder or easier)? At this level of detail, you do not need to know how the results are obtained, just what they are and why you should care about them.
The goal of level 1 review is to help you quickly figure out what is known and not known in a literature and quickly place new work into the context of existing results. Most reading you do as a researcher will stop at this level of detail. You will practice this level a lot in the course.
Level 2: Take a result of particular interest and dive deeper to try to develop an intuition for why it works. If the result is an upper bound, describe the algorithm and understand why it has the stated running time. Once you understand the algorithm you can use the text in the paper, and the corresponding lemma statements, to develop some intuition for why this particular strategy works. If the result is a lower bound, describe the setup for the proof and seek out the intuition behind how they will use this setup to prove their final result.
The goal of level 2 review is to deepen your knowledge about the different types of strategies that have worked well in a given setting. Often, for example, when you encounter an exciting-sounding result in your field, you will want to find out whether the paper has innovated a new technique that might be useful to your work, or instead simply thrown more careful and complicated analysis at an existing technique.
Level 3: Take a specific proof and understand the details. You should be able to walk through the lemma statements that lead up to the final proof and sketch the mathematical/logical argument for why each statement is true. You should be able to do this without consulting the paper or your notes. A good place to start is by mapping out the lemma statements and building an understanding of which statements depend which other statements, and which statements ultimately combine to prove the main result. You can then tackle the lemmas, one by one, starting at the lowest level of the hierarchy, trying to understand the details.
The goal of level 3 review is to master a technique at a sufficient level of detail that you can adapt and apply it to your own problems. This is a time-consuming process, so level 1 and 2 will help ensure that you only apply it where the knowledge will prove important to your work. It is also an important process, as this level of understanding often unlocks new collections of results.

Reading Response Questions

As detailed in the schedule below, we will cover 1 - 2 papers in each class. You are responsible for submitting reading response questions for the papers covered in a class, by the beginning of the class. Late submissions will receive 0 points.

In more detail, your reading response must take 1 result from each of the papers, and perform a level 1 analysis. That is, you must describe the problem and model, identify the specific time complexity proved (every parameter in the time complexity must be explained), describe how it compares to existing results, and summarize why we should care about the result. If we cover 2 papers, for example, you will analyze 2 results, 1 from each.

Submit your reading response questions by e-mailing them to the professor with the subject line: COSC 747: Reading Response: Class X, where X is the corresponding class number.

Lecture Summary Questions

At the end of each lecture, the professor will e-mail the class a question about the material covered during the presentation (and surrounding discussion). The question will require only a short answer. To respond, simply reply to my e-mail with your answer. This is due by midnight the same day as the lecture.

If you pay attention in class and make sure you follow both the presentation and discussion surrounding the presentation it should take you less than a minute to answer the question. If you do not pay attention an answer may be difficult to come by at all. You may not collaborate on these answers.

Presentations

Students will rotate responsibility for presenting papers in the class, following a schedule that will be determined once the final enrollment is fixed. During a presentation, you must first walk the class through a level 1 analysis on all results in the papers covered in the class. You must then choose at least one result and walk the class through a level 2 analysis. Finally, by the beginning of the class in which you present, you must add a succinct summary of the papers to draft of the the class survey paper which we will keep in an SVN repository. These summaries will be brief (no more than one paragraph per paper), and you will be provided examples of what they should look like.

Your presentation should last around 45 - 50 minutes. If you worry that your presentation will run short, add additional level 2 analyses, or do a more detailed comparison of the results to existing work, to get it to the appropriate length.

A quick note on preparation: Because a presentation seems less concrete then a problem set, students sometimes assume they can get away with reading the papers at the last minute and winging their discussion. Don't do this. It is not difficult to tell the difference between a student who really knows the material and one who does not, and the latter will receive a low grade.

Presenter's Choice Presentations

As shown on the syllabus below, at the end of the semester, each student gets a chance to present a paper of his or her choice. Several students are assigned to each such lecture. They will each present one paper and the time will be split evenly among them.

For these lectures, it is the student's responsibility to find a new paper (i.e., that we have not covered yet) that studies algorithms in a wireless model. Please submit the paper to the professor for approval at least two days before your presentation.

Reading summary questions are not required for presenter's choice lectures. You do not have to do a final write-up on your presenter's choice papers. The professor will still send out lecture summary questions.

Final Write-Up

At the end of the semester, each student will be responsible for handing in a formal summary of each of the papers he or she presented in class. This does not include the presenter's choice papers.

These summaries should be handed in by the last day of classes for the semester in LaTex format. The professor will provide a detailed template/guidelines for these summaries. These write-ups should be understood to be similar to a take-home exam. That is, if you follow the template/guidelines, you will be forced to really understand the papers you present -- describing their model, problems, and results with clarity. The quality level expected for these write-ups is higher than the standard reading response summaries, as is reflected by their contribution to your final grade (see below).

The professor is happy to look at drafts of these summaries and provide feedback about where you are falling short of the template/guidelines. To maximize your chances of a good grade, it is highly recommended that you take advantage of this offer. Don't wait until the last minute, however, as the professor cannot guarantee same-day response or responses over the weekend.

Survey Paper

After the semester concludes, the professor will combine the final write-up summaries to produce a detailed annotated bibliography of the papers covered during the course. He will then massage this into the proper format for a survey paper and submitted with all students' names as co-authors. This will occur over the summer.

Grading

Students will be graded on their reading response questions, presentations, attendance/participation, and final write-up. In more detail, grades will be assigned on the following point scale:

0 - 2 points for each paper's reading response questions. 2 points means a good answer, 1 point means the answer was missing something significant, and 0 points means no answer was submitted or the answer was seriously deficient. Notice, each individual reading response submission is not worth many points, but they add up to something significant. This is intentional, as it allows a student to occasionally skip these questions -- e.g., during a particularly busy week -- without major impact on his or her final grade, so long as they usually submit good answers. We will cover around 40 - 50 papers in the class, so around 80 - 100 total points are available.
0 - 50 points for each presentation. These points cover your in-class presentation and write-ups for your assigned papers. Each student will be responsible for 6 - 7 presentations, so around 300 - 350 total points are available.
0 - 50 points for participation. The percentage of points you receive depends on the percentage of lecture summary questions you answer correctly. I reserve the right to deduct extra points for chronic absences or obvious lack of attention during lecture.
0 - 100 points for your final write-ups.

At the end of the semester, I will add up all the points earned by each student and decide where the cut offs are for A, B, and C work. These cut offs will be independent of the actual student scores, so it is completely possible for all students to earn an A (so long as you put in the required effort).

Office Hours

I hold regular office hours from 11:30 am to 1:00 pm on Thursdays, in my office at 342 A Saint Mary's Hall.

Schedule

The schedule below describes which papers we will cover in each class. You will be provided these papers electronically at the beginning of the class in an archive file. Each paper is named as follows: [last name of first author]-[publication year]. Some of the schedule is left empty -- these papers will be filled in as the class progresses.

Class Number	Date	Description	Presenter
1	1/9	Course Mechanics; Introduction to Wireless Algorithms
		Part 1: The Protocol Model
2	1/15	Wireless Networks as Multi-Access Channels N. Abramson. The ALOHA System: Another Alternative for Computer Communication (1970). [no reading response questions required] R. Gallager. A Perspective on Multi-Access Channels (1985). [no reading response questions required] J. Komlos and A. Greenberg. An Asymptotically Nonadaptive Algorithm for Conflict Resolution in Multiple-Access Channels (1985).	professor
3	1/17	Centralized Global Broadcast: Early Results I. Chlamtac and S. Kutten. On Broadcasting in Radio Networks -- Problem Analysis and Protocol Design (1985). I. Chlamtac and O. Weinstein. The Wave Expansion Approach to Broadcasting in Multihop Radio Networks (1991).	professor
4	1/22	Centralized Global Broadcast: Pursuing Optimality N. Alon, A. bar-Noy, N. Linial, and D. Peleg. A Lower Bound for Radio Broadcast (1991). L. Gasieniec, D. Peleg, and Q. Xin. Faster Communication in Known Topology Radio Networks (2007).	professor
5	1/24	Distributed Global Broadcast: Randomized Solutions R. Bar-Yehuda, O. Goldreich, and A. Itai. On the Time-Complexity of Broadcast in Multi-Hop Radio Networks: An Exponential Gap between Determinism and Randomization (1992). Errata Regarding: On the Time-Complexity of Broadcast in Multi-Hop Radio Networks: An Exponential Gap between Determinism and Randomization. [no reading response questions required; presenter should use errata to present results from above paper correctly] E. Kushilevitz and Y. Mansour. An \Omega(D/log(N/D)) Lower Bound for Broadcast in Radio Networks (1998).	Henry
6	1/29	Distributed Global Broadcast: Deterministic Solutions D. Kowalski and A. Pelc. Deterministic Broadcasting Time in Radio Networks of Unknown Topology (2002). D. Kowalski and A. Pelc. Broadcasting in Undirected Ad Hoc Radio Networks (2005). [also includes an important randomized result]	Keelan
7	1/31	Multihop Leader Election R. Bar-Yehuda, O. Goldreich and A. Itai. Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with No Collision Detection (1991). M. Ghaffari and B. Haeupler. Near Optimal Leader Election in Multi-Hop Radio Networks (2012).	Weitong
8	2/5	The Wake-Up Problem T. Jurdzinski and G. Stachowiak. Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks (2002). S. Daum, F. Kuhn and C. Newport. Efficient Symmetry Breaking in Multi-Channel Radio Networks (2012). [you are only responsible for the single result in Section 4.2, though you will need to read Section 4.1 to understand it.]	Xi
9	2/7	Local Broadcast M. Bender, M. Farach-Colton, S. He, B. Kuszmaul and C. Leiserson. Adversarial Contention Resolution for Simple Channels (2005). M. Ghaffari, B. Haeupler, N. Lynch and C. Newport. Bounds on Contention Management in Radio Networks (2012). *[Only read results for the classical model* (in this paper "classical" = "protocol").]**	Brendan
10	2/12	Distributed Network Structuring F. Kuhn, T. Moscibroda and R. Wattenhoffer. Initializing Newly Deployed Ad Hoc and Sensor Networks (2004). T. Moscibroda and R. Wattenhoffer. Maximal Independent Sets in Radio Networks (2005). [Ask about extra credit opportunity here.]	Tonghe
		Part 2: The Physical Model
11	2/14	Connectivity Scheduling: Early Results T. Moscibroda and R. Wattenhofer. The Complexity of Connectivity in Wireless Networks (2006). T. Moscibroda. The Worst-Case Capacity of Wireless Sensor Networks (2007).	Xi
12	2/19	Connectivity Scheduling: Optimal/Distributed Results M. M. Halldorsson and P. Mitra. Wireless Connectivity and Capacity (2012). M. M. Halldorsson and P. Mitra. Distributed Connectivity of Wireless Networks (2012).	Henry
13	2/21	Capacity and Link Scheduling: Centralized Results O. Goussevskaia, R. Wattenhofer, M. Halldorsson, and E. Welzl. Capacity of Arbitrary Wireless Networks (2009). M. M. Halldorsson and P. Mitra. Wireless Capacity with Oblivious Power in General Metrics (2011).	Keelan
14	2/26	Capacity and Link Scheduling: Distributed Results T. Kesselheim and B. Vocking. Distributed Contention Resolution in Wireless Networks (2010). M. Halldorsson and P. Mitra. Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model (2011).	Weitong
15	2/28	Dynamic Link Scheduling T. Kesselheim. Dynamic Packet Scheduling in Wireless Networks (2012). G. Pei and V. A. Kumar. Low-Complexity Scheduling for Wireless Networks (2012).	Changlong
16	3/12	Structuring Networks C. Scheideler, A. Richa, and P. Santi. An O(log n) Dominating Set Protocol for Wireless Ad-Hoc Networks under the Physical Interference Model (2008). D. Yu, Y. Wang, Q. Hua, and F. Lau. Distributed (Delta + 1)-Coloring in the Physical Model (2012).	Brendan
17	3/14	Global Broadcast T. Jurdzinski and D. Kowalski. Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks (2012). [Read results for broadcast and leader election. You can skip result on emulating stronger models.] D. Yu, Q. Hua, Y. Wang, H. Tan, and F. Lau. Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks Under the SINR Model (2012).	Tonghe
18	3/19	Connecting Physical Model to Other Models E. Lebhar and Z. Lotker. Unit Disk Graph and Physical Interference Model: Putting Pieces Together (2009). T. Jurdzinski and D. Kowalski. Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks (2012). [Read results for emulating stronger models.]	Changlong
		Part 3: Dynamic Models
19	3/21	Distributed Algorithms in Dynamic Networks, Part 1 C. Avin, M. Koucky, and Z. Lotker. How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs). (2008) F. Kuhn, N. Lynch, and R. Oshman. Distributed Computation in Dynamic Networks. (2010)	Henry
20	3/26	Distributed Algorithms in Dynamic Networks, Part 2 F. Kuhn, R. Osham, and Y. Moses. Coordinated Consensus in Dynamic Networks. (2011) A. Cornejo, S. Gilbert, and C. Newport. Aggregation in Dynamic Networks. (2012)	Keelan
21	4/2	Distributed Broadcasting in Dynamic Radio Networks A. Clementi, A. Monti, and R. Silvestri. Broadcasting in Dynamic Radio Networks. (2009) F. Kuhn, N. Lynch, C. Newport, R. Oshman, and A. Richa. Broadcasting in Unreliable Radio Networks. (2010)	Weitong
22	4/4	The Dual Graph Model K. Censor-Hillel, S. Gilbert, F. Kuhn, N. Lynch, and C. Newport. Structuring Unreliable Radio Networks. (2011) M. Ghaffari, N. Lynch, and C. Newport. The Cost of Radio Network Broadcast for Different Models of Unreliable Links. (Under Submission)	Xi
23	4/9	Shared Spectrum: Deterministic Algorithms. S. Dolev, S. Gilbert, R. Guerraoui, and C. Newport. Gossiping in a Multi-Channel Radio Network: An Oblivious Approach to Coping with Malicious Interference. (2007) S. Gilbert, R. Guerraoui, D. Kowalski, and C. Newport. Interference-Resilient Information Exchange. (2009)	Brendan
24	4/11	Shared Spectrum: Randomized Algorithms. S. Daum, S. Gilbert, F. Kuhn, and C. Newport. Leader Election in Shared Spectrum Radio Networks. (2012) S. Daum, M. Ghaffari, S. Gilbert, F. Kuhn, and C. Newport. Maximal Independent Sets in Multichannel Radio Networks. (Under Submission)	Tonghe
25	4/16	Single-Channel Jamming-Resistant Algorithms. B. Awerbuch, A. Richa, and C. Scheideler. A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks. (2008) V. King, J. Saia, and M. Young. Conflict on a Communication Channel. (2011)	Changlong
26	4/18	Presenter's Choice.	Henry, Keelan
27	4/23	Presenter's Choice.	Weitong, Xi, Brendan
28	4/25	Presenter's Choice.	Tonghe, Changlong

COSC 747 - Topics in Wireless Network Algorithms

Georgetown University

Prof. Calvin Newport

Tuesday and Thursday, 2:00 - 3:15 pm

3rd Floor Conference Room, Saint Mary's Hall