SPAA 2004 Call for Participation

[Michael Bender]

Call for Participation

==========================================================================

Sixteenth ACM Symposium on Parallelism in Algorithms and Architectures
SPAA '04
June 27-30, 2004
Barcelona, Spain

==========================================================================

This symposium was called the ACM Symposium on Parallel Algorithms and
Architectures from 1989 to 2002. The new name to reflects the expanded
scope of the conference as detailed below.

This year, in a tradition starting in 2001, SPAA defines "parallel" very
broadly to encompass any computational "device" that can perform multiple
operations or tasks simultaneously. As a consequence, SPAA 2004 covers all
aspects of parallelism. This includes traditional parallel and distributed
algorithms and architectures, plus new aspects including the internet, the
web, sensor networks, quantum and DNA computing, etc. For more
information, see the call for papers.

==========================================================================

Venue

The conference will be held at the Technical University of Catalonia.
See http://www.spaa-conference.org/ for more information.

==========================================================================

Registration

The deadline for early registration is June 7, 2004.
See http://www.spaa-conference.org/ for registration information.

==========================================================================

Technical Program

          June 27, 2004, Sunday

6pm - TBD   Registration
7pm - TBD   Reception at Catedra Gaudi (Campus Nord - UPC)


          June 28, 2004, Monday

TBD                 Continental Breakfast
9:00am - 9:10am     Welcome
9:10am - 10:25am    Session 1: Routing I
9:10am - 9:35am     On Delivery Times in Packet Networks under Adversarial Traffic
                    Adi Rosen and Michael S. Tsirkin
9:35am - 10:00am    Adaptive Channel Queue Routing on k-ary n-cubes
                    Arjun Singh, William J. Dally, Amit Gupta, and Brian Towles
10:00am - 10:25am   Compact Name-Independent Routing with Minimum Stretch
                    Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel Thorup
10:25am - 10:50am   Break
10:50am - 12:30pm   Session 2: Peer-To-Peer Systems
10:50am - 11:15am   Object Location in Realistic Networks
                    Kirsten Hildrum, Robert Krauthgamer, and John Kubiatowicz
11:15am - 11:40am   Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems
                    David R. Karger and Matthias Ruhl
11:40am - 12:05am   Consistent, Order-Preserving Data Management in Distributed Storage Systems
                    Baruch Awerbuch and Christian Scheideler
12:05am - 12:30pm   Geometric Generalizations of the Power of Two Choices
                    John W. Byers, Jeffrey Considine, and Michael Mitzenmacher
12:30pm - 2:30pm    Lunch
2:30pm - 3:45pm     Session 3: Caching I
2:30pm - 2:55pm     Fighting Against Two Adversaries: Page Migration in Dynamic Networks
                    Marcin Bienkowski, Miroslaw Korzeniowski, and Friedhelm Meyer auf der Heide
2:55pm - 3:20pm     Online Hierarchical Cooperative Caching
                    Xiaozhou Li, C. Greg Plaxton, Mitul Tiwari, and Arun Venkataramani
3:20pm - 3:45pm     New Results on Web Caching with Request Reordering
                    Susanne Albers
3:45pm - 4:15pm     Break
4:15pm - 5:30pm     Session 4: Routing II
4:15pm - 4:40pm     Packet-Mode Policies for Input-Queued Switches
                    Dan Guez, Alex Kesselman, and Adi Rosen
4:40pm - 5:05pm     Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines
                    Fan Chung, Ronald Graham, and George Varghese
5:05pm - 5:30pm     Lower Bounds for Approximating Sparse Graphs and M-Matrices
                    Gary L. Miller and Peter C. Richter
Evening, time TBD   Business Meeting


          June 29, 2004, Tuesday

TBD                 Continental Breakfast
9:10am - 10:50am    Session 5: Algorithms
9:10am - 9:35am     Balanced Graph Partitioning
                    Konstantin Andreev and Harald Raecke
9:35am - 10:00am    Bi-criteria Algorithm for Scheduling Jobs on Cluster Platforms
                    Pierre-Francois Dutot, Lionel Eyraud, Gregory Mounie, and Denis Trystram
10:00am - 10:25am   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
10:25am - 10:50am   An NC Algorithm for Finding a Maximal Acyclic Set in a Graph
                    Aaron Windsor
10:50am - 11:15am   Break
11:15am - 12:30pm   Session 6: Networks I
11:15am - 11:40am   Scheduling Against an Adversarial Network
                    Stefano Leonardi, Alberto Marchetti-Spaccamela, and Friedhelm Meyer auf der Heide
11:40am - 12:05am   On Achieving Optimized Capacity Utilization in Application Overlay Networks with
                    Multiple Competing Sessions
                    Yi Cui, Baochun Li, and Klara Nahrstedt
12:05am - 12:30am   Pagoda: A Dynamic Overlay Network for Routing, Data Management, and Multicasting
                    Ankur Bhargava, Kishore Kothapalli, Chris Riley, Christian Scheideler, and Mark Thober
