June 27-28, 1998, Saturday-Sunday

The conferences will be preceded by a "Mini-School on Parallel and Distributed Computing" organized by the Student Chapter of the Mexican Computer Science Society. Click here for more information.

June 28, 1998, Sunday

15:00 - 17:00 Tutorial 1
Algorithmic Problems in Internet Research
George Varghese, Washington University
17:30 - 19:30 Tutorial 2
High Performance Clusters: State of the Art and Challenges Ahead
David Culler, University of California, Berkeley
20:00 - 22:00 Reception

June 29, 1998, Monday

9:30 - 10:45 Invited Talk
How to Find It: Research Issues in Distributed Search
Udi Manber, University of Arizona
10:45 - 11:05 Break
11:05 - 12:20 Session L1

PODC: (Algorithmic Issues in Network Protocols)

Compact Routing Schemes With Low Stretch Factor
Tamar Eilam, Cyril Gavoille and David Peleg

Reconsidering Fragmentation and Reassembly
Girish P. Chandranmenon and George Varghese

Competitive Dynamic Bandwidth Allocation
Amotz Bar-Noy, Yishay Mansour and Baruch Schieber


Elimination Forest Guided 2D Sparse LU Factorization
Kai Shen, Xiangmin Jiao and Tao Yang

Fast Set Operations Using Treaps
Guy E. Blelloch and Margaret Reid-Miller

Communication-Optimal Parallel Minimum Spanning Tree Algorithms
Micah Adler, Wolfgang Dittrich, Ben Juurlink, Miroslaw Kutylowski and Ingo Rieping

12:20 - 14:15 Lunch
14:15 - 15:55 Session L2: SPAA exclusive

"Dynamic-Fault-Prone BSP": A Paradigm for Robust Computations in Changing Environments
Spyros C. Kontogiannis, Grammati E. Pantziou, Paul G. Spirakis and Moti Yung

An Adversarial Model for Distributed Dynamic Load Balancing
S. Muthukrishnan and Rajmohan Rajaraman

Deadlock-Free Routing in Arbitrary Networks via the Flattest Common Supersequence Method
Ambrose K. Laing and Robert Cypher

Lamport Clocks: Verifying A Directory Cache-Coherence Protocol
Manoj Plakal, Daniel J. Sorin, Anne E. Condon and Mark D. Hill

15:55 - 16:15 Break
16:15 - 17:55 Session L3: PODC exclusive
(Shared Memory Algorithms and Data Structures)

Asynchronous Group Mutual Exclusion (PODC version)
Yuh-Jzer Joung

Combining Funnels
Nir Shavit and Asaph Zemach

Synchronization Mechanisms for SCRAMNet+ Systems
Stephen Menke, Mark Moir and Srikanth Ramamurthy

20:30 - 22:00 SPAA Business meeting
20:30 - 24:00 PODC Business meeting and rump session

June 30, 1998, Tuesday

9:30 - 10:45 Invited Talk
Parallel/Distributed Computing Issues in Data Warehousing
Hector Garcia-Molina, Stanford
10:45 - 11:05 Break
11:05 - 12:45 Session L4

PODC: (Cryptographic Protocols)

Amortizing Randomness in Private Multiparty Computations
Eyal Kushilevitz, Rafail Ostrovsky and Adi Rosen

Universal Service-Providers for Database Private Information Retrieval (abstract)
Giovanni Di-Crescenzo, Yuval Ishai and Rafail Ostrovsky

Simplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptography
R. Gennaro, M. Rabin and T. Rabin

Optimal Efficiency of Optimistic Contract Signing
Birgit Pfitzmann, Matthias Schunter and Michael Waidner


Efficient Disk Allocation for Fast Similarity Searching
Sunil Prabhakar, Divyakant Agrawal and Amr El Abbadi

A Framework for Simple Sorting Algorithms on Parallel Disk Systems
Sanguthevar Rajasekaran

Blocking in Parallel Multisearch Problems
Wolfgang Dittrich, David Hutchinson and Anil Maheshwari

Automatic Parallel I/O Performance Optimization in Panda
Y. Chen, M. Winslett, Y. Cho and S. Kuo

12:45 - 14:30 Lunch
14:30 - 15:45 Session L5

PODC: (Unifying Different Distributed Models)

The Unified Structure of Consensus: a Layered Analysis Approach
Yoram Moses and Sergio Rajsbaum

Unifying Synchronous and Asynchronous Message-Passing Models
Maurice Herlihy, Sergio Rajsbaum and Mark Tuttle

Round-by-Round Fault Detectors: Unifying Synchrony and Asynchrony
Eli Gafni


Thread Scheduling for Multiprogrammed Multiprocessors
Nimar S. Arora, Robert D. Blumofe and C. Greg Plaxton

How "Hard" is Thread Partitioning and How "Bad" is a List Scheduling Based Partitioning Algorithm?
Xinan Tang and Guang R. Gao

Explicit Multi-Threading (XMT) Bridging Models for Instruction Parallelism
Uzi Vishkin, Shlomit Dascal, Efraim Berkovich and Joseph Nuzman

15:45 - 16:05 Break
16:05 - 16:55 Session BA1: PODC short talks

A Point to Point Connectivity Protocol (PODC version)
Paul LeMahieu and Jehoshua Bruck

An Error Control Scheme for Large-Scale Multicast Applications (Infocom '98 version)
Christos Papadopoulos, Guru Parulkar and George Varghese

The Global Efficiency of Distributed, Rate-Based, Flow Control Algorithms
Panagiota Fatourou, Marios Mavronicolas and Paul Spirakis

Scalable Best Matching Prefix Lookups (SIGCOMM '97 version, notes)
Marcel Waldvogel, George Varghese, Jon Turner and Bernhard Plattner

Optimal Allocation of Electronic Content in Networks
Israel Cidon, Shay Kutten and Ran Sofer

16:55 - 17:15 Break
17:15 - 17:45 Session BA2: PODC short talks

A Direct Lower Bound for k-Set Consensus (PODC version)
Hagit Attiya

Muteness Detectors for Consensus with Byzantine Processes
Assia Doudou and Andre Schiper

Implementing and Evaluating an Eventually-Serializable Data Service
O. Cheiner and A. Shvartsman

19:00 - 22:00 Banquet

July 1, 1998, Wednesday

9:30 - 10:45 Session L6


The Message Classification Model
Christof Fetzer

Reliable Message Delivery and Conditionally-Fast Transactions are not Possible without Accurate Clocks
Mark A. Smith

Synthesis of Fault-Tolerant Concurrent Programs
Anish Arora, Paul Attie and E. Allen Emerson


Computational Bounds for Fundamental Problems on General-Purpose Parallel Models
Philip D. MacKenzie and Vijaya Ramachandran

Broadcasting, Multicasting and Gossiping in Trees under the All-Port Line Model
Johanne Cohen

Layout Area of the Bitonic Sorting Network
Shimon Even, S. Muthukrishnan, Michael S. Paterson and Suleyman Cenk Sahinalp

10:45 - 11:05 Break
11:05 - 12:45 Session L7

PODC: (Lower Bounds)

A Lower Bound on the Local Time Complexity of Universal Constructions
Prasad Jayanti

A Tight Lower Bound for Randomized Synchronous Consensus
Ziv Bar-Joseph and Michael Ben-Or
Winner of best student paper award

A Time Complexity Lower Bound for Randomized Implementations of Some Shared Objects
Prasad Jayanti

Consensus Numbers of Multi-Objects
Eric Ruppert


Dynamic Scheduling with Incomplete Information
Hannah Bast

Parallel Continuous Randomized Load Balancing
Petra Berenbrink, Tom Friedetzky and Ernst W. Mayr

Recovery Time of Dynamic Allocation Processes
Artur Czumaj

Analyses of Load Stealing Models Based on Differential Equations
Michael Mitzenmacher

12:45 - 14:30 Lunch
14:30 - 15:45 Session L8


Persistent Messages in Local Transactions
David E. Lowell and Peter M. Chen

A Dynamic View-Oriented Group Communication Service
R. De Prisco, A. Fekete, N. Lynch and A. Shvartsman

An Adaptive Totally Ordered Multicast Protocol that Tolerates Partitions (gzipped)
Gregory V. Chockler, Nabil Huleihel and Danny Dolev


In-Memory Directories: Eliminating the Directory Overhead in CC-NUMAs
Christopher Ho, Heidi Ziegler and Michel Dubois

Using "Test Model-Checking" to Verify the Runway-PA8000 Memory Model
Rajnish Ghughal, Abdel Mokkedem, Ratan Nalumasu and Ganesh Gopalakrishnan

Computation-Centric Memory Models
Matteo Frigo and Victor Luchangco

15:45 - 16:15 Break (PODC)
15:45 - 16:15 Session SR1: SPAA Revue poster presentations

An Abstract Execution Model for Temporal Logic Programs for Multi-Processor Architectures
Mehmet A. Orgun

An Architecture-Independent Workload Characterization Model for Parallel Computer Architectures
Abdullah Ibrahim Almojel

Explicit Parallelism Description: An Attractive Alternative for Multithreaded Processors
Xavier Verians, Jean-Didier Legat, Jean-Jacques Quisquater and Benoit Macq

A Run-Time Performance Monitor for Message-Passing Parallel Programs
Kang Zhang, Kei-Chun Li and Chengzheng Sun

Tolerating Faults in Counting Networks
Marc D. Riedel and Jehoshua Bruck

(Additional poster presentations listed under SPAA Revue Research Announcements)

16:15 - 16:45 Session SR2: SPAA Revue feature talk
Thanks for the Memory Hierarchy
Thomas H. Cormen, Dartmouth College
16:15 - 16:55 Session BA3: PODC short talks

k-Stabilization of Reactive Tasks
Joffroy Beauquier, Christophe Genolini and Shay Kutten

Asynchronus Time-Adaptive Self Stabilization
Shay Kutten and Boaz Patt Shamir

Robust Efficient Distributed RSA-Key Generation
Yair Frankel, Philip D. MacKenzie and Moti Yung

Probabilistic Byzantine Quorum Systems (TR version)
Dahlia Malkhi, Michael Reiter, Avishai Wool and Rebecca N. Wright

16:45 - 17:45 Session SR3: SPAA Revue research announcements>

Parallel Shortest Path Algorithms: Identifying the Factors that Affect Performance*
Michelle Hribar, Valerie E. Taylor and David E. Boyce

A Cost Model for Communication on a Symmetric MultiProcessor*
Nancy M. Amato, Andrea Pietracaprina, Geppino Pucci, Lucia K. Dale and Jack Perdue

On the Performance and Scalability of Client-Server Based Parallel Disk I/O*
Erich Schikuta, Kurt Stockinger and Helmut Wanek

A Parallel Algorithm for Bound-Smoothing using Tetrangle Inequality
Kumar Rajan and Narsingh Deo

File Placement in a Web Cache Server*
Valery Soloviev and Andrew Yahin

New Bounds for Oblivious Mesh Routing*
Kazuo Iwama and Eiji Miyano

Disk Array Declustering Using Permutation Development Data Layout (PDDL)*
Thomas J.E. Schwarz, s.j. and Walter A. Burkhard

Communications-Efficient Multithreading on Wide-Area Networks*
Michael S. Bernstein and Bradley C. Kuszmaul

*research announcement to be supplemented with a poster presentation

16:55 - 17:15 Break (PODC)
17:15 - 17:55 Session BA4: PODC short talks

Efficient Evaluation of Causal Relations between Nonatomic Events
Ajay D. Kshemkalyani

An Agent-based Architecture for Building CORBA Distributed Systems
F. Bellas, R. Juanes, N. Rodriguez and A. Vina

Responsiveness and Consistency Tradeoffs in Interactive Groupware (PODC version)
Sumeer Bhola, Guru Banavar and Mustaque Ahamad

17:45 - 18:15 Session SR4: SPAA Revue feature talk
Data Management in Networks
Friedhelm Meyer auf der Heide, University of Paderborn

July 2, 1998, Thursday

9:30 - 10:45 Session L9

PODC: (Distributed Computing Issues on the Internet)

Supporting Quality Of Service in HTTP Servers (postscript, PDF)
Raju Pandey, J. Fritz Barnes and Ronald Olsson

The HIP Protocol for Hierarchical Multicast Routing
Clay Shields and J.J. Garcia-Luna-Aceves

In-Place Reconstruction of Delta Compressed Files
Randal C. Burns and Darrell D. E. Long


Linear Programming Models for Scheduling Systems of Affine Recurrence Equations -- a Comparative Study
Stephen Balev, Patrice Quinton, Sanjay Rajopadhye and Tanguy Risset

Efficient Communication Strategies for Ad-Hoc Wireless Networks
Micah Adler and Christian Scheideler

Scheduling Time-Constrained Communication in Linear Networks
Micah Adler, Arnold L. Rosenberg, Ramesh K. Sitaraman and Walter Unger

10:45 - 11:05 Break
11:05 - 12:20 Session L10

PODC: (Wait-Free Algorithms)

Adaptive Wait-Free Algorithms for Lattice Agreement and Renaming (PODC version)
Hagit Attiya and Arie Fouren

A Polylog Time Wait-Free Construction for Closed Objects
Tushar Chandra, Prasad Jayanti and King Tan

Structured Derivations of Consensus Algorithms for Failure Detectors
Jiong Yang, Gil Neiger and Eli Gafni


Asynchronous Parallel Algorithm for Mining Association Rules on a Shared-memory Multi-processors
David W. Cheung, Kan Hu and Shaowei Xia

Trace-Driven Studies of VLIW Video Signal Processors
Zhao Wu and Wayne Wolf

Detecting Data Races in Cilk Programs that Use Locks
Guang-Ien Cheng, Mingdong Feng, Charles E. Leiserson, Keith H. Randall and Andrew F. Stark

12:20 - 14:00 Lunch
14:00 Conferences adjourn

Links in This Document

The links in this document should provide you with access to the fullest versions of the papers that are available. In some cases, different versions are listed. Please consult the authors' home pages for further information and for email address by which you might inquire for future versions or related papers.

Authors of PODC papers wishing to be listed here should send email with the appropriate URL's to Gil Neiger ( and Yehuda Afek (

This page maintained by Gil Neiger.

Last modified: June 19, 1998