TABLE OF CONTENTS OF THE SPAA'96

• Towards Efficiency and Portability: Programming with the BSP Model
  
  Mark Goudreau, U. Central Florida
  Kevin Lang, Satish Rao, Torsten Suel, NEC
  Thanasis Tsantilas Columbia U.
  
  
• A Quantitative Comparison of Parallel Computation Models
  
  Harry A.G. Wijshoff, B.H.H. Juurlink, Leiden U.
  
  
• BSP vs LogP
  
  Gianfranco Bilarcli, U. Padova and U. Illinois, Chicago
  Kieran T. Herley, U. College Cork
  Andrea Pietracaprina, U. Padova
  Geppino Pucci, U. Padova
  Paul Spirakis, Computer Technology Institute, Patras
  
  
• A Steady State Analysis of Diffracting Trees
  
  Nir Shavit, Tel-Aviv U. and MIT
  Eli Upfal, IBM Almaden and Weizmann Institute
  Asaph Zemach, Tel-Aviv U.
  
  
• Asynchronous Shared Memory Search Structures
  
  Micah Acller, UC Berkeley and ICSI
  
  
• Improved Methods for Hiding Latency in High Bandwith Networks
  
  Matthew Andrews, MIT
  Tom Leighton, MIT
  P. Takis Metaxas, Wellesley College
  Lisa Zhang, MIT
  
  
• Optimal Latency-Throughput Tradeoffs for Data Parallel Pipelines
  
  Jaspal Subhlok, CMU
  Gary Vondran, HP Labs
  
  
• First and Second Order Diffusive Methods for Rapid, Coarse, Distributed Load Balancing
  
  Bhaskar Ghosh, Informix
  S. Muthukrishnan, U. Warwick
  Martin H. Schultz, Yale
  
  
• On Multiprocessor System Scheduling
  
  Xiaotie Deng, Patrick Dymond, York U.
  
  
• An Analysis of Gang Scheduling for Multiprogrammed Parallel Computing Environments
  
  Mark Squillante, IBM T.J. Watson
  Fang Wang, Yale
  Marios Papaefthymiou, Yale
  
  
• Flexible Usage of Parity Storage Space in Disk Arrays
  
  Eric J. Schwabe, Ian M. Sutherland, Northwestern
  
  
• Simple Randomized Mergesort on Parallel Disks
  
  Rakesh D. Barve, Duke
  Edward F. Grove, Max-Planck-Institut, Saarbrucken
  Jeffrey Scott Vitter, Duke
  
  
• Anticipatory Instruction Scheduling
  
  Vivek Sarkar, Barbara Simons, IBM Software Solutions Division
  
  
• On the Benefit of Supporting Virtual Channels in Wormhole Routers
  
  Richard J. Cole, Courant Institute, NYU
  Bruce M. Maggs, CMU
  Ramesh K. Sitaraman, U. Massachusetts, Amherst
  
  
• Universal Continuous Routing Strategies
  
  Christian Scheideler, Berthold Vöcking, Heinz Nixdorf Institut Paderborn
  
  
• On the Communication Throughput of Buffered Multistage Interconnection Networks
  
  Ralf Rehrmann, Burkhard Monien, Reinhard Lüling, Ralf Diekmann, U. Paderborn
  
  
• Constant Time per Edge is Optimal on Rooted Tree Networks
  
  Michael Mitzenmacher, UC Berkeley
  
  
• A Tight Layout of the Butterfly Network
  
  Aythan Avior, Technion
  Tiziana Calamoneri, U. Rome "La Sapienza"
  Shimon Even, Technion
  Ami Litman, Technion
  Arnold L. Rosenberg, U. Massachussetts, Amherst
  
  
• On the Slowdown of Efficient Simulations of Multibutterflies on Butterflies and Butterfly-Derived Networks
  
  Kevin J. Rappoport, Pacific-Sierra Research
  
  
• Local Memory Requirement of Universal Routing Schemes
  
  P. Fraigniaud, C. Gavoille, LIP ENS Lyon
  
  
• A Dynamic Load Balancing Framework for Unstructured Adaptive Computations on Distributed-Memory Multiprocessors
  
  Andrew Sohn, NJIT
  Rupak Biswas, RIACS
  Horst D. Simon, Lawrence Berkeley Labs.
  
  
• A Library of Basic PRAM Algorithms and its Implementation in FORK
  
  Christoph W. Keller, U. Trier
  Jesper Larsson Träff, Max-Planck Institut fuer Informatik
  
  
• myDatabase: Parallelism in a Memory-Mapped Environment
  
  Peter Buhr, Anil Goel, Naomi Nishimura, Prabhakar Ragde, U. Waterloo
  
  
• From AAPC Algorithms to High Performance Permutation Routing and Sorting
  
  Thomas M. Stricker, Jonathan C. Harclwick, CMU
  
  
• Parallel Neighborhood Modeling
  
  D. Hutchinson, L. Küttner, M. Lanthier, A. Maheshwari, D. Nussbaum,
  D. Roytenberg, J. R. Sack, Carleton U.
  
  
• Components of Congestion Control
  
  Ludmila Cherkasova, HP Labs
  Al Davis, U. Utah
  Robin Hodgson, Vadim Kotov, Ian Robinson, Tomas Rokicki, HP Labs
  
  
• Parallel Algorithms for Personalized Communication and Sorting with an Experimental Study
  
  David R. Helman, David A. Bader, Joseph JaJa,, U. Maryland, College Park
  
  
• Deterministic Sorting and Randomized Median Finding on the BSP Model
  
  Alexandros V. Gerbessiotis, Constantinos J. Siniolakis, Oxford
  
  
• Fully Dynamic Search Trees for an Extension of the BSP Model
  
  Armin Bäumker, Wolfgang Dittrich, U. Paderborn
  
  
• Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling
  
  Richard Cole., Courant Institute, NYU
  Philip N. Klein, Brown
  Robert E. Tarjan, Princeton
  
  
• Parallel Multidimensional Search Using Approximation Algorithms: With Applications to Linear-Programming and Related Problems.
  
  Sandeep Sen, IIT New Delhi
  
  
• Parallel Balanced Allocations
  
  Volker Stemann, ICSI
  
  
• Efficient Execution of Nondeterministic Parallel Programs on Asynchronous Systems
  
  Yonatan Aumann, Bar-Ilan U.
  Michael A. Bender, Harvard,
  Y. Lisa Zhang, MIT
  
  
• Scope Consistency: A Bridge Between Release Consistency and Entry Consistency
  
  Liviu Iftode, Jaswinder Pal Singh, Kai Li, Princeton
  
  
• Verification of FLASH Cache Coherence Protocol by Aggregation of Distributed
  Transactions
  
  Seungjoon Park, David L. Dill, Stanford
  
  
• An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms
  
  Robert D. Blumofe, U. Texas, Austin
  Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall, MIT
  
  
• On Trading Task Reallocation for Thread Management in Partitionable
  Multiprocessors
  
  Lixin Gao, Arnold L. Rosenberg, Ramesh K. Sitaraman, U. Massachusetts, Amherst
  
  
• Load-Sharing via Weighted Factoring
  
  Susan Flynn Hummel, Polytechnic U. and IBM T.L Watson
  Jeanette Schmidt, R.N. Uma, Joel Wein, Polytechnic U.
  
  
• Resource Scheduling for Parallel Database and Scientific Applications
  
  Soumen Chakrabarti, UC Berkeley
  S. Muthukrishnan, U. Warwick