12:30pm - 2:30pm    Lunch
2:30pm - 3:45pm     Session 7: Algorithmic Game Theory
2:30pm - 2:55pm     Sharing the Cost of Multicast Transmissions in Wireless Network
                    V. Bilo, C. Di Francescomarino, M. Flammini, and G. Melideo
2:55pm - 3:20pm     Selfish Load Balancing and Atomic Congestion Games
                    Subhash Suri, Csaba D. Toth, and Yunhong Zhou
3:20pm - 3:45pm     How to Route and Tax Selfish Unsplittable Traffic
                    Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Pino Persiano
Evening             Outing and Dinner


          June 30, 2004, Wednesday

TBD                 Continental Breakfast
9:00am - 10:15am    Session 8: Shared Memory and Architecture
9:00am - 9:25am     A Scalable Lock-free Stack Algorithm
                    Danny Hendler, Nir Shavit, and Lena Yerushalmi
9:25am - 9:50am     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.
9:50am - 10:15am    Efficient Orchtestration of Sub-Word Parallelism in Media Processors
                    John Oliver, Venkatesh Akella, and Frederic T. Chong
10:15am - 10:30am   Break
10:30am - 11:45pm   Session 9: Caching II
10:30am - 10:55am   Effectively Sharing a Cache Among Threads
                    Guy E. Blelloch and Phillip B. Gibbons
10:55am - 11:20am   Cache-Oblivious Shortest Paths in Graphs Using Buffer Heap
                    Rezaul Alam Chowdhury and Vijaya Ramachandran
11:20am - 11:45am   Online Algorithms for Prefetching and Caching on Parallel Disks
                    Rahul Shah, Peter Varman, and Jeffrey Scott Vitter
11:45am - 12:00am   Break
12:00pm - 12:50pm   SPAA Revue
12:00pm - 12:10pm   Improved Combination of Online Algorithms for Acceptance and Rejection
                    David P. Bunde and Yishay Mansour
12:10pm - 12:20pm   Time Complexity of Practical Parallel Steiner Point Insertion Algorithms
                    Dan A. Spielman, Shang-hua Teng, and Alper Ungor
12:20pm - 12:30pm   The Inherent Queuing Delay of Parallel Packet Switches
                    Hagit Attiya and David Hay
12:30pm - 12:40pm   Efficient Search in Unstructured Peer-to-Peer Networks
                    Vicent Cholvi, Pascal Felber, and Ernst Biersack
12:40pm - 12:50pm   The Potential in Energy Efficiency of a Speculative Chip-Multiprocessor
                    Yuu Tanaka and Toshinori Sato and Takenori Koushiro
12:50pm - 2:45pm    Lunch
2:45pm - 4:00pm     Session 10: Networks II
2:45pm - 3:10pm     Online Algorithms for Network Design
                    Adam Meyerson
3:10pm - 3:35pm     Expansion Properties of (Secure) Wireless Networks
                    Alessandro Panconesi and Jaikumar Radhakrishnan
3:35pm - 4:00pm     The Effect of Random Faults on Network Expansion
                    Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein,
                    and Christian Scheideler
4:00pm - 4:15pm     Break
4:15pm - 5:30pm     Session 11: Distributed Computation
4:15pm - 4:40pm     Dynamic Analysis of the Arrow Distributed Protocol
                    Fabian Kuhn and Roger Wattenhofer
4:40pm - 5:05pm     Optimal Early Stopping Uniform Consensus in Synchronous Systems
                    with Process Omission Failures
                    Philippe Raipin Parvedy and Michel Raynal
5:05pm - 5:30pm     Writing-All Deterministically and Optimally Using a Non-Trivial
                    Number of Asynchronous Processors
                    Dariusz Kowalski and Alex Shvartsman
5:30pm  END

==========================================================================

Program Chair
    Micah Adler, U. Massachusetts

Program Committee
    Micah Adler, U. Massachusetts
    John Byers, Boston U.
    Tom Cormen, Dartmouth College
    Bruce Hendrickson, Sandia National Laboratories
    Maurice Herlihy, Brown U.
    Christos Kaklamanis, U. Patras
    Christian Lengauer, U. Passau
    Geppino Pucci, U. Padova
    Satish Rao, U.C. Berkeley
    Yves Robert, ENS Lyon
    Peter Sanders, MPI Saarbrucken
    Daniel Sorin, Duke U.
    Aravind Srinivasan, U. Maryland
    Berthold Vocking, U. Dortmund

SPAA Local Arrangements Chair
    Eulalia Barriere, Technical U. of Catalonia

SPAA General Chair
    Phil Gibbons, Intel Research

SPAA Secretary
    Cynthia A. Phillips, Sandia National Laboratories

SPAA Treasurer
    Rajmohan Rajaraman, Northeastern U.

Publicity Chair
    Michael Bender, SUNY Stony Brook

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.