| 2004 | A Local Algorithm for Ad Hoc Majority Voting via Charge Fusion. Yitzhak Birk, Liran Liss, Assaf Schuster, Ran Wolff |
| 2004 | A Single-Enqueuer Wait-Free Queue Implementation. Matei David |
| 2004 | Active and Concurrent Topology Maintenance. Xiaozhou Li, Jayadev Misra, C. Greg Plaxton |
| 2004 | An Optimistic Approach to Lock-Free FIFO Queues. Edya Ladan-Mozes, Nir Shavit |
| 2004 | Bounded Version Vectors. José Bacelar Almeida, Paulo Sérgio Almeida, Carlos Baquero |
| 2004 | Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs. Yon Dourisboure |
| 2004 | Contention-Free MAC Protocols for Wireless Sensor Networks. Costas Busch, Malik Magdon-Ismail, Fikret Sivrikaya, Bülent Yener |
| 2004 | Coupling and Self-stabilization.. Laurent Fribourg, Stéphane Messika, Claudine Picaronny |
| 2004 | Distributed Computing, 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4-7, 2004, Proceedings Rachid Guerraoui |
| 2004 | Distributed Weighted Matching. Mirjam Wattenhofer, Roger Wattenhofer |
| 2004 | Dynamic Memory ABP Work-Stealing. Danny Hendler, Yossi Lev, Nir Shavit |
| 2004 | Efficient Adaptive Collect Using Randomization. Hagit Attiya, Fabian Kuhn, Mirjam Wattenhofer, Roger Wattenhofer |
| 2004 | Efficient Verification for Provably Secure Storage and Secret Sharing in Systems Where Half the Servers Are Faulty. Rida A. Bazzi, Goran Konjevod |
| 2004 | Exploiting Content Localities for Efficient Search in P2P Systems. Lei Guo, Song Jiang, Li Xiao, Xiaodong Zhang |
| 2004 | Fault-Tolerant Storage in a Dynamic Environment. Uri Nadav, Moni Naor |
| 2004 | Group-Solvability. Eli Gafni |
| 2004 | Local-Spin Group Mutual Exclusion Algorithms. Robert Danek, Vassos Hadzilacos |
| 2004 | Message-Optimal and Latency-Optimal Termination Detection Algorithms for Arbitrary Topologies. Neeraj Mittal, Subbarayan Venkatesan, Sathya Peri |
| 2004 | Non-skipping Timestamps for Byzantine Data Storage Systems. Rida A. Bazzi, Yin Ding |
| 2004 | Nonblocking Concurrent Data Structures with Condition Synchronization. William N. Scherer III, Michael L. Scott |
| 2004 | On Byzantine Agreement over (2, 3)-Uniform Hypergraphs. D. V. S. Ravikant, Muthuramakrishnan Venkitasubramaniam, V. Srikanth, K. Srinathan, C. Pandu Rangan |
| 2004 | On Quorum Systems for Group Resources with Bounded Capacity. Yuh-Jzer Joung |
| 2004 | Optimal Dispersal of Certificate Chains. Eunjin Jung, Ehab S. Elmallah, Mohamed G. Gouda |
| 2004 | Optimal Randomized Self-stabilizing Mutual Exclusion on Synchronous Rings. Philippe Duchon, Nicolas Hanusse, Sébastien Tixeuil |
| 2004 | Practical Lock-Free and Wait-Free LL/SC/VL Implementations Using 64-Bit CAS. Maged M. Michael |
| 2004 | Relationships Between Broadcast and Shared Memory in Reliable Anonymous Distributed Systems. James Aspnes, Faith E. Fich, Eric Ruppert |
| 2004 | Routing with Improved Communication-Space Trade-Off. Ittai Abraham, Cyril Gavoille, Dahlia Malkhi |
| 2004 | Synchronous Condition-Based Consensus Adapting to Input-Vector Legality. Taisuke Izumi, Toshimitsu Masuzawa |
| 2004 | The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms. Gadi Taubenfeld |
| 2004 | The Notion of Veto Number and the Respective Power of OP and OS to Solve One-Shot Agreement Problems. Roy Friedman, Achour Mostéfaoui, Michel Raynal |
| 2004 | The Synchronous Condition-Based Consensus Hierarchy. Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal |
| 2004 | Towards a Theory of Consistency Primitives. Ueli M. Maurer |
| 2004 | Virtual Mobile Nodes for Mobile Ad Hoc Networks. Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alexander A. Shvartsman, Jennifer L. Welch |