| 2004 | Brief announcement: an incremental algorithm for calculation of backup-paths in link-state networks. | Pierre Fransson, Lenka Carr-Motyckov |
| 2004 | Eclecticism shrinks even small worlds. | Pierre Fraigniaud, Cyril Gavoille, Christophe Paul |
| 2004 | Lock-free linked lists and skip lists. | Mikhail Fomitchev, Eric Ruppert |
| 2004 | On the inherent weakness of conditional synchronization primitives. | Faith E. Fich, Danny Hendler, Nir Shavit |
| 2004 | Brief announcement: on the possibility of consensus in asynchronous systems with finite average response times. | Christof Fetzer, Ulrich Schmid |
| 2004 | Mechanism design for policy routing. | Joan Feigenbaum, Rahul Sami, Scott Shenker |
| 2004 | Gradient clock synchronization. | Rui Fan, Nancy A. Lynch |
| 2004 | Efficient algorithms for constructing (1+, varepsilon;, beta)-spanners in the distributed and streaming models. | Michael Elkin, Jian Zhang |
| 2004 | How fast can a distributed atomic read be? | Partha Dutta, Rachid Guerraoui, Ron R. Levy, Arindam Chakraborty |
| 2004 | Brief announcement: polygonal broadcast, secret maturity and the firing sensors. | Shlomi Dolev, Ted Herman, Limor Lahiani |
| 2004 | Brief announcement: virtual mobile nodes for mobile ad hoc networks. | Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alexander A. Shvartsman, Jennifer L. Welch |
| 2004 | Bringing practical lock-free synchronization to 64-bit applications. | Simon Doherty, Maurice Herlihy, Victor Luchangco, Mark Moir |
| 2004 | Brief announcement: STALK: a self-stabilizing hierarchical tracking service for sensor networks. | Murat Demirbas, Anish Arora, Tina Nolte, Nancy A. Lynch |
| 2004 | The weakest failure detectors to solve certain fundamental problems in distributed computing. | Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Vassos Hadzilacos, Petr Kouznetsov, Sam Toueg |
| 2004 | Brief announcement: a single enqueuer wait-free queue implementation. | Matei David |
| 2004 | Brief announcement: linear time byzantine self-stabilizing clock synchronization. | Ariel Daliot, Danny Dolev, Hanna Parnas |
| 2004 | On the expected payment of mechanisms for task allocation. | Artur Czumaj, Amir Ronen |
| 2004 | Brief announcement: degree: optimal deterministic routing for P2P systems. | Gennaro Cordasco, Luisa Gargano, Mikael Hammar, Vittorio Scarano |
| 2004 | Selfish caching in distributed systems: a game-theoretic analysis. | Byung-Gon Chun, Kamalika Chaudhuri, Hoeteck Wee, Marco Barreno, Christos H. Papadimitriou, John Kubiatowicz |
| 2004 | A better wake-up in radio networks. | Bogdan S. Chlebus, Dariusz R. Kowalski |
| 2004 | Brief announcement: secret handshakes from CA-oblivious encryption. | Claude Castelluccia, Stanislaw Jarecki, Gene Tsudik |
| 2004 | Efficient top-K query calculation in distributed networks. | Pei Cao, Zhe Wang |
| 2004 | Asynchronous group key exchange with failures. | Christian Cachin, Reto Strobl |
| 2004 | Efficient synchronous snapshots. | Alex Brodsky, Faith Ellen Fich |
| 2004 | Brief announcement: the design of an internet-scale monitoring and assertion-checking infrastructure. | Monica Brockmeyer, Chunbo Chu |