| 2004 | A note on efficient aggregate queries in sensor networks. | Boaz Patt-Shamir |
| 2004 | Brief announcement: detecting malicious routers. | Alper Tugay Mizrak, Keith Marzullo, Stefan Savage |
| 2004 | Brief announcement: the synchronous condition-based consensus hierarchy. | Achour Mostfaoui, Sergio Rajsbaum, Michel Raynal |
| 2004 | Brief announcement: completing the lock-free dynamic cycle. | Maged M. Michael |
| 2004 | Analyzing Kleinberg's (and other) small-world Models. | Charles U. Martel, Van Nguyen |
| 2004 | Balanced binary trees for ID management and load balance in distributed hash tables. | Gurmeet Singh Manku |
| 2004 | Brief announcement: concurrent maintenance of rings. | Xiaozhou Li, Jayadev Misra, C. Greg Plaxton |
| 2004 | Completely fair SFE and coalition-safe cheap talk. | Matt Lepinski, Silvio Micali, Chris Peikert, Abhi Shelat |
| 2004 | Brief announcement: towards a secure indirection infrastructure. | Karthik Lakshminarayanan, Daniel Adkins, Adrian Perrig, Ion Stoica |
| 2004 | Brief announcement: name-independent compact routing in trees. | Kofi A. Laing |
| 2004 | Brief announcement: efficient clustering in unstructured radio networks. | Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer |
| 2004 | What cannot be computed locally! | Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer |
| 2004 | Geometrically aware communication in random wireless networks. | Gady Kozma, Zvi Lotker, Micha Sharir, Gideon Stupp |
| 2004 | Broadcast in radio networks tolerating byzantine adversarial behavior. | Chiu-Yuen Koo |
| 2004 | Choosing a random peer. | Valerie King, Jared Saia |
| 2004 | Group membership: a novel approach and the first single-round algorithm. | Roger I. Khazan |
| 2004 | Brief announcement: Trilix: a scalable unstructured lookup system for dynamic environments. | Idit Keidar, Roie Melamed |
| 2004 | Brief announcement: randomized rumor spreading with fewer phone calls. | Kirsten Hildrum, Sean Ma, Satish Rao |
| 2004 | Brief announcement: stretch between nearby peers. | Kirsten Hildrum, John Kubiatowicz, Jeremy Stribling |
| 2004 | Brief announcement: self-stabilizing distance-d distinct labels via enriched fair composition. | Lisa Higham, Lixiao Wang |
| 2004 | On spectrum sharing games. | Magns M. Halldrsson, Joseph Y. Halpern, Li (Erran) Li, Vahab S. Mirrokni |
| 2004 | On the design of distributed protocols from differential equations. | Indranil Gupta |
| 2004 | Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. | Paul W. Goldberg |
| 2004 | Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs. | Jie Gao, Li Zhang |
| 2004 | Brief announcement: veto number and the respective power of eventual failure detectors. | Roy Friedman, Achour Mostfaoui, Michel Raynal |