16. SPAA 2004: Barcelona, Catalonia, Spain

Phillip B. Gibbons, Micah Adler (Eds.): SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallel Algorithms, June 27-30, 2004, Barcelona, Spain. ACM 2004, ISBN 1-58113-840-7 BibTeX

Routing 1

Adi Rosén, Michael S. Tsirkin:
On delivery times in packet networks under adversarial traffic. 1-10
Electronic Edition (ACM DL) BibTeX
Arjun Singh, William J. Dally, Amit K. Gupta, Brian Towles:
Adaptive channel queue routing on k-ary n-cubes. 11-19
Electronic Edition (ACM DL) BibTeX
Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, Mikkel Thorup:
Compact name-independent routing with minimum stretch. 20-24
Electronic Edition (ACM DL) BibTeX

Peer-To-peer systems

Kirsten Hildrum, Robert Krauthgamer, John Kubiatowicz:
Object location in realistic networks. 25-35
Electronic Edition (ACM DL) BibTeX
David R. Karger, Matthias Ruhl:
Simple efficient load balancing algorithms for peer-to-peer systems. 36-43
Electronic Edition (ACM DL) BibTeX
Baruch Awerbuch, Christian Scheideler:
Consistent and compact data management in distributed storage systems. 44-53
Electronic Edition (ACM DL) BibTeX
John W. Byers, Jeffrey Considine, Michael Mitzenmacher:
Geometric generalizations of the power of two choices. 54-63
Electronic Edition (ACM DL) BibTeX

Caching I

Marcin Bienkowski, Miroslaw Korzeniowski, Friedhelm Meyer auf der Heide:
Fighting against two adversaries: page migration in dynamic networks. 64-73
Electronic Edition (ACM DL) BibTeX
Xiaozhou Li, C. Greg Plaxton, Mitul Tiwari, Arun Venkataramani:
Online hierarchical cooperative caching. 74-83
Electronic Edition (ACM DL) BibTeX
Susanne Albers:
New results on web caching with request reordering. 84-92
Electronic Edition (ACM DL) BibTeX

Routing II

Dan Guez, Alexander Kesselman, Adi Rosén:
Packet-mode policies for input-queued switches. 93-102
Electronic Edition (ACM DL) BibTeX
Fan R. K. Chung, Ronald L. Graham, George Varghese:
Parallelism versus memory allocation in pipelined router forwarding engines. 103-111
Electronic Edition (ACM DL) BibTeX
Gary L. Miller, Peter C. Richter:
Lower bounds for graph embeddings and combinatorial preconditioners. 112-119
Electronic Edition (ACM DL) BibTeX

Algorithms

Konstantin Andreev, Harald Räcke:
Balanced graph partitioning. 120-124
Electronic Edition (ACM DL) BibTeX
Pierre-François Dutot, Lionel Eyraud, Grégory Mounié, Denis Trystram:
Bi-criteria algorithm for scheduling jobs on cluster platforms. 125-132
Electronic Edition (ACM DL) BibTeX
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Charles E. Leiserson:
On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs. 133-144
Electronic Edition (ACM DL) BibTeX
Aaron Windsor:
An NC algorithm for finding a maximal acyclic set in a graph. 145-150
Electronic Edition (ACM DL) BibTeX

Networks I

Stefano Leonardi, Alberto Marchetti-Spaccamela, Friedhelm Meyer auf der Heide:
Scheduling against an adversarial network. 151-159
Electronic Edition (ACM DL) BibTeX
Yi Cui, Baochun Li, Klara Nahrstedt:
On achieving optimized capacity utilization in application overlay networks with multiple competing sessions. 160-169
Electronic Edition (ACM DL) BibTeX
Ankur Bhargava, Kishore Kothapalli, Chris Riley, Christian Scheideler, Mark Thober:
Pagoda: a dynamic overlay network for routing, data management, and multicasting. 170-179
Electronic Edition (ACM DL) BibTeX

Algorithmic game theory

Vittorio Bilò, Chiara Di Francescomarino, Michele Flammini, Giovanna Melideo:
Sharing the cost of multicast transmissions in wireless networks. 180-187
Electronic Edition (ACM DL) BibTeX
Subhash Suri, Csaba D. Tóth, Yunhong Zhou:
Selfish load balancing and atomic congestion games. 188-195
Electronic Edition (ACM DL) BibTeX
Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Pino Persiano:
How to route and tax selfish unsplittable traffic. 196-205
Electronic Edition (ACM DL) BibTeX

Shared memory and architecture

Danny Hendler, Nir Shavit, Lena Yerushalmi:
A scalable lock-free stack algorithm. 206-215
Electronic Edition (ACM DL) BibTeX
Simon Doherty, David Detlefs, Lindsay Groves, Christine H. Flood, Victor Luchangco, Paul A. Martin, Mark Moir, Nir Shavit, Guy L. Steele Jr.:
DCAS is not a silver bullet for nonblocking algorithm design. 216-224
Electronic Edition (ACM DL) BibTeX
John Oliver, Venkatesh Akella, Frederic T. Chong:
Efficient orchestration of sub-word parallelism in media processors. 225-234
Electronic Edition (ACM DL) BibTeX

Caching II

Guy E. Blelloch, Phillip B. Gibbons:
Effectively sharing a cache among threads. 235-244
Electronic Edition (ACM DL) BibTeX
Rezaul Alam Chowdhury, Vijaya Ramachandran:
Cache-oblivious shortest paths in graphs using buffer heap. 245-254
Electronic Edition (ACM DL) BibTeX
Rahul Shah, Peter J. Varman, Jeffrey Scott Vitter:
Online algorithms for prefetching and caching on parallel disks. 255-264
Electronic Edition (ACM DL) BibTeX

SPAA revue

David P. Bunde, Yishay Mansour:
Improved combination of online algorithms for acceptance and rejection. 265-266
Electronic Edition (ACM DL) BibTeX
Daniel A. Spielman, Shang-Hua Teng, Alper Üngör:
Time complexity of practical parallel steiner point insertion algorithms. 267-268
Electronic Edition (ACM DL) BibTeX
Hagit Attiya, David Hay:
The inherent queuing delay of parallel packet switches. 269-270
Electronic Edition (ACM DL) BibTeX
Vicent Cholvi, Pascal Felber, Ernst W. Biersack:
Efficient search in unstructured peer-to-peer networks. 271-272
Electronic Edition (ACM DL) BibTeX
Yuu Tanaka, Toshinori Sato, Takenori Koushiro:
The potential in energy efficiency of a speculative chip-multiprocessor. 273-274
Electronic Edition (ACM DL) BibTeX

Networks II

Adam Meyerson:
Online algorithms for network design. 275-280
Electronic Edition (ACM DL) BibTeX
Alessandro Panconesi, Jaikumar Radhakrishnan:
Expansion properties of (secure) wireless networks. 281-285
Electronic Edition (ACM DL) BibTeX
Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein, Christian Scheideler:
The effect of faults on network expansion. 286-293
Electronic Edition (ACM DL) BibTeX

Distributed computation

Fabian Kuhn, Roger Wattenhofer:
Dynamic analysis of the arrow distributed protocol. 294-301
Electronic Edition (ACM DL) BibTeX
Philippe Raipin Parvédy, Michel Raynal:
Optimal early stopping uniform consensus in synchronous systems with process omission failures. 302-310
Electronic Edition (ACM DL) BibTeX
Dariusz R. Kowalski, Alexander A. Shvartsman:
Writing-all deterministically and optimally using a non-trivial number of asynchronous processors. 311-320
Electronic Edition (ACM DL) BibTeX