Adv. Topics in Dist. Sys. Spring 06. Presentation Schedule.

Date

and 

 Reviews  

Topic

Main Papers

More Papers (optional)

Must-see Papers if you're doing a project in the area.

• The mathematical theory of infectious diseases and its applications, N.T.J. Bailey, 1975 (out of print)

Decentralized (P2P) Systems

• The Gnutella protocol specification v 0.4, Document revision 1.2, www.clip2.com

Decentralized (P2P) Systems

• Chord: a scalable peer-to-peer lookup service for Internet applications, I. Stoica et al, SIGCOMM 2001

• 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

• 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

• 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

• 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

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. 

• 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
• CoDNS: Improving DNS Performance and Reliability via Cooperative Lookups, KyoungSoo Park et al, OSDI 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.
• 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

• Scalability of reliable group communication using overlays, F. Baccelli et al, Infocom 2004.

• OceanStore: An Architecture for Global-Scale Persistent Storage ,  J. Kubiatowicz, ASPLOS 2000 

• 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

• TAG: A Tiny Aggregation service for ad-hoc sensor networks, S. Madden, et al, OSDI 2002

• A framework for time indexing in sensor networks, He et al, ACM TOSN 2005.

• DIFS: A distributed index for features in sensor networks, B. Greenstein et al, SNPA 2003

• 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

• Localized algorithms in wireless ad-hoc networks: location discovery and sensor exposure, S. Meguerdichian et al, Mobihoc 2001

• Amorphous Computing, H. Abelson et al, CACM 2000.

• End to end arguments in system design, Saltzer, Reed and Clark, 1984 
• A comparison of overlay routing and multihoming route control, A. Akella et al, SIGCOMM 2004.
• Preserving peer replicas by rate-limited sampled voting, P. Maniatis et al, SOSP 2003

• On transport layer support for peer to peer networks, H-Y. Hsieh et al, IPTPS 2004.

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

• The Byzantine Generals problem, L. Lamport et al, TOPLAS 1982
• Practical Byzantine Fault-Tolerance, Castro et al, OSDI 1999.
• BAR Fault Tolerance for Cooperative Services. A. Aiyer et al, SOSP 2005.

Project Survey Report due, 11.59 pm [12pt font, single-sided, 3 pages max]

• On the design of distributed protocols from differential equations, I. Gupta, PODC 2004

• Implementing Declarative Overlays. Boon Thau Loo et al, SOSP 2005.

• A protocol family approach to survivable storage infrastructures, J. Wylie et al, Fudico 2004.

• Routing design in operational networks: a look from the inside, D. A. Maltz et al, SIGCOMM 2004
• (short paper) Tools for the code generation, J. Ambrosio 2003.

• MapReduce: Simplified Data Processing on Large Clusters, Dean et al, OSDI 2004.
• MON: ON-demand overlays for distributed system management, Liang et al, WORLDS 2005.
• ACMS: The Akamai Configuration Management System
  Sherman et al, NSDI 2005.

• PlanetLab website
• Emulab Website
• WAIL website
• ModelNet website

• 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

• (short papers, for review read both)
  • 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

Spring Vacation - No Class.

Spring Vacation - No Class.

• 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

Indy [REVIEWS] [ppt slides]

• 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.
• Metarouting, Griffin et al, SIGCOMM 2005.

• 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.
• OSPF monitoring: architecture, design and deployment experience, A Shaikh et al, NSDI 2004.

Project Midterm Report due, 11.59 pm [12pt font, single-sided, 8 pages max]

• 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

• Botz-4-Sale: Surviving Organized DDoS Attacks That Mimic Flash Crowds, Srikanth Kandula et al, NSDI 2005.

• The case for cooperative networking, V. N. Padmanabhan et al, IPTPS 2002.

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

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

• Automatic Discovery of Mutual Exclusion Algorithms, Bar David et al, PODC 2003.

• Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience, D. Loguinov et al, SIGCOMM 2003 

• Splitstream, Castro et al, SOSP 2003.
• FeedTree: Sharing Web micronews with peer-to-peer event notification, Sandler et al, IPTPS 2005.
• Adaptive and Efficient Epidemic-style Protocols for Reliable and Scalable Multicast, Gupta et al, (to appear in) IEEE TPDS, 2006.
   

• 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.
• Matching events in a content-based subscription system.  M. K. Aguilera et al., PODC, 1999     

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

• 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

• Scalability, Fidelity and Containment in the Potemkin Virtual Honeyfarm, Michael Vrable et al, SOSP 2005.

• Vigilante: End-to-End Containment of Internet Worms, Manuel Costa, SOSP 2005.

• 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

• Secure routing for structured peer-to-peer overlay networks, M. Castro et al, OSDI 2002

• Peer-to-Peer File Sharing and Copyright Law: A Primer for Developers,
  F. von Lohmann, IPTPS 2003

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

• 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

(paper copies for the first three were handed out in class)

• 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

Poster Presentation of Project

Project Final Report due, 11.59 pm [12pt font, single-sided, 12 pages max]

• 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

• 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

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

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

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

• 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