| [Adl02] | M. Adler. Tradeoffs in Probabilistic Packet Marking for IP Traceback. In Proc. ACM STOC, 2002. |
| [AK04] | A. Agarwal and P. R. Kumar. Improved capacity bounds for wireless networks. Wireless Communications and Mobile Computing, Vol. 4, pp. 251-261, 2004. |
| [AM+03] | G. Aggarwal, R. Motwani, D. Shah, and A. Zhu. Switch scheduling via randomized edge-coloring. Proc. IEEE Symposium on Foundations of Computer Science, 2003. |
| [AC+00] | R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network Information Flow. IEEE Transactions on Information Theory, IT-46, pp. 1204-1216, 2000. |
| [AMS99] | N. Alon, Y. Matias and M. Szegedy. The space complexity of approximating the frequency moments. J. Comp. Sys. Sci. 58 (1999), 137-147. |
| [AS00] | N. Alon and J. H. Spencer. The Probabilistic Method, Second Edition. John Wiley and Sons, Inc., 2000. |
| [BJ+02] | Z. Bar-Yossef, T. S. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan. Counting Distinct Elements in a Data Stream. In Proc. RANDOM 2002. |
| [BL+03] | S. Banerjee, S. Lee, B. Bhattacharjee, A. Srinivasan, and R. Braud. Scalable Resilient Media Streaming. CS-TR 4482 and UMIACS TR 2003-51, Department of Computer Science, University of Maryland, College Park, May 2003. |
| [BBC04] | B. Bash, J. W. Byers and J. Considine. Approximately Uniform Random Sampling in Sensor Networks. Proc. of the 1st Workshop on Data Management in Sensor Networks (DMSN '04), Toronto, Canada, August 2004. |
| [BR94] | M. Bellare and J. Rompel. Randomness-efficient oblivious sampling. In 35th Annual Symposium on Foundations of Computer Science, pages 276-287, Santa Fe, New Mexico, 20-22 November 1994. |
| [BM02] | A. Broder and M. Mitzenmacher. Network Applications of Bloom Filters: A Survey. Proc. Allerton Conference, 2002. |
| [BC+02] | J. Byers, J. Considine, M. Mitzenmacher and S. Rost. Informed content delivery across adaptive overlay networks. Proc. SIGCOMM 2002. |
| [BLM02] | J. Byers, M. Luby and M. Mitzenmacher. A Digital Fountain approach to asynchronous reliable multicast. IEEE Journal on Selected Areas in Communications, Vol. 20, No. 8, 2002. |
| [Che52] | H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493-509, 1952. |
| [CL+04] | J. Considine, F. Li, G. Kollios and J. W. Byers. Approximate Aggregation Techniques for Sensor Databases. Proc. of the 20th IEEE Int'l Conference on Data Engineering (ICDE '04), Boston, MA, April 2004, pp. 449-460. |
| [CT91] | T. Cover and J. Thomas. Elements of Information Theory. Wiley, 1991. |
| [Dub98] | D. P. Dubhashi. Martingales and Locality in Distributed Computing. Proc. Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 174-185, 1998. |
| [DM+03] | D. P. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, and A. Srinivasan. Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. Proc. ACM-SIAM Symposium on Discrete Algorithms, pages 717-724, 2003. |
| [FFF99] | M. Faloutsos, P. Faloutsos and C. Faloutsos. On Power-Law Relationships of the Internet Topology. Proc. ACM SIGCOMM, 1999. |
| [Fei99] | U. Feige. Noncryptographic selection protocols. In Proc. FOCS 1999, pages 142-153. |
| [GS+04] | L. Girod, T. Stathopoulos, N. Ramanathan, J. Elson, D. Estrin, E. Osterweil, and T. Schoellhammer. A System for Simulation, Emulation, and Deployment of Heterogeneous Sensor Networks. In Proceedings of SenSys 2004, November 2004. |
| [GMS04] | C. Gkantsidis, M. Mihail and A. Saberi. Random Walks in Peer-to-Peer Networks. In Proceedings of INFOCOM, 2004. |
| [GB+04] | V. Gopalakrishnan, B. Bhattacharjee, S. Chawathe, and P. Keleher. Efficient Peer-to-Peer Namespace Searches. Technical Report CS-TR-4568, Dept. of Computer Science, University of Maryland, February, 2004. |
| [G2-04] | V. Gopalakrishnan, B. Silaghi, B. Bhattacharjee and P. Keleher. Adaptive Replication in Peer-to-Peer Systems. In The 24th International Conference on Distributed Computing Systems, March 2004. |
| [GK00] | P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, 46(2), pp. 388-404, 2000. |
| [HKK04] | K. Hildrum, R. Krauthgamer, and J. Kubiatowicz. Object location in realistic networks. In Proceedings of SPAA, 2004. |
| [Hoe63] | W. Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, 58:13-30, 1963. |
| [JP+03] | K. Jain, J. Padhye, V. N. Padmanabhan and L. Qiu. Impact of interference on multi-hop wireless network performance. Proceedings of the 9th Annual International conference on Mobile computing and Networking, pages 66-80, 2003. |
| [JT04] | R. Johari and J. N. Tsitsiklis. Efficiency loss in a Cournot mechanism for network resource allocation, 2004. |
| [KVV00] | R. Kannan, S. Vempala, and A. Vetta. On clusterings: good, bad and spectral. Proc. of the 41st IEEE Symposium on Foundations of Computer Science, 2000. |
| [KL+97] | D. Karger, E. Lehman, F. T. Leighton, M. Levine, D. Lewin, and R. Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 654-663, May 1997. |
| [KDG03] | D. Kempe, A. Dobra and J. Gehrke. Computing Aggregate Information using Gossip. In Proceedings of FOCS 2003. |
| [KM04] | D. Kempe and F. McSherry. A Decentralized Algorithm for Spectral Analaysis. In Proceedings of STOC 2004. |
| [KS04] | V. King and J. Saia. Choosing a random peer. Proc. ACM Symposium on Principles of Distributed Computing, pages 125-130, 2004. |
| [Kle00] | J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000. |
| [KL01] | J. Kleinberg and S. Lawrence. The Structure of the Web. Science 294(2001), 1849. |
| [KSW04] | J. Kleinberg, A. Slivkins, and T. Wexler. Triangulation and Embedding using Small Sets of Beacons. Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004. |
| [KN03] | M. Kodialam and T. Nandagopal. Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem. Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, pages 42-54, 2003. |
| [KSV78] | V. Kolchin, B. Sevastyanov, and V. Chistyakov. Random Allocations, Wiley, 1978. (A classic reference for occupancy problems.) |
| [KM+04] | V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. End-to-End Packet-Scheduling in Wireless Ad-Hoc Networks. In Proc. ACM-SIAM Symposium on Discrete Algorithms, pages 1014-1023, 2004. |
| [LMR94] | F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job shop scheduling in O(congestion+dilation) steps. Combinatorica, 14(2):167-180, 1994. |
| [LMR99] | F. T. Leighton, B. M. Maggs, and A. Richa. Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica, 19(2):1-27, 1999. |
| [LS93] | N. Linial and M. Saks. Low Diameter Graph Decompositions. Combinatorica, 13:441-454, 1993. (See Alessandro Panconesi's online notes for a nice description of the distributed algorithm and associated background.) |
| [Lu93] | M. Luby. Removing randomness in parallel computation without a processor penalty. Journal of Computer and System Sciences, 47(2):250-286, 1993. |
| [Lu02] | M. Luby. LT Codes. Proc. IEEE Symposium on Foundations of Computer Science, 2002. |
| [LM+01] | M. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. Spielman. Efficient Erasure Correcting Codes. IEEE Transactions on Information Theory, Vol. 47, No. 2, 569-584, 2001. |
| [MNW04] | G. Manku, M. Naor and U. Wieder. Know Thy Neighbour's Neighbour: The Role of Lookahead in Randomized P2P Networks. Proc. 36th ACM Symposium on Theory of Computing, 2004. |
| [MPS03] | M. Mihail, C. H. Papadimitriou, and A. Saberi. On Certain Connectivity Properties of the Internet Topology. Proceedings of FOCS 2003. |
| [MU04] | M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, to appear. |
| [MR95] | R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. |
| [Mut] | S. Muthukrishnan. Data Streams: Algorithms and Applications. (Periodically-updated writeup covering many topics in the data-stream model.) |
| [NEC] | The Network Coding Home Page. |
| [NIC] | The NICE Project, University of Maryland. |
| [PR04] | A. Panconesi and J. Radhakrishnan. Expansion properties of (secure) wireless networks. Proceedings of SPAA 04. |
| [PS97] | A. Panconesi and A. Srinivasan. Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds. SIAM Journal on Computing, Vol. 26, 350-368, 1997. |
| [PRR99] | C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. Theory of Computing Systems, Vol. 32, Number 3, pp. 241-280, 1999. |
| [PS+04] | J. Polastre, R. Szewcyk, A. Mainwaring, D. Culler and J. Anderson. Analysis of Wireless Sensor Networks for Habitat Monitoring. In Wireless Sensor Networks, Raghavendra, Sivalingam, and Znati, editors, Kluwer Academic Publishers, pp. 399-423, 2004. |
| [Raj02] | R. Rajaraman. Topology Control and Routing in Ad Hoc Networks: A Survey. SIGACT News 33:60-73, June 2002. |
| [Rou02] | T. Roughgarden. Selfish Routing. PhD Thesis, Department of Computer Science, Cornell University, May 2002. |
| [SWA03] | N. Spring, D. Wetherall, and T. Anderson. Reverse Engineering the Internet. Proc. Hotnets-II Workshop, 2003. |
| [SM+03] | I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications. IEEE/ACM Transactions on Networking, Vol. 11, No. 1, pp. 17-32, February 2003. |
| [Tar04] | É. Tardos. Games in Networks. Invited talk, STOC 2004. |
| [TB04] | G. Theodorakopoulos and J. Baras. Trust Evaluation in Ad-Hoc Networks. In Proc. ACM Workshop on Wireless Security, 2004. |
| [WL+01] | R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang. Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. In Proc. INFOCOM, 2001. |
| [WS98] | D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440-42, 1998. |
| [XK04] | F. Xue and P. R. Kumar. The number of neighbors needed for connectivity of wireless networks. Wireless Networks, pp. 169-181, Vol.10, No. 2, March 2004. |
| [YJB02] | S.-H. Yook, H. Jeong, and A.-L. Barabási. Modeling the Internet's large-scale topology. Proceedings of the National Academy of Sciences 99, 13382-13386 (2002). |
| [ZG+03] | J. Zhao and R. Govindan. Understanding Packet Delivery Performance In Dense Wireless Sensor Networks. Proceedings of the ACM Sensys, November 2003. |