Course Schedule : Scattered Systems, Fall 2004

[10/19] Unless mentioned otherwise, you are expected to write reviews to only TWO of the papers in each session from now onwards.

By September 9, 5 pm, sign up for a presentation slot (from below, on the dates 9/14 through 11/16 only): Form groups of 2, or discuss with Indranil at one of his office hours (Tu, Th 3.30-5 pm, 2112 SC).

Your work (presentations and reviews) should be original and independent. If you reuse slides from someone else's presentation, please acknowledge them. The standard university policies on original work, cheating and attribution apply to these presentations.

A final note to all: You are encouraged to read ahead of the class, especially if you find one (or more) topics that interest you enough to want to do a project and write a paper on. As a tip, some of the more interesting topics occur in the second half of the course.

Date	Slides and Reviews	Topic	Main Papers	More Papers (optional) *Must-see Papers if you're doing a project in the area.*
8/26	Indranil [slides]	Introduction	The mathematical theory of infectious diseases and its applications, N.T.J. Bailey, 1975 (out of print)
8/31	Indranil [slides]	Decentralized (P2P) Systems	The Gnutella protocol specification v 0.4, Document revision 1.2, www.clip2.com
9/2	Indranil [slides]	Decentralized (P2P) Systems	Chord: a scalable peer-to-peer lookup service for Internet applications, I. Stoica et al, SIGCOMM 2001
9/7	Indranil [slides]	Sensor Networks	Smart Dust TinyOS	Research challenges in wireless networks of biomedical sensors, L. Schwiebert, ACM Sigmobile 2001 Research challenges in environmental observation and forecasting systems, D.C. Steere et al, Mobicom 2000 Design considerations for distributed microsensor systems, A. Chandrakasan et al, CICC 1999
9/9	Indranil [slides]	Basic Distributed Computing Concepts	Impossibility of distributed consensus with one faulty process, Fischer, Lynch and Patterson, Journal ACM 1985 Time, clocks and the ordering of events in a distributed system, L. Lamport, Communications ACM 1978	Distributed snapshots: determining global states of distributed systems, Chandy and Lamport, ACM TOCS 1985
9/14	Jin Liang [slides] [reviews]	Overlays and DHTs	Resilient overlay networks , D. Andersen et al, SOSP 2001 Freenet: a distributed anonymous information storage and retrieval system, I. Clarke et al, 2000 Kelips, I. Gupta et al, IPTPS 2003	Pastry: scalable, distributed object location and routing for large-scale peer-to-peer systems, A. Rowstron et al, Middleware 2001. A routing underlay for overlay networks, A. Nakao et al, SIGCOMM 2003 A scalable content addressable network, S. Ratnasamy et al, SIGCOMM 2001 Viceroy: a scalable and dynamic emulation of the butterfly, D. Malkhi et al, PODC 2002
9/16	Charles Yang & Ted Pongthawornkamol [slides] [reviews]	Epidemics	Epidemic algorithms for replicated database maintenance, A. Demers et al, PODC 1987. Gossip-based ad hoc routing, Z. Haas et al, Infocom 2002 Bimodal multicast, K Birman et al, ACM TOCS 1999	Immunology as information processing, S. Forrest et al, 2000. Efficient epidemic-style protocols for reliable and scalable multicast, I. Gupta et al, SRDS 2002.
9/21	Zahid Anwar [slides] [reviews]	P2P Apps (1)	Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, A. Rowstron et al, SOSP 2001 SHARP: an architecture for secure resource peering, Y. Fu et al, SOSP 2003 Scalability of reliable group communication using overlays, F. Baccelli et al, Infocom 2004.	Peer-to-peer support for massively multiplayer games, B. Knutsson et al, Infocom 2004. Operating system support for planetary-scale network services, A. Bavier et al, NSDI 2004. OceanStore: An Architecture for Global-Scale Persistent Storage , J. Kubiatowicz, ASPLOS 2000. Wide-area cooperative storage with CFS, F. Dabek et al, SOSP 2001 Ivy: a read/write peer-to-peer file system, A. Muthitacharoen et al, OSDI 2002
9/23	Pradeep Kyasanur & Romit Roy Chaudhury [slides1] [slides2] [reviews]	Sensor Net Routing	A review of current routing protocols for ad hoc mobile wireless networks, E.M. Royer et al, IEEE Personal Communications 1999 Directed diffusion: A scalable and robust communication paradigm for sensor networks, C. Intanagonwiwat et al, Mobicom 2000 Locating and bypassing routing holes in sensor networks, Q. Fang et al, Infocom 2004.	Rumor Routing Algorithm For Sensor Networks, Braginsky et al Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Heinzelman et al Adaptive Protocols for Information Dissemination in Wireless Sensor Networks, Kulik et al Energy efficient routing in ad hoc disaster recovery Networks, G. Zussman et al, Infocom 2003
9/28	Al Harris [slides] [reviews]	The End-to-End Approach	End to end arguments in system design, Saltzer, Reed and Clark, 1984 ESRT : Event-to-Sink Reliable Transport in wireless sensor networks, Y. Sankarasubramaniam et al, Mobihoc 2003 Middleboxes: taxonomy and issues, RFC 3234, zvon.org (read entire article by following "Next" links),	Rethinking the design of the Internet: the end-to-end arguments vs. the brave new world, Blumenthal and Clark, ACM Trans. Internet Technology, 2001 Middleboxes no longer considered harmful, M. Walfish et al, OSDI 2004. Untangling the Web from DNS, M. Walfish et al, NSDI 2004.
9/30	Jigar Doshi [slides] [reviews]	In-network processing	TAG: A Tiny AGgregation service for ad-hoc sensor networks, S. Madden, et al, OSDI 2002 Time indexing in sensor networks, R. Zheng, G. He, et al, MASS 2004. Localized algorithms in wireless ad-hoc networks: location discovery and sensor exposure, S. Meguerdichian et al, Mobihoc 2001	Multi-resolution state retrieval in sensor networks, B. Deb et al, SNPA 2003 Robust location detection in emergency sensor networks, S. Ray et al, Infocom 2003 Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks, P. Levis et al, NSDI 2004. Localized edge detection in sensor fields, K.K.Chintalapudi et al, SNPA 2003 Optimal energy balanced algorithm for selection in single hop sensor network, M. Singh et al, SNPA 2003 Sensor deployment and target localization based on virtual forces, Y. Zou et al, Infocom 2003
10/5	Jintae Kim & Jungmin So [slides] [reviews]	P2P Apps (2)	A comparison of overlay routing and multihoming route control, A. Akella et al, SIGCOMM 2004. On transport layer support for peer to peer networks, H-Y. Hsieh et al, IPTPS 2004. Preserving peer replicas by rate-limited sampled voting, P. Maniatis et al, SOSP 2003
10/7	Moosa M. and Cheema Adeep Singh [slides] [reviews]	Algorithms for Systems	A sqrt-N algorithm for mutual exclusion in decentralized systems, M. Maekawa, ACM TOCS, Apr. 1985. A practical distributed mutual exclusion protocol in dynamic peer-to-peer systems, S-D. Lin et al, IPTPS 2004. Scalable and dynamic quorum systems, Naor and Wieder, PODC 2003	Replication strategies in unstructured peer-to-peer networks, E. Cohen et al, SIGCOMM 2002 Exploiting network proximity in peer-to-peer overlay networks, M. Castro et al, MSR TechReport 2002 Geometric ad-hoc routing: of theory and practice, F. Kuhn et al, PODC 2003 On the curvature of the Internet and its usage for overlay construction and distance estimation, Y. Shavitt et al, Infocom 2004.
10/12	Boris Capitanu & Ellick Chan [slides] [reviews]	A Step Back	(short papers) 2 P2P or Not 2 P2P, M. Roussopoulos et al, IPTPS 2004. (AND) Scooped, again, J. Ledlie et al, IPTPS 2003. Service capacity of peer-to-peer networks, X. Yang et al, Infocom 2004. The capacity of wireless networks, P. Gupta et al, IEEE Transactions on Information Theory, vol. IT-46, no. 2, pp. 388-404, March 2000
10/14	Indranil [reviews] [slides]	Protocol Design (1)	A protocol family approach to survivable storage infrastructures, J. Wylie et al, Fudico 2004. On the design of distributed protocols from differential equations, I. Gupta, PODC 2004 (short paper) Tools for the code generation, J. Ambrosio 2003.	Routing design in operational networks: a look from the inside, D. A. Maltz et al, SIGCOMM 2004
10/19	Pse-Hsi Chen & Yookyung Jo [slides] [reviews]	Membership	Rule Relaxation (on account of survey deadline): Select ONE paper from among the following for your class review. A gossip-based failure detection service, R. van Renesse et al, Middleware 1998 Using random subsets to build scalable network services, D. Kostic et al, USITS 2003 SWIM: Scalable Weakly-consistent Infection-style process group Membership protocol, A. Das et al, DSN 2002	CONGRESS:CONnection-oriented Group address RESolution Service, A. Tal et al, 1997 On scalable and efficient distributed failure detectors, I. Gupta et al, PODC 2001
10/21	James Newell [slides] [reviews]	Sources of unreliability in networks	Rule Relaxation (on account of survey deadline): Select ONE paper from among the following for your class review. Internet routing instability, C. Labovitz et al, SIGCOMM 1997 The synchronization of periodic routing messages, S. Floyd et al, IEEE/ACM TON, 1994. Characterising the use of a campus wireless network, D. Schwab et al, Infocom 2004.	Locating Internet routing instabilities, A. Feldmann et al, SIGCOMM 2004. Characterization of failures in an IP backbone, A. Markopoulos et al, Infocom 2004. A longitudinal survey of Internet host reliability, D. Long et al, SRDS 1995 End-to-end Internet packet dynamics, V. Paxson, SIGCOMM 1997 Measurement and modeling of the temporal dependence in packet loss, M. Yajnik et al, Infocom 1999 Route flap damping exacerbates Internet routing convergence , Z. M. Mao et al, SIGCOMM 2002 Route oscillations in I-BGP with route reflection, A. Basu et al, SIGCOMM 2002 Stability issues in OSPF routing, A. Basu et al, SIGCOMM 20 01 On the effect of traffic self-similarity on network performance, K. Park et al, WSC 1997 Measurement and analysis of the error characteristics of an in building wireless network SIGCOMM 1996 Modeling the performance of wireless sensor networks, C-F. Chiasserini et al, Infocom 2004.
10/22	Project Survey Report due, 11.59 pm [12pt font, single-sided, 3 pages max]
10/26	Vartika Bhandari [slides] [reviews]	Inside sensor nets	DIFS: A distributed index for features in sensor networks, B. Greenstein et al, SNPA 2003 Amorphous Computing (web site) - select two papers the CACM 2001 paper, and one other major paper
10/28	Indranil [slides] [reviews]	Protocol Design (2)	Randomized ID selection for peer-to-peer networks, G. S. Manku, PODC 2004 Composition and behaviors of probabilistic I/O automata, Wu et al, TCS 1997. OSPF monitoring: architecture, design and deployment experience, A Shaikh et al, NSDI 2004.	A composable service model with loss and a scheduling algorithm, S. Ayyorgun et al, Infocom 2004. Peer-to-Peer Approach to Resource Location in Grid Environments, A. Iamnitchi et al, 2003. The Click modular router, E. Kohler et al, ACM TOCS 2000.
11/2	Michael Treaster [slides] [reviews]	Security	The Byzantine Generals problem, L. Lamport et al, TOPLAS 1982 Secure routing for structured peer-to-peer overlay networks, M. Castro et al, OSDI 2002 TinySec: A Link Layer Security Architecture for Wireless Sensor Networks, Chris Karlof et al, Sensys 2004.	The Sybil Attack, J. R. Douceur, IPTPS 2002 Secure routing in wireless sensor networks: attacks and countermeasures, C. Karlof et al, SNPA 2003 Peer-to-Peer File Sharing and Copyright Law: A Primer for Developers, F. von Lohmann, IPTPS 2003
11/4	William Conner & Chris Banek [slides] [reviews]	Caching	The case for cooperative networking, V. N. Padmanabhan et al, IPTPS 2002. On the scale and performance of cooperative web proxy caching, A. Wolman et al, SOSP 1999 Caching technologies for web applications, C. Mohan (IBM), VLDB 2001	Squirrel: a decentralized, peer-to-peer web cache, S. Iyer et al, PODC 2002. Approximate caches for packet classification, F. Chang et al, Infocom 2004. Comparing strength of locality of reference - popularity, majorization and some folk theorems, S. Vanichpun, Infocom 2004.
11/9	Mayssam Sayyadian [reviews] [slides]	Practical theory perspectives	Matching events in a content-based subscription system. M. K. Aguilera et al., PODC, 1999 Evaluating the running time of a communication round over the Internet, O. Bakr et al, PODC 2002 Computation in Networks of Passively Mobile Finite-State Sensors, Dana Angluin, James Aspnes, Zoe Diamadi, Michael Fischer, Rene Peralta, PODC 2004.	Gryphon Home An efficient multicast protocol for content-based publish-subscribe systems, G. Banavar et al, ICDCS 1999 A reliable multicast framework for light-weight sessions and application level framing, S. Floyd et al, 1997 SCRIBE: the design of a large-scale event notification infrastructure, A. Rowstron et al, NGC 2001. Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience, D. Loguinov et al, SIGCOMM 2003
11/11	Indranil [reviews] [slides]	P2P Characteristic Studies	Rule Relaxation (on account of report deadline): Select ONE paper from among the following for your class review. Measurement, modeling, and analysis of a peer-to-peer file-sharing workload Krishna P. Gummadi et al, SOSP 2003 Availability and Locality Measurements of Peer-to-Peer File Systems, J. Chu et al, SPIE 2002. Small-world file sharing communities, A Iamnitchi et al, Infocom 2004.	A measurement study of peer-to-peer file sharing systems, S. Saroui et al, MMCN 2002 Free riding on Gnutella Adar and Huberman, First Monday, 2000
11/16	Indranil [reviews] [slides]	Handling Stress	Rule Relaxation (on account of report deadline): Select ONE paper from among the following for your class review. Understanding availability, R. Bhagwan et al, IPTPS 2003 Comparing the performance of DHTs under churn, J. Li et al, IPTPS 2004. A churn-resistant peer-to-peer web caching system, P. Linga et al, Wshop on Survivable & Self-Regenerative Systems 2003.	Handling Churn in a DHT, S. Rhea et al, Usenix 2004. High-reliability architectures for networks under stress, G. E. Weichenberg et al, Infocom 2004.
11/18	Indranil [reviews] [slides]	The Grid	Rule Relaxation (on account of report deadline): Select ONE paper from among the following for your class review. Grid: a new infrastructure for 21st century science, I. Foster, Physics Today, 2002 On death, taxes and the convergence of peer-to-peer and grid computing, I. Foster et al, IPTPS 2003	The anatomy of the Grid: enabling scalable virtual organizations, I. Foster et al, Intnl Journal High Perf. Computing Appl. 2001
11/23	THANKSGIVING BREAK
11/24	Project Midterm Report due, 11.59 pm [12pt font, single-sided, 8 pages max]
11/25	THANKSGIVING BREAK
11/30	Indranil [slides] [reviews]	Structure of Networks	Select TWO papers from among the following for your class review. Exploring complex networks, Steven Strogatz, Nature 2001 Scaling properties of the Internet graph, A. Akella et al, PODC 2003 Mapping the Gnutella network, M. Ripeanu et al, IEEE Computing Journal 2002	Implicit structure and the nature of blogspace, Adar et al. The anatomy of a large-scale hypertextual web search engine, Brin and Page DHT routing using social links, S. Marti et al, IPTPS 2004. Duncan Watt's Small World Project, Columbia Jon Kleinberg's Structure of Information Networks course
12/2	Ted Pongthawornkamol [slides] [reviews]	Automatic Computing and Inference	Select TWO papers from among the following for your class review. Model checking large protocol implementations, M. Musuvathi et al, NSDI 2004. Overview of CAIDA Tools (give overview, and discuss at least five tools from different categories) Total Recall: system support for automated availability management, R. Bhagwan et al, NSDI 2004.	Inferring TCP Connection Characteristics Through Passive Measurements, S. Jaiswal et al, Infocom 2004. Multiple source, multiple destination network tomography, M. Rabbat et al, Infocom 2004.
12/7	James Newell [slides] [reviews]	Selfish algorithms	Select ONE paper from among the following for your class review. The tragedy of the commons, G. Hardin, 1968 How bad is selfish routing, T. Roughgarden et al, FOCS 2000 Characterizing selfishly constructed overlay networks, B-G. Chun et al, Infocom 2004.	On Selfish Routing in Internet-Like Environments, L. Qiu , SIGCOMM 2003
12/9	Indranil [slides] [no reviews]	Misc. & Wrap-Up	(paper copies were handed out in class) Read all papers below. NO reviews are required. C. M. Christensen, Ch. 1 from "The Innovator's Dilemma" R. P. Feynman, "Metaplast Corp." R. Hoffmann, "Why buy that theory?", 2003 How (and how not) to write a good SOSP paper, R. Levin and D. D. Redell	Advice on Research and Writing (take with a grain of salt)
END OF CLASSES
12/17	Project Final Report due, 11.59 pm [12pt font, single-sided, 12 pages max]

Leftover		Economic Theory	Rationality and self-interest in peer to peer networks, J. Shneidman et et al, IPTPS 2003 Distributed algorithmic mechanism design: recent results and future directions, J. Feigenbaum et al, DIALM 2002. To share or not to share: an analysis of incentives to contribute in collaborative file sharing environments, K. Ranganathan, Wshop Economics of P2P systems 2003	Incentives for Cooperation in Peer-to-Peer Networks, K. Lai, Wshop Economics of P2P systems 2003 (short paper) The social cost of sharing, H. R. Varian, Wshop Economics of P2P systems 2003
Leftover		The future of sensor nets?	Research challenges in wireless networks of biomedical sensors, L. Schwiebert, ACM Sigmobile 2001 Research challenges in environmental observation and forecasting systems, D.C. Steere et al, Mobicom 2000 Design considerations for distributed microsensor systems, A. Chandrakasan et al, CICC 1999	Next century challenges: mobile networking for smart dust, J.M. Jahn et al, Mobicom 1999 System architecture directions for networked sensors, J. Hill et al, ASPLOS 2000 Next century challenges: scalable coordination in sensor networks, D. Estrin et al, Mobicom 1999
Leftover		P2P - Etc.	Starfish: highly-available block storage, E. Gabber et al, Usenix 2003. Turning the postal system into a generic digital communication mechanism, R. Y. Wang et al, SIGCOMM 2004.
Leftover		Topology and Naming	Algorithmic aspects of topology control problems for ad hoc networks, E. Lloyd et al, Mobihoc 2002 Unreliable sensor grids: coverage, connectivity and diameter, S. Shakkottai et al, Infocom 2003 An address-free architecture for dynamic sensor networks, J. Elson et al, 2000 Prophet address allocation for large scale MANETs, H. Zhou et al, Infocom 2003	Biologically Inspired Topology Control Mechanism for Multi-hop Wireless Network, Z. Huang et al, Mobihoc 2003

Scattered Systems Fall 04, Presentation Schedule