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 University17:30 - 19:30 Tutorial 2
High Performance Clusters: State of the Art and Challenges Ahead
David Culler, University of California, Berkeley20: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 Arizona10: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 PelegReconsidering Fragmentation and Reassembly
Girish P. Chandranmenon and George VargheseCompetitive Dynamic Bandwidth Allocation
Amotz Bar-Noy, Yishay Mansour and Baruch SchieberSPAA:
Elimination Forest Guided 2D Sparse LU Factorization
Kai Shen, Xiangmin Jiao and Tao YangFast Set Operations Using Treaps
Guy E. Blelloch and Margaret Reid-MillerCommunication-Optimal Parallel Minimum Spanning Tree Algorithms
Micah Adler, Wolfgang Dittrich, Ben Juurlink, Miroslaw Kutylowski and Ingo Rieping12: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 YungAn Adversarial Model for Distributed Dynamic Load Balancing
S. Muthukrishnan and Rajmohan RajaramanDeadlock-Free Routing in Arbitrary Networks via the Flattest Common Supersequence Method
Ambrose K. Laing and Robert CypherLamport Clocks: Verifying A Directory Cache-Coherence Protocol
Manoj Plakal, Daniel J. Sorin, Anne E. Condon and Mark D. Hill15: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 JoungCombining Funnels
Nir Shavit and Asaph ZemachSynchronization Mechanisms for SCRAMNet+ Systems
Stephen Menke, Mark Moir and Srikanth Ramamurthy20: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, Stanford10: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 RosenUniversal Service-Providers for Database Private Information Retrieval (abstract)
Giovanni Di-Crescenzo, Yuval Ishai and Rafail OstrovskySimplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptography
R. Gennaro, M. Rabin and T. RabinOptimal Efficiency of Optimistic Contract Signing
Birgit Pfitzmann, Matthias Schunter and Michael WaidnerSPAA:
Efficient Disk Allocation for Fast Similarity Searching
Sunil Prabhakar, Divyakant Agrawal and Amr El AbbadiA Framework for Simple Sorting Algorithms on Parallel Disk Systems
Sanguthevar RajasekaranBlocking in Parallel Multisearch Problems
Wolfgang Dittrich, David Hutchinson and Anil MaheshwariAutomatic Parallel I/O Performance Optimization in Panda
Y. Chen, M. Winslett, Y. Cho and S. Kuo12: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 RajsbaumUnifying Synchronous and Asynchronous Message-Passing Models
Maurice Herlihy, Sergio Rajsbaum and Mark TuttleRound-by-Round Fault Detectors: Unifying Synchrony and Asynchrony
Eli GafniSPAA:
Thread Scheduling for Multiprogrammed Multiprocessors
Nimar S. Arora, Robert D. Blumofe and C. Greg PlaxtonHow "Hard" is Thread Partitioning and How "Bad" is a List Scheduling Based Partitioning Algorithm?
Xinan Tang and Guang R. GaoExplicit Multi-Threading (XMT) Bridging Models for Instruction Parallelism
Uzi Vishkin, Shlomit Dascal, Efraim Berkovich and Joseph Nuzman15: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 BruckAn Error Control Scheme for Large-Scale Multicast Applications (Infocom '98 version)
Christos Papadopoulos, Guru Parulkar and George VargheseThe Global Efficiency of Distributed, Rate-Based, Flow Control Algorithms
Panagiota Fatourou, Marios Mavronicolas and Paul SpirakisScalable Best Matching Prefix Lookups (SIGCOMM '97 version, notes)
Marcel Waldvogel, George Varghese, Jon Turner and Bernhard PlattnerOptimal Allocation of Electronic Content in Networks
Israel Cidon, Shay Kutten and Ran Sofer16:55 - 17:15 Break 17:15 - 17:45 Session BA2: PODC short talks A Direct Lower Bound for k-Set Consensus (PODC version)
Hagit AttiyaMuteness Detectors for Consensus with Byzantine Processes
Assia Doudou and Andre SchiperImplementing and Evaluating an Eventually-Serializable Data Service
O. Cheiner and A. Shvartsman19:00 - 22:00 Banquet July 1, 1998, Wednesday
9:30 - 10:45 Session L6 PODC:
The Message Classification Model
Christof FetzerReliable Message Delivery and Conditionally-Fast Transactions are not Possible without Accurate Clocks
Mark A. SmithSynthesis of Fault-Tolerant Concurrent Programs
Anish Arora, Paul Attie and E. Allen EmersonSPAA:
Computational Bounds for Fundamental Problems on General-Purpose Parallel Models
Philip D. MacKenzie and Vijaya RamachandranBroadcasting, Multicasting and Gossiping in Trees under the All-Port Line Model
Johanne CohenLayout Area of the Bitonic Sorting Network
Shimon Even, S. Muthukrishnan, Michael S. Paterson and Suleyman Cenk Sahinalp10: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 JayantiA Tight Lower Bound for Randomized Synchronous Consensus
Ziv Bar-Joseph and Michael Ben-Or
Winner of best student paper awardA Time Complexity Lower Bound for Randomized Implementations of Some Shared Objects
Prasad JayantiConsensus Numbers of Multi-Objects
Eric RuppertSPAA:
Dynamic Scheduling with Incomplete Information
Hannah BastParallel Continuous Randomized Load Balancing
Petra Berenbrink, Tom Friedetzky and Ernst W. MayrRecovery Time of Dynamic Allocation Processes
Artur CzumajAnalyses of Load Stealing Models Based on Differential Equations
Michael Mitzenmacher12:45 - 14:30 Lunch 14:30 - 15:45 Session L8 PODC:
Persistent Messages in Local Transactions
David E. Lowell and Peter M. ChenA Dynamic View-Oriented Group Communication Service
R. De Prisco, A. Fekete, N. Lynch and A. ShvartsmanAn Adaptive Totally Ordered Multicast Protocol that Tolerates Partitions (gzipped)
Gregory V. Chockler, Nabil Huleihel and Danny DolevSPAA:
In-Memory Directories: Eliminating the Directory Overhead in CC-NUMAs
Christopher Ho, Heidi Ziegler and Michel DuboisUsing "Test Model-Checking" to Verify the Runway-PA8000 Memory Model
Rajnish Ghughal, Abdel Mokkedem, Ratan Nalumasu and Ganesh GopalakrishnanComputation-Centric Memory Models
Matteo Frigo and Victor Luchangco15: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. OrgunAn Architecture-Independent Workload Characterization Model for Parallel Computer Architectures
Abdullah Ibrahim AlmojelExplicit Parallelism Description: An Attractive Alternative for Multithreaded Processors
Xavier Verians, Jean-Didier Legat, Jean-Jacques Quisquater and Benoit MacqA Run-Time Performance Monitor for Message-Passing Parallel Programs
Kang Zhang, Kei-Chun Li and Chengzheng SunTolerating 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 College16:15 - 16:55 Session BA3: PODC short talks k-Stabilization of Reactive Tasks
Joffroy Beauquier, Christophe Genolini and Shay KuttenAsynchronus Time-Adaptive Self Stabilization
Shay Kutten and Boaz Patt ShamirRobust Efficient Distributed RSA-Key Generation
Yair Frankel, Philip D. MacKenzie and Moti YungProbabilistic Byzantine Quorum Systems (TR version)
Dahlia Malkhi, Michael Reiter, Avishai Wool and Rebecca N. Wright16: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. BoyceA Cost Model for Communication on a Symmetric MultiProcessor*
Nancy M. Amato, Andrea Pietracaprina, Geppino Pucci, Lucia K. Dale and Jack PerdueOn the Performance and Scalability of Client-Server Based Parallel Disk I/O*
Erich Schikuta, Kurt Stockinger and Helmut WanekA Parallel Algorithm for Bound-Smoothing using Tetrangle Inequality
Kumar Rajan and Narsingh DeoFile Placement in a Web Cache Server*
Valery Soloviev and Andrew YahinNew Bounds for Oblivious Mesh Routing*
Kazuo Iwama and Eiji MiyanoDisk Array Declustering Using Permutation Development Data Layout (PDDL)*
Thomas J.E. Schwarz, s.j. and Walter A. BurkhardCommunications-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. KshemkalyaniAn Agent-based Architecture for Building CORBA Distributed Systems
F. Bellas, R. Juanes, N. Rodriguez and A. VinaResponsiveness and Consistency Tradeoffs in Interactive Groupware (PODC version)
Sumeer Bhola, Guru Banavar and Mustaque Ahamad17:45 - 18:15 Session SR4: SPAA Revue feature talk
Data Management in Networks
Friedhelm Meyer auf der Heide, University of PaderbornJuly 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 OlssonThe HIP Protocol for Hierarchical Multicast Routing
Clay Shields and J.J. Garcia-Luna-AcevesIn-Place Reconstruction of Delta Compressed Files
Randal C. Burns and Darrell D. E. LongSPAA:
Linear Programming Models for Scheduling Systems of Affine Recurrence Equations -- a Comparative Study
Stephen Balev, Patrice Quinton, Sanjay Rajopadhye and Tanguy RissetEfficient Communication Strategies for Ad-Hoc Wireless Networks
Micah Adler and Christian ScheidelerScheduling Time-Constrained Communication in Linear Networks
Micah Adler, Arnold L. Rosenberg, Ramesh K. Sitaraman and Walter Unger10: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 FourenA Polylog Time Wait-Free Construction for Closed Objects
Tushar Chandra, Prasad Jayanti and King TanStructured Derivations of Consensus Algorithms for Failure Detectors
Jiong Yang, Gil Neiger and Eli GafniSPAA:
Asynchronous Parallel Algorithm for Mining Association Rules on a Shared-memory Multi-processors
David W. Cheung, Kan Hu and Shaowei XiaTrace-Driven Studies of VLIW Video Signal Processors
Zhao Wu and Wayne WolfDetecting Data Races in Cilk Programs that Use Locks
Guang-Ien Cheng, Mingdong Feng, Charles E. Leiserson, Keith H. Randall and Andrew F. Stark12:20 - 14:00 Lunch 14:00 Conferences adjourn
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 (gilATacm.org) and Yehuda Afek (afek@math.tau.ac.il).