[The following information can be ftp'd anonymously from thumper.bellcore.com in pub/podc/podc94prog.tex thumper's IP address is 128.96.41.1] PODC '94 PROGRAM AND REGISTRATION IMPORTANT NOTE: Please note that hard copies of this program will NOT be widely distributed. This policy has allowed us to reduce registration fees substantially below last year's. Also note that the room accomodations INCLUDE meals. Since we have to pay for these rooms on July 15th to hold them, it is critical that you register promptly. There are nearby hotels, but the rate are likely to be higher and will not include meals. LATE REGISTRATION FEES WILL BE IMPOSED FOR CONFERENCE REGISTRATIONS POSTMARKED AFTER JULY 15th. Association for Computing Machinery Thirteenth Annual Symposium on Principles of Distributed Computing Griffin Commons on the UCLA Campus Los Angeles, California (U.S.A.) Sponsored by ACM SIGOPS and SIGACT With the support of The Computer Science Department at University of California, Los Angeles August 14-17, 1994 ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- PODC '94 Conference Registration --- UCLA --- August 14-17, 1994 Program registration includes: Sunday night reception, Banquet, coffee breaks and proceedings. Please circle the appropriate registration fees (quoted in US Dollars). NOTE: The student registration fee includes the banquet. Students NOT wishing to attend the banquet may deduct $35.00 from the registration fee. Please make your check or money order in US Dollars payable to: PODC '94. Before July 15 After July 15 ACM Member $215.00 $285.00 Non member $285.00 $355.00 Full time student $110.00 $135.00 Please mail to: PODC94 Registration c/o James E. Burns Bellcore, 3X-114 331 Newman Springs Road Red Bank, NJ 07701-5699 Name: _________________________________________ Affiliation: __________________________________ Surface Address: ______________________________ _________________________________________ _________________________________________ Name on badge: ________________________________ email: ________________________________________ ACM number: ___________________________________ Student ID number: ____________________________ Phone: ________________________________________ Dietary Restrictions: __________________________________________________ A conference registration/information desk will be set up in Griffin Commons at the UCLA Conference Center throughout the meeting hours of the conference. ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- PODC '94 Hotel Registration --- August 14-17, 1994 The PODC Committee must pay for the rooms in advance in order to reserve them. Please send in your (prepaid) reservations as early as possible, but no later than July 15, 1994. Availability and price of rooms after that date is uncertain. Please make your check or money order in US Dollars payable to: PODC '94. Accommodations at Sunset Village include breakfast, lunch and dinner in the Griffin Commons Dining Hall, in the same complex where the meetings will be held. Rooms include phone, TV, private bath, and daily maid service. Singles run $90.00/person/night, and doubles $70.00/person/night. Accommodations at UCLA Residence Halls include breakfast, lunch and dinner in the Residence Hall Cafeteria. Rooms include phones and maid service upon arrival. A community bath is located on each floor. Singles run $63.00/person/night, and doubles $42.00/person/night. Name: _________________________________________ Surface Address: ______________________________ _________________________________________ _________________________________________ Phone: ________________________________________ Arrival Date/Time: ____________________________ Departure Date/Time: __________________________ Sharing with: _________________________________ NOTE: The full amount must be paid in advance! Sunset Village: $90.00 single $70.00 double Residence Halls: $63.00 single $42.00 double Room accomodations: _____ Nights at $______/night Parking Permit: _____ Days at $5.00/day Total Remitted: $______________ Please mail reservations to: PODC94 Registration c/o James E. Burns Bellcore, 3X-114 331 Newman Springs Road Red Bank, NJ 07701-5699 ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- General Information Symposium Site PODC94 will be held on the campus of the University of California, Los Angeles. August in Los Angeles is warm (average 76F) and sunny with cooler evenings. Los Angeles offers activities to suit almost any taste, from beaches and mountains, to theater and museums, to night clubs and amusement parks. No matter what sights you plan on taking in, be sure to pack your sunglasses. Transportation to UCLA BY AIR: Los Angeles International Airport is located approximately 12 miles from the UCLA campus. Car rental can be arranged through any major rental car agency. If driving from the airport, take the San Diego Freeway (the 405) North to Sunset Boulevard Exit East and follow BY CAR directions below. Taxi Service is available from the airport to Westwood Village and the UCLA Residential Complex. Individual one-way fares range from approximately $14.00 for Super Shuttle (310-338-1111) to $25.00 for a taxi (Yellow Cab 310-837-7252, Checker Cab 310-822-7777). Bus service between the airport and UCLA is available through RTD bus line #560 (call 213-626-4455 for schedule and fare information). BY CAR: Heading South on the San Diego Freeway (the 405) take the Sunset Boulevard Exit. At the stop light turn left onto Sunset Boulevard. Proceed east on Sunset Boulevard to Bellagio. Heading North on the San Diego Freeway (the 405) take the Sunset Boulevard Exit. At the stop light turn right onto Sunset Boulevard. Proceed east on Sunset Boulevard to Bellagio. From Sunset, turn right onto Bellagio and proceed to the stop sign at the top of the hill. At the stop sign, turn left onto De Neve Drive. Proceed down the hill and park in the SV parking structure. Passports, Visas, and Foreign Exchange Participants are advised to check their individual circumstances for entry into the United States. Proceedings The proceedings will be distributed to all participants at the symposium. Remote Computer Access There will be terminals available for remotely accessing your home machines. Conference Committee Program Chair: David Peleg -- Weizmann Institute and IBM T.J. Watson General Chair: Jim Anderson -- University of North Carolina at Chapel Hill (anderson@cs.unc.edu) Treasurer: Jim Burns -- Bellcore (burns@nova.bellcore.com) Local Arrangements: Elizabeth Borowsky -- University of California at Los Angeles (podc94@cs.ucla.edu) Program Committee James Anderson---University of North Carolina at Chapel Hill Brian Bershad---University of Washington Israel Cidon---Sun Labs and Technion Michael J. Fischer---Yale University Shay Kutten---IBM T.J. Watson Yishay Mansour---Tel-Aviv University Keith Marzullo---University of California at San Diego David Peleg---Weizmann Institute, IBM T.J. Watson Mark Tuttle---DEC Cambridge Research Lab Orli Waarts---IBM Almaden Jennifer Welch---Texas A&M University Agenda and Technical Program ---Sunday, August 14--- Opening Reception, Griffin Commons Terrace ---Monday, August 15--- Session 1. Chair: Israel Cidon 8:30 Invited Lecture Jon S. Turner University Washington at St. Louis 9:30 Reconciliations John Howard, Shmuel Katz Mitsubishi Electric Research Lab, The Technion 9:50 Repeatable and portable message-passing programs Robert Cypher, Eric Leu IBM T.J. Watson, IBM Almaden 10:10 Coffee Break Session 2. Chair: Jim Anderson 10:40 Making operations of concurrent data types fast Martha J. Kosa Tennessee Technological University 11:00 Delimiting the power of bounded size synchronization objects Yehuda Afek, Gideon Stupp Tel-Aviv University 11:20 Wait-freedom vs. bounded wait-freedom in public data structures Hagit Brit, Shlomo Moran The Technion 11:40 Contention-free complexity of shared memory algorithms Rajeev Alur, Gadi Taubenfeld AT&T Bell Labs 12:00 Lunch Session 3. Chair: David Peleg 1:50 Self-stabilizing algorithms for finding centers and medians of trees Mehmet Hakan Karaata, Sriram V. Pemmaraju, Steven C. Bruell, Sukumar Ghosh University of Iowa 2:00 Leader Election in the presence of link failures Gurdip Singh Kansas State University 2:10 Stabilizing algorithms for diagnosing crash failures Jeffery C. Line, Sukumar Ghosh University of Iowa 2:20 On the coding of dependencies in distributed computations Claude Jard, Guy-Vincent Jourdan IRISA/CNRS Beaulieu 2:30 Probabilistic self-stabilizing mutual exclusion in uniform rings Joffroy Beauquier, Sylvie Dela\"et Universit\'e de Paris Sud 2:40 The impact of synchronization on the session problem Marios Mavronicolas University of Cyprus 2:50 A fault-tolerant dynamic resource allocation algorithm Injong Rhee Texas A&M University 3:00 Implementation of authenticated communication based on hierarchy-relative naming scheme Nobuhisa Fujinami Sony Computer Science Laboratory 3:10 Derivation of fault-tolerance properties of distributed algorithms Philippe Qu\'einnec, G\'erard Padiou IRIT Toulouse 3:20 Towards a minimal object-oriented language for distributed and concurrent programming Matthias Radestock, Susan Eisenbach Imperial College 3:30 CoLa: a coordination language for massive parallelism B\'eat Hirsbrunner, Marc Aguilar, Oliver Krone Universit\'e de Fribourg 3:40 Coffee Break Session 4. Chair: Mark Tuttle 4:00 Using belief to reason about cache coherence Lily B. Mummert, J.M. Wing, M. Satyanarayanan Carnegie Mellon University 4:20 Open systems in TLA Mart\'in Abadi and Leslie Lamport DEC Systems Research Center 4:40 ENF event predicate detection in distributed systems Willard Korfhage, Hsien-Kuang Chiou Polytechnic University 5:00 Mixed consistency: a model for parallel programming D. Agrawal, M. Choy, H.V. Leong, A.K. Singh University of California at Santa Barbara 5:20 Global flush communication primitive for sending a message to a group of processes Ashwani Gahlot, Mohan Ahuja and Timothy Carlson IBM Research Triangle, University of California at San Diego, Ohio State University 6:00 Banquet, Griffin Commons Study Lounge ---Tuesday, August 16--- Session 5. Chair: Orli Waartz 8:30 A checkpoint protocol for an entry consistent shared memory system Nuno Neves, Miguel Castro, Paulo Guedes IST - INESC Lisboa 8:50 A performance evaluation of lock-free synchronization protocols Anthony LaMarca University of Washington 9:10 Using $k$-exclusion to implement resilient, scalable shared objects James H. Anderson, Mark Moir University of North Carolina at Chapel Hill 9:30 Disjoint-access parallel implementations of strong shared memory primitives Amos Israeli, Lihu Rappoport The Technion 9:50 Coffee Break Session 6. Chair: Mark Tuttle 10:20 Time-optimal message-efficient work performance in the presence of faults Roberto De Prisco, Alain Mayer, Moti Yung Columbia University, Columbia University, IBM T.J. Watson 10:40 Resilience of general interactive tasks Benny Chor, Lee-Bath Nelson The Technion, Stanford University 11:00 Asynchronous computations with optimal resilience Michael Ben-Or, Boaz Kelmer, Tal Rabin Hebrew University 11:20 Coins, weights and bounded-time contention in balancing networks William Aiello, Ramarathnam Venkatesan, Moti Yung Bellcore, Bellcore, IBM T.J. Watson 11:40 A combinatorial treatment of balancing networks Costas Busch and Marios Mavronicolas University of Cyprus 12:00 Lunch Session 7. Chair: Shay Kutten 1:50 A characterization of networks supporting linear interval routing Pierre Fraigniaud, Cyril Gavoille Ecole Normale Sup\'erieure de Lyon 2:10 Potential function analysis of greedy hot-potato Routing Amir Ben-Dor, Shay Halevi and Assaf Schuster The Technion 2:30 The virtual path layout problem in fast networks Ornan Gerstel, Shmuel Zaks The Technion 2:50 Self-stabilization by counter flushing George Varghese Washington University at St. Louis 3:10 Memory-efficient and self-stabilizing network Reset Baruch Awerbuch, Rafail Ostrovsky MIT, University of California at Berkeley and ICSI 3:30 Coffee Break Session 8. Chair: Jennifer Welch 3:50 Efficient dynamic load sharing algorithm using scheduling information Seung Ho Cho, Seung Ryeol Choi, Sang Young Han Kangnam University, Seoul National University, Seoul National University 4:00 A recognise-and-accuse policy to speed up distributed processes A. Genco, G. Lo Re Universita di Palermo, Consiglio Nazionale delle Ricerche 4:10 Controlling real-time asynchronous tasks with ESTEREL synchronous language M. Adelantado, F. Boniol ONERA-CERT/DERI Toulouse 4:20 Consistency and conformance in ODP Howard Bowman, John Derrick University of Kent 4:30 XMP++: an object-oriented solution for hiding the complexity of network management protocols Sakari Rahkila, Susanne Stenberg Nokia Research Center 4:40 A compositional verification method for LOTOS Hacene Fouchal Institut National des Telecommunications Evry 4:50 Verification of a distributed algorithm K. Sere, M. Wald\'en University of Kuopio, \oAbo Akademi University 5:00 The formal verification of an ATM network Paul Curzon University of Cambridge 5:10 A verification method based on homomorphic model abstractions Ulrich Nitsche German National Research Centre for Computer Science 5:20 Modelling garbage collection algorithms using CCS and temporal logic Howard Bowman, John Derrick, Richard Jones University of Kent 5:30 Integrated support environment for concurrent process calculi Sen Yoshida, Atsushi Togashi and Norio Shiratori Tohoku University 8:00 Business Meeting and Rump Session: Buenos Aires Room, Sunset Canyon Recreational Center ---Wednesday, August 17--- Session 9. Chair: Keith Marzullo 8:30 Invited Lecture: A Quantitative Case for Networks of Workstations (NOW) David Patterson University of California at Berkeley 9:30 Adaptive algorithms for PASO systems Jeffery Westbrook, Lenore Zuck Yale University 9:50 Uniform actions in asynchronous distributed systems Dalia Malki, Ken Birman, Aleta Ricciardi, Andr\'e Schiper Hebrew University, Cornell University, Bell Northern Research, Ecole Polytechnique F\'ed\'erale Lausanne 10:10 Coffee Break Session 10. Chair: Yishay Mansour 10:40 Observable clock synchronization Danny Dolev, R\"udiger Reischuk, Ray Strong IBM Almaden 11:00 Knowledge, timed precedence and clocks Yoram Moses, Ben Bloom Weizmann Institute and Oxford University, Weizmann Institute 11:20 A formally verified algorithm for clock synchronization under a hybrid fault model John Rushby SRI International 11:40 Proving time bounds for randomized distributed algorithms Nancy Lynch, Isaac Saias, Roberto Segala MIT 12:00 Lunch Session 11. Chair: Orli Waartz 1:50 Set-Linearizability and obliviousness: foundations of the study of asynchronous computability Gil Neiger Georgia Institute of Technology 2:00 Dynamic sets for search David Steere, M. Satyanarayanan, Jeannette Wing Carnegie Mellon University 2:10 The competitive analysis of wait-free algorithms and its application to the cooperative collect problem Miklos Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts IBM Almaden, Yale University, IBM Almaden, IBM Almaden 2:20 Simulating fail-stop in asynchronous distribute systems Laura Sabel, Keith Marzullo Cornell University, University of California at San Diego 2:30 PCODE: efficient parallel computing over distributed environments Jehoshua Bruck, Danny Dolev, Ching-Tien Ho, Rimon Orni, Ray Strong IBM Almaden 2:40 On the memory overhead of distributed snapshots Lior Shabtai and Adrian Segall The Technion 2:50 Adaptive video on demand Sudhanshu Aggarwal, Juan Garay, Amir Herzberg MIT, IBM T.J. Watson, IBM T.J. Watson 3:00 Distributed pursuit-evasion: some aspects of privacy and security in distributed computing P. Spirakis, B. Tampakas Computer Technology Institute Patras 3:10 Contention in counting networks Costas Busch, Nikos Hardavellas, Marios Mavronicolas University of Cyprus 3:20 Coffee Break Session 12. Chair: Jennifer Welch 3:40 Set consensus using arbitrary objects Maurice Herlihy, Sergio Rajsbaum DEC Cambridge Research Lab, MIT 4:00 Wait-freedon vs. t-resiliency and the robustness of wait-free hierarchies Tushar Chandra, Vassos Hadzilacos, Prasad Jayanti, Sam Toueg IBM T.J. Watson, University of Toronto, Dartmouth College, Cornell University 4:20 A gap theorem for concensus types Gary L. Peterson, Rida A. Bazzi, Gil Neiger Spelman College, Georgia Institute of Technology, Georgia Institute of Technology 4:40 On the use of registers in achieving wait-free consensus Rida A. Bazzi, Gil Neiger, Gary L. Peterson Georgia Institute of Technology, Georgia Institute of Technology, Spelman College 5:00 Consensus power makes sense! Elizabeth Borowsky, Eli Gafni University for California at Los Angeles ----------**********----------**********----------**********---------- Jim Anderson anderson@cs.unc.edu PODC94 General Chair Computer Science Dept 919 962-1757 (voice) University of North Carolina 919 962-1799 (fax) Chapel Hill, NC 27599-3175