List of accepted papers for SPAA 2004: On Delivery Times in Packet Networks under Adversarial Traffic Adi Rosen and Michael S. Tsirkin Adaptive Channel Queue Routing on k-ary n-cubes Arjun Singh, William J. Dally, Amit Gupta, and Brian Towles Compact Name-Independent Routing with Minimum Stretch Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel Thorup Object location in realistic networks Kirsten Hildrum, Robert Krauthgamer, and John Kubiatowicz Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems David R. Karger and Matthias Ruhl Consistent, Order-Preserving Data Management in Distributed Storage Systems Baruch Awerbuch and Christian Scheideler Geometric Generalizations of the Power of Two Choices John W. Byers, Jeffrey Considine, and Michael Mitzenmacher Fighting Against Two Adversaries: Page Migration in Dynamic Networks Marcin Bienkowski, Miroslaw Korzeniowski, and Friedhelm Meyer auf der Heide Online Hierarchical Cooperative Caching Xiaozhou Li, C. Greg Plaxton, Mitul Tiwari, and Arun Venkataramani New Results on Web Caching with Request Reordering Susanne Albers Packet-Mode Policies for Input-Queued Switches Dan Guez, AlexKesselman, and Adi Rosen Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines Fan Chung, Ronald Graham, and George Varghese Lower Bounds for Approximating Sparse Graphs and M-Matrices Gary L. Miller and Peter C. Richter Balanced Graph Partitioning Konstantin Andreev and Harald Raecke Bi-criteria Algorithm for Scheduling Jobs on Cluster Platforms Pierre-Francois Dutot, Lionel Eyraud, Gregory Mounie, and Denis Trystram On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Charles E. Leiserson An NC Algorithm for Finding a Maximal Acyclic Set in a Graph Aaron Windsor Scheduling Against an Adversarial Network Stefano Leonardi, Alberto Marchetti-Spaccamela, and Friedhelm Meyer auf der Heide On Achieving Optimized Capacity Utilization in Application Overlay Networks with Multiple Competing Sessions Yi Cui, Baochun Li, and Klara Nahrstedt Pagoda: A Dynamic Overlay Network for Routing, Data Management, and Multicasting Ankur Bhargava, Kishore Kothapalli, Chris Riley, Christian Scheideler, and Mark Thober Sharing the Cost of Multicast Transmissions in Wireless Network V. Bilo, C. Di Francescomarino, M. Flammini, and G. Melideo Selfish Load Balancing and Atomic Congestion Games Subhash Suri, Csaba D. Toth, and Yunhong Zhou How to Route and Tax Selfish Unsplittable Traffic Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Pino Persiano A Scalable Lock-free Stack Algorithm Danny Hendler, Nir Shavit, and Lena Yerushalmi DCAS is not a Silver Bullet for Nonblocking Algorithm Design Simon Doherty, David L. Detlefs, Lindsay Groves, Christine H. Flood, Victor Luchangco, Paul A. Martin, Mark Moir, Nir Shavit, and Guy L. Steele, Jr. Efficient Orchtestration of Sub-Word Parallelism in Media Processors John Oliver, Venkatesh Akella, and Frederic T. Chong Effectively Sharing a Cache Among Threads Guy E. Blelloch and Phillip B. Gibbons Cache-Oblivious Shortest Paths in Graphs Using Buffer Heap Rezaul Alam Chowdhury and Vijaya Ramachandran Online Algorithms for Prefetching and Caching on Parallel Disks Rahul Shah, Peter Varman, and Jeffrey Scott Vitter Improved Combination of Online Algorithms for Acceptance and Rejection David P. Bunde and Yishay Mansour Time Complexity of Practical Parallel Steiner Point Insertion Algorithms Dan A. Spielman, Shang-hua Teng, and Alper Ungor The Inherent Queuing Delay of Parallel Packet Switches Hagit Attiya and David Hay Efficient Search in Unstructured Peer-to-Peer Networks Vicent Cholvi, Pascal Felber, and Ernst Biersack The Potential in Energy Efficiency of a Speculative Chip-Multiprocessor Yuu Tanaka and Toshinori Sato and Takenori Koushiro Online Algorithms for Network Design Adam Meyerson Expansion Properties of (Secure) Wireless Networks Alessandro Panconesi and Jaikumar Radhakrishnan The Effect of Random Faults on Network Expansion Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein, and Christian Scheideler Dynamic Analysis of the Arrow Distributed Protocol Fabian Kuhn and Roger Wattenhofer Optimal Early Stopping Uniform Consensus in Synchronous Systems with Process Omission Failures Philippe Raipin Parvedy and Michel Raynal Writing-All Deterministically and Optimally Using a Non-Trivial Number of Asynchronous Processors Dariusz Kowalski and Alex Shvartsman