annerie@praxis.cs.ruu.nl (Annerie Deckers) (09/18/90)
LAST CALL LAST CALL LAST CALL LAST CALL LAST CALL LAST CALL LAST CALL
4th International Workshop on Distributed Algorithms
Serra Alimini - Otranto - Italy
September 24-25-26 1990
Organized by:
Istituto di Scienze dell'Informazione
Facolta' di Scienze M.F.N.
University of Bari - Italy
With the collaboration of:
Department of Computer Science
University of Utrecht - The Netherlands
and
Center for Parallel and Distributed Computing (Paradise)
Carleton University, Ottawa - Canada
The Workshop on Distributed Algorithms is intended to provide an
international forum for researchers in the area of
distributed algorithms and distributed systems, to present and discuss recent
research results and to identify and explore directions for future research.
The Workshop was previously held in Ottawa (1985), Amsterdam (1987), and Nice
(1989).
Program Committee
D. Dolev (Hebrew Univ., and IBM Almaden), J. van Leeuwen (Univ. of Utrecht,
co- chairman), F. Mattern (Kaiserslautern), N. Santoro (Carleton Univ. and Univ. of Bari, co-chairman), P. Spirakis (NYU and CTI Patras), R.B. Tan (Univ. of
Oklahoma and Univ. of Utrecht), S. Toueg (Cornell Univ.), P.M.B. Vitanyi (CWI
and Univ. of Amsterdam), and S. Zaks (Technion).
Proceedings
The proceedings of the Workshop will be published in the series Lecture Notes
in Computer Science by Springer Verlag.
Organizing Committee Chairman
Giovanni Pani - University of Bari and Oxford University
Organizing Secretariat
Centro Internazionale Congressi S.r.l.
Viale Papa Pio XII, 18
70124 Bari
Italy
tel. +39-80-517299
fax +39-80-514533
Scientific Program
Monday, September 24, 1990
09.00: Opening remarks: N. Santoro - University of Bari and Carleton Univer-
sity, Ottawa
Chairman: J. van Leeuwen - University of Utrecht
09.10: Self-Stabilizing Ring Orientation
A. Israeli, M. Jalfon - Technion, Haifa
09.35: Memory-Efficient Self-Stabilization on General Networks
Y. Afek - Tel-Aviv University
S. Kutten, M. Yung - IBM T.J. Watson Research Center, Yorktown Heights
10.00: Break
Chairman: P. Spirakis - New York University and CTI Patras
10.25: On the Computational Power Needed to Elect a Leader
A. Itai - Technion, Haifa
10.50: Spanning Tree Construction for Nameless Networks
I. Lavallee, C. Lavault - INRIA, Rocquencourt
11.15: Break
Chairman: S. Zaks - Technion, Haifa
11.40: A Linear Fault-Tolerant Naming Algorithm
J. Beauquier - Universite Paris 11
P. Gastin - Universite Paris 6
V. Villain - Universite de Picardie, Amiens
12.05: Distributed Data Structures: A Complexity-Oriented View
D. Peleg - The Weizmann Institute, Rehovot
12.30: Lunch
Chairman: F. Mattern - University of Kaiserslautern
15.00: An Improved Algorithm to Detect Communication Deadlocks in Distributed
Systems
B. Kroger, O. Vornberger - University of Osnabruck
R. Luling, B. Monien - University of Paderborn
15.25: On the Average Performance of Synchronized Programs in Distributed
Networks
S. Rajsbaum, M. Sidi - Technion, Haifa
15.50: Break
Chairman: R.B. Tan - University of Oklahoma, Chickasha and University of Utrecht
16.15: Distributed Algorithms for Reconstructing MST after Topology Change
J. Park - Kangweon National University
T. Masuzawa, K. Hagihara, N. Tokura - Osaka University
H. Yang - Kangweon National University
16.40: Efficient Distributed Algorithms for Single-Source Paths and Related
Problems on Plane Networks
R. Janardan, S. Wing Cheng - University of Minnesota, Minneapolis
17.05: Break
Chairman: M. Raynal - Universite de Rennes
17.30: Stepwise Development of a Distributed Load Balancing Algorithm
P. Gronning, T. Qvist Nielsen, H. H. Lovengreen - Technical University
of Denmark, Lyngby
17.55: Greedy Packet Scheduling
I. Cidon, S. Kutten - IBM T.J. Watson Research Center, Yorktown Heights
Y. Mansour - MIT, Cambridge, MA
D. Peleg - The Weizmann Institute, Rehovot
Tuesday, September 25, 1990
Chairman: P. Spirakis - New York University and CTI Patras
09.10: Optimal Computation of Global Sensitive Functions in Fast Networks
I. Cidon, I. Gopal, S. Kutten - IBM T.J. Watson Research Center, York-
town Heights
09.35: Efficient Mechanism for Fairness and Deadlock-Avoidance in High-Speed
Networks
Y. Ofek, M. Yung - IBM T.J. Watson Research Center, Yorktown Heights
10.00: Strong Verifiable Secret Sharing
C. Dwork - IBM Almaden Research Center and MIT, Cambridge, MA
10.25: Break
Chairman: J. van Leeuwen - University of Utrecht
10.50: Weak Consistency and Pessimistic Replica Control
A. Sandoz, A. Schiper - Ecole Polytechnique Federale de Lausanne
11.15: Localized-Access Protocols for Replicated Databases
D. Agrawal, A. El Abbadi - University of California, Santa Barbara
11.40: Weighted Voting for Operation Dependent Management of Replicated Data
M. Obradovic, P. Berman - Pennsylvania State University, University Park
12.30: Lunch
Excursion to Lecce
5
Wednesday, September 26, 1990
Chairman: P. Spirakis - New York University and CTI Patras
08.45: Wakeup under Read/Write Atomicity
P. Jayanti, S. Toueg - Cornell University, Ithaca
09.10: Time and Message Efficient Reliable Broadcasts
T. Chandra, S. Toueg - Cornell University, Ithaca
09.35: Early-Stopping Distributed Bidding and Applications
N. Budhiraja, A. Gopal, S. Toueg - Cornell University, Ithaca
10.00: Break
Chairman: D. Dolev - Hebrew University, Jerusalem and IBM Almaden Research
Center
10.25: Fast Consensus in Networks of Bounded Degree
P. Berman - Pennsylvania State University, University Park
J. A. Garay - IBM T.J. Watson Research Center, Yorktown Heights
10.50: Using Common Knowledge to Consistently Coordinate Simultaneous
Actions in Systems with Failures
G. Neiger - Georgia Institute of Technology, Atlanta
M. R. Tuttle - Cambridge Research Laboratory, MA
11.15: Break
Chairman: N. Santoro - University of Bari and Carleton University, Ottawa
11.40: Agreement on the Group Membership in Distributed Systems
R. de Lemos, P. D. Ezhilchelvan - University of Newcastle upon Tyne
12.05: Tight Bounds on the Round Complexity of Distributed 1-Solvable Tasks
O. Biran, S. Moran, S. Zaks - Technion, Haifa
12.30: Break
Chairman: P. Vitanyi - CWI and University of Amsterdam
15.00: A Time-Randomness Tradeoff for Communication Complexity
R. Fleischer - University of Saarland, Saarbrucken
H. Jung - Humboldt University, Berlin
K. Mehlhorn - University of Saarland, Saarbrucken
15.25: Bounds on the Costs of Register Implementations
S. Chaudhuri - University of Washington, Seattle
J. L. Welch - University of North Carolina, Chapel Hill
15.50: A Bounded First-In, First-Enabled-Solution to the l-Exclusion Problem
Y. Afek - AT&T Bell Laboratories, Murray Hill and Tel-Aviv University
D. Dolev - IBM Almaden Research Center and Hebrew University, Jerusalem
E. Gafni - Tel-Aviv University and University of California, Los Angeles
M. Merritt - AT&T Bell Laboratories, Murray Hill
N. Shavit - IBM Almaden Research Center and Stanford University
Excursion to Otranto.
General Information
Workshop Location
The 4th International Workshop on Distributed Algorithms will be held at Serra
Alimini Uno (Otranto) in the region of Bari -Italy. Serra Alimini Uno
(Tel. +39-836-85205) is a tourist village which faces the Adriatic sea and has
all the amenities to make your stay very enjoyable. It is in the southern part
of Apulia, famous for its beautiful beaches and its sea. The participants will
be accommodated in holiday cottages with private gardens. The cottages consist of 1, 2 or 3 bedrooms and a bathroom. Each participant will have a private
bedroom.
>From the cottages, one can walk to the congress hall, the restaurant, the
beach es and all the facilities: swimming pool, tennis courts, riding-ground;
the use of the latter facilities is not included in the registration fee.
The weather at Otranto in late September is around 20C-29C (70F-85F). It is
very warm in the daytime but may be a little bit cool at night in the breeze,
so bring a light sweater or jacket.
Registration
All Workshop attendees are required to register. Please complete and return
the enclosed registration form to Centro Internazionale Congressi S.r.l., Viale Papa Pio XII, 18, 70124 Bari, Italy.
Fee
before_August_31_ after_August_31_
Full Workshop Fee Lit. 427,000 (350$)Lit. 549,000 (450$)
Students Lit. 244,000 (200$)Lit. 366,000 (300$)
Accompanying Person Lit. 366,000 (300$)Lit. 488,000 (400$)
The 10.07.1990 exchange rate is : 1 U.S. $ = Lit. 1,220 approx. The above
mentioned amounts qouted in U.S. $are purely indicative and must be kept as
an unofficial reference. The only official amounts are those quoted in
Italian Lire which is the only currency to be used for payment.
The registration fee is to be made payable in Italian Lire by an international
cheque and sent to Centro Internazionale Congressi S.r.l. along with the
registration form.
The fee for the workshop covers:
half board on September 23, 1990;
full board on September 24, 25, 26, 1990;
the workshop proceedings which will be mailed after the workshop;
bus transportation service from Bari airport, Bari railway station and
Brindisi airport to Serra Alimini on sunday September 23 and vice versa on
Thursday September 27;
excursion to Lecce and Otranto.
Participants will be accommodated in cottages with 2 or 3 bedrooms on a first-
come, first- served basis. For the participants wishing to reserve accom-
modation in a single room cottage, there will be an extra charge of Lit.
100,000 (82 $)for the three days. Only a limited number of single rooms are
available.
All the above amounts include VAT.
Transportation
A bus transportation service to and from Serra Alimini has been arranged for
the participants according to the following timetable:
Sunday September 23
departure from Bari Airport and from Bari railway station at 08.00 p.m.
departure from Brindisi Airport at 09.30 p.m.
arrival at Serra Alimini at about 10.30 p.m.
Thursday September 27
departure from Serra Alimini at 07.30 a.m.
arrival at Brindisi Airport at about 08.30 a.m.
arrival at Bari Airport at about 10.00 a.m.
arrival at Bari railway station at about 10.30 a.m.
The bus will show a sign indicating the name of the Workshop. Participants are
recommended to use this bus transportation service as it is rather difficult
to reach Serra Alimini individually.
Bari and Brindisi Transportation Connections
By Plane
Town |Frequency |Dep. |Arr. |
| | | |
>From Rome to Bari |Daily |09.10 |10.10 |
|" |13.30 |14.30 |
|" |15.40 |16.40 |
|" |17.20 |18.20 |
|" |22.00 |23.00 |
>From Bari to Rome |Daily |07.00 |08.00 |
|" |11.00 |12.00 |
|" |13.40 |14.40 |
|" |15.20 |16.20 |
|" |19.10 |20.10 |
>From Milano Linate to Bari |Daily |07.00 |10.00 |Via Roma
|" |11.25 |12.50 |
|" |15.00 |18.20 |Via Roma
|" |20.20 |21.45 |
>From Bari to Milano Linate |Daily |07.40 |09.05 |
|" |11.00 |14.05 |Via Roma
|" |13.40 |17.05 |Via Roma
|" |17.30 |18.55 |
|" |19.10 |22.05 |Via Roma
>From Rome to Brindisi |Daily |09.50 |10.55 |
|" |17.05 |18.10 |
|" |21.00 |22.05 |
>From Brindisi to Rome |Daily |07.00 |08.10 |
|" |11.40 |12.50 |
|" |19.00 |20.10 |
>From Milano Linate to Brindisi|Daily |07.00 |10.55 |Via Roma
|" |13.35 |15.05 |
|" |15.00 |18.10 |Via Roma
|" |19.00 |22.05 |Via Roma
>From Brindisi to Milano Linate|Daily |07.00 |11.05 |Via Roma
|" |07.00 |10.05 |Via Roma
|" |11.40 |15.05 |Via Roma
|" |11.40 |16.15 |Via Roma
|" |15.50 |17.25 |
|" |19.00 |22.05 |Via Roma
By Train
Town | Dep. |Arr. |
| | |
>From Rome to Bari |07.15 |12.34 |Intercity
| 16.20 |22.20 |Intercity
| 18.10 |22.40 |Intercity ETR 450
| 23.20 |06.28 |
>From Bari to Rome |06.00 |10.30 |Intercity Pendolino
| 17.54 |23.15 |Intercity
| 00.37 |08.10 |
>From Milano to Bari | 07.00 |15.32 |Intercity
| 11.00 |19.37 |Intercity
| 12.00 |20.59 |Intercity
| 13.55 |22.59 |Intercity
| 20.46 |06.12 |
>From Bari to Milano | 07.37 |15.55 |Intercity
| 09.18 |18.00 |Intercity
| 11.50 |21.10 |Intercity
| 15.13 |23.00 |Intercity
| 19.49 |06.05 |