WDAG '94: Advance Program

Note that you can combine
in one and the same week in the Netherlands the two conferences
ESA'94 in Utrecht and WDAG'94 on Terschelling, because they are
carefully planned back-to-back.

**********************

         8TH INTERNATIONAL WORKSHOP ON

            DISTRIBUTED ALGORITHMS

                    WDAG '94

                Sponsored by
           EATCS, CWI and Utrecht Univ.
                NFI through NWO
        September 29 --- October 1, 1994
         Terschelling, The Netherlands




        ADVANCE REGISTRATION FORM

Last name           ____________________________________________

First name          ____________________________________________

Affiliation         ____________________________________________

Mailing address     ____________________________________________

                    ____________________________________________

                    ____________________________________________

EMail address       ____________________________________________

Telephone           ____________________________________________

Registration fee*   Dfl                         _________________

Accompanying Person(s)   Dfl                   _________________

Extra Banquet Ticket(s)     Dfl                _________________

WDAG Bus Sept 28     Dfl                       _________________

WDAG Bus Oct 1     Dfl                         _________________
                                               -----------------

Total                     Dfl                  _________________

   See below for methods of payment.


Conference Fee *        Before Aug. 15          After  Aug. 15

Double Occupancy &      Dfl     950             Dfl     1.100
Single Occupancy        Dfl   1.100             Dfl     1.250
Students &%$            Dfl     800             Dfl       900
Accompanying Person %   Dfl     600             Dfl       700
Extra Proceedings       Dfl      75             Dfl        75
Extra Banquet Ticket    Dfl      75             Dfl        75
WDAG Bus Sept 28 #      Dfl      50             Dfl        50
WDAG Bus Oct 1 #        Dfl      50             Dfl        50

*Includes proceedings, breakfasts, lunches, dinners, three
nights conference hotel and all social events.
& Specify room mate below.
% Double occupancy; includes all meals and banquet.
$ Proof of full-time studentship required (like letter of adviser)
# Only with sufficient pre-registration.

       Single room     _____                (Check
       Double room     _____                  one)

  If sharing a room, with whom:     _____________________________

       Request Free Bicycle               _______________________
       WDAG Bus to Workshop on Sept 28    _______________________
       WDAG Bus to Amsterdam on Oct 1     _______________________


=================================================================
    Credit Card Information  (if applicable)

  VISA / MasterCard / American Express

  Exp. Date  _______ Card # _____________________________________

  Name &  Address    ____________________________________________

  of Card Holder     ____________________________________________

                     ____________________________________________

                     ____________________________________________

         Authorization:  I authorize Stichting WIC to
         charge my credit card the above amount.


  Signature______________________________________________________
 =================================================================
    Return form (with payment slip) to:

  WDAG'94 c/o Ms. Anna Baanders
  CWI
  P.O. Box 94079
  1090 GB Amsterdam
  The Netherlands [1ex]
  Telefax: +31 20 592 4199

   Email registrations and registration forms
not accompanied by payment will not be accepted.



    CONFERENCE HOTEL

The conference hotel is the Golden Tulip Hotel Schylge,
Burgemeester van Heusdenweg 37, 8881 ED Terschelling-West, The Netherlands.
Telephone: +31 5620 2111; Telefax: +31 5620 2800.
The hotel is located on a beautiful bay
with a view of the harbour and the Wadden Sea (wetlands
with tidal mudflats),
at the edge of the picturesque
village of West-Terschelling
on Terschelling (Island), a ten minutes walk from ferry arrival.
The conference rates quoted
include service, VAT, and all meals.  Contact Anna Baanders
(anna@cwi.nl) for
information on children's rates.


    METHODS OF PAYMENT

Combined payment for the Conference fee and the hotel registration is
required.  Payment can be made by VISA, MasterCard, American Express, a
bank cheque in Dutch Guilders, Eurocheque, or bank transfer.     Personal
cheques will not be accepted.  On cheques, mention ``WDAG'94'' and the
name of the participant(s).  Direct transfers to / make out cheques to
Account   31.35.57.977 of
Stichting WIC, Amsterdam; RABO-bank, Middenweg
88, Amsterdam, The Netherlands.
Upon cancellation in writing received before September 1, the
registration fee will be refunded in full, less Dfl 100 for
administration and handling fee. Regretfully,
after September 1, no refund is possible.


    ADDITIONAL PROCEEDINGS

These will be available on site and cost about Dfl 75 each.


    CONFERENCE INFORMATION

  Location:
Terschelling is one of the most picturesque islands of the chain
in the north of the Netherlands (Frisia province). With a length of 30 km
and an average width of 3.5 km the island exhibits a rich
variety of landscapes of great natural beauty.
On the north side the white sand beach is 30 km
long and at some places over 1 km wide. The beach is separated
from woods by a strip of natural sand dunes
in some places over a km wide, which in turn give way to reclaimed
land (polders) with pastures. The south side of the island
is separated from the shallow Wadden Sea by dikes. There is
a rich variety of vegetation  throughout the 80   uncultivated area.
The eastern half of the island is formed by the nature reserve
`De Boschplaat', awarded `European Natural Monument' status in 1970,
one of the richest bird sanctuaries in the world. With seals
and sea lions,
four more (national) Natural Monuments, the ecology
has more variety and richness than anywhere in the Netherlands. The village
of West-Terschelling, the largest village on the island,
boasts a rich collection of whaler's captain's houses dating
from the 16th  and 17th century. This includes the house (with
the `watchful eye') of
Willem Barentsz (ca 1550-1597), famous explorer of the north route
to India and Cathay in the 16th century, discoverer of Nova Zembla,
and namegiver of the Barentsz Sea, Barentsz Shallows, and Barentsz Island.
The 55 meter tall lighthouse Brandaris
dating from 1323 (current structure from 1594),
may be one of the oldest continuously operating lighthouses in the world.
There are lots of cozy bars and other holiday paraphernalia.
The church of the hamlet of Hoorn
on the east side of the island dates from the 12th century.
As is to be expected, the island can be explored excellently
on foot and on bicycle. Conference participants
which so desire will be provided with bicycles free of charge.

  Weather: The weather should be sunny with occasional showers,
possibly windy, and a day time temperature
between 14 C and 20 C. Just in case (since Terschelling
is on the latitude north of the equator) bring a warm
sweater and wind-cheater.

  Social Program:  Wednesday Night:  Reception and Registration at the
Golden Tulip Hotel Schylge from 20.00---23.00 hours.
Thursday Night:  Business meeting in Hotel Schylge.
Friday afternoon: hike in the Natural Monument
`Dodemanskisten' (Dead men's coffins).
Friday Night:  Banquet.

  Invited Lectures:  There will be invited lectures
by Arjen Lenstra (Bellcore), Moti Yung (IBM T.J. Watson),
and Wolfgang Paul (Univ. Saarlandes, Saarbruecken).

  Combining ESA and WDAG:  The 8th International Workshop on
Distributed Algorithms (WDAG'94)
and the 2nd European Symposium on Algorithms (ESA'94) both take
place in the Netherlands and are carefully planned back-to-back
in a single week from Monday September 26 through Saterday
October 1 to facilitate a combined attendance.
ESA takes place  September 26-28, 1994, Papendal, Utrecht, The Netherlands.
One can travel in the afternoon of Wednesday September 28
from one location to the other---but be sure to plan your itinerary to
catch the last ferry (see `Getting There').


    GETTING THERE

  By airplane:  Amsterdam is served by the Schiphol International
Airport, a major European airport.  From the airport, take a train to the
Amsterdam Central Station and follow the ``by train'' instructions.
(Beware of pick-pockets active at Schiphol Airport and
in connecting public transport.)

  By train:  From Amsterdam Central Station, from Utrecht
Central Station, or from Schiphol Airport, take a train to
Leeuwarden, and change there to the train to Harlingen Haven
(Haven = Harbour). Tickets cost Dfl 40--45 (one-way).
Departure time from
Amsterdam Central Station (xx =  full hour): xx.02 (change at Amersfoort)
and xx.32 (direct) to Leeuwarden (each hour xx). Duration: 2 hours
23 minutes. From Schiphol
Airport same train at xx.35 (change at Amersfoort)
and xx.05 (direct). Duration: 2 hours 50 minutes. Departure time
from Utrecht Central Station: xx.22 (direct)
and xx.52 (change at Amersfoort). Duration:
1 hour 51 minutes. The train Leeuwarden-Harlingen-Harlingen Haven
departs from Leeuwarden at xx.19 and xx.50 in between 12.50 and 14.50
and in between 17.50 and 19.19. Exit at Harlingen Haven.
>From here follow ``by ferry'' instructions.

  By train/bus:  This is shorter but suffers from
possibly bad connections. From Amsterdam Central Station
take the train to Alkmaar. At Alkmaar Station take
the (infrequent) FRAM Bus crossing
the `Afsluitdijk' to Harlingen, and exit at Harlingen Haven.
>From here follow ``by ferry'' instructions.

  By automobile:  From Utrecht go to Amsterdam
and take the Ring Freeway direction Zaandam and Leeuwarden.
>From Amsterdam take Freeway A7 (north) to Leeuwarden.
On the way you will cross the big dike `Afsluitdijk' which
is ca 30 km long (the biggest dike of Holland).
Just after the dike follow signs to Harlingen and exit the
freeway at the
`Ferry Terschelling' exit after the Harlingen exit.
You  cannot long term park  your car either in town
or on the short term parking in front of the ferry ticket office.
Unload your luggage at the ticket office and
instead follow the signs to the long parking lot where you can
park your car at a moderate daily fee (ca 15 minutes walking back
from the exit nearest to the ferry).

  WDAG Bus:  If there are enough pre-registrants
for the Dfl 50 bus departing from Amsterdam CS
(Central Station---North Exit (Noord Uitgang))
at 13.00 on September 28, to catch the ferry
of 15.05 in Harlingen Haven, then we will arrange for that.
Similarly, for going back to Amsterdam CS with
the WDAG Bus connecting to the 16.45 ferry from
Terschelling on Saterday, October 1 (arrival at
Amsterdam CS about 20.00).

  By ferry:  The ferry to Terschelling (included in your
registration fee) departs from the traditional town of Harlingen.
Car ferries depart from Harlingen harbour in September at 10.05, 15.05, and
19.50 taking about 1 hour 45 minutes to arrive at West-Terschelling.
The fast catamaran `Koegelwieck'  (with Dfl 7.50 surcharge) departs from
Harlingen harbour at 8.00  (Mo) and 9.00 (Tue-Sat) via Vlieland,
12.20, 15.30 (Wed), 18.00. It takes about 45 minutes.
>From West-Terschelling to Harlingen harbour
in September at 07.00, 12.35, 17.35 (car ferry),
and at 06.45 (Mo), 07.45 (Tue-Sat), 10.30 via Vlieland,
14.30 (Wed) 16.45 (Koegelwieck). On October 1 the winter schedule
starts which is less frequent with the last ferry at
16.45.  Further information at
`Rederij Doeksen' +31 5620 2770
(information car ferry), +31 5620 3220 (Koegelwieck),
+31 5620 6111 (reservation car transport). We believe that
car transportation is booked full very long in advance
(and you do not need a car on the island). Ferry transport
is included in the registration package---this means that
if you pre-register we will send the tickets to
you together with the hotel reservation documents.
If you do not pre-register, then you may have to pay
the ferry yourself since we cannot pre-send the ferry
ticket.
In case you miss the last ferry: Harlingen is an
old port town with 17th century houses, cozy bars,
and some nice small hotels near the harbour where
you can stay over to take next day's ferry.


    MESSAGES  & ADDITIONAL INFORMATION

Messages for attendees should be addressed to Hotel Schylge,
Telephone: +31 5620 2111; Telefax: +31 5620 2800,
in name of the attendee or WDAG'94 Organizers.

    ACKNOWLEDGMENTS

  Sponsors: This workshop is sponsored by a generous
grant from  `Nationale Faciliteit Informatica (NFI)'
administred through the Netherlands Organization for Scientific
Research (NWO). The NFI is
an independent public-policy research programme
established by the Ministry of Economic Affairs
to sponsor large scale efforts in targeted growth areas in computer science
and its applications. The project sponsoring this workshop
is `Algorithmic Aspects of Parallel and
Distributed Computing (ALADDIN)',  Contract Number NF 62-376, a
joint project of the CWI (Centrum voor Wiskunde en
(Universiteit Utrecht).
The workshop is further sponsored by
EATCS, ERCIM, CWI, and UU.

  Local Arrangements:  Gerard Tel (co-chair), Univ. Utrecht;
Paul Vitanyi (co-chair), CWI & Univ. Amsterdam;
and Anna Baanders (secretary), CWI.

  Program Committee: J. Anderson (Univ North Carolina at Chapel Hill, USA);
A. Bar-Noy (IBM T.J. Watson Res., USA); O. Babaoglu (Univ Bologna, Italy);
F. Chin (Univ. Hong Kong, Hong Kong); B. Charron-Bost (LITP Paris, France);
I. Gopal (IBM T.J. Watson Res., USA); M. Herlihy (DEC CRL, USA);
A. Israeli (Technion, Israel); S. Kutten (IBM T.J. Watson Res., USA);
S. Mullender (Twente Univ., Netherlands); G. Neiger (Georgia Tech., USA);
G. Tel (Utrecht Univ., Netherlands, co-chair); P. Vitanyi (CWI and
Univ. Amsterdam, Netherlands, co-chair).

  Steering Committee:  D. Dolev (IBM Almaden & Hebrew Univ.);
F. Mattern (Univ. Saarlandes); N. Santoro (Carleton Univ.);
A. Schiper (EPF, Lausanne); P. Spirakis (CTI   Univ. Patras);
R. Tan (Univ. Oklahoma); G. Tel (Univ. Utrecht); S. Toueg (Cornell Univ.);
P. Vitanyi (CWI   Univ. Amsterdam); S. Zaks (Technion).


    PROGRAM

All sessions will be at conference Golden Tulip Hotel Schylge.
Rump sessions will be scheduled at the conference.


   RECEPTION/REGISTRATION:  Wednesday from 20:00 to 23:00
at the Hotel Schylge.



   SESSION 1:  Thursday, September 29, Morning
Chair: Paul Vitanyi

  9:00--9:50
   Factoring on the Internet (Invited Lecture),
A.K. Lenstra (Bellcore, USA)

  9:50--10:20
   Replicated File Management in Large-Scale Distributed Systems
O. Babaoglu (Univ. Bologna, Italy), A. Bartoli (Univ. Pisa, Italy),
G. Dini (Univ. Pisa, Italy)

  10:20--10:50
Break

   SESSION 2:  Thursday, September 29, Morning
Chair:  Sape Mullender

  10:50--11:20
   Self-Stabilization by Local Checking and Global Reset ,
B. Awerbuch (Johns Hopkins Univ. &  MIT, USA),
B. Patt-Shamir (MIT, USA), G. Varghese (Washington Univ., USA)

  11:20--11:50
   Local Labeling and Resource Allocation Using Preprocessing ,
H. Attiya (Technion, Israel), H. Shachnai (IBM T.J. Watson, USA),
T. Tamir (Technion, Israel)

  11.50--12.20
   Uniform Deterministic Self-Stabilizing Ring-Orientation in Odd-Length
Rings ,
J.-H. Hoepman (CWI, Netherlands)


    LUNCH:  Starting at 12:30.


   SESSION 3:  Thursday, September 29, Afternoon
Chair: Shay Kutten


  14:00--14:30
   Reaching (and Maintaining) Agreement in the Presense of Mobile Faults ,
J.A. Garay (IBM T.J. Watson, USA)

  14:30--15:00
   Using Failure Detectors to Solve Consensus in Asynchronous
Shared-Memory Systems , W.-K. Lo (Univ. Toronto, Canada),
V. Hadzilacos (Univ. Toronto, Canada)

   15.00--15.30
   Primary Partition `Virtually-Synchronous Communication' is harder
than Consensus , A. Schiper (EPF Lausanne, Switzerland),
A. Sandoz (EPF Lausanne, Switzerland)

  15:30--16:00
Break


   SESSION 4:  Thursday, September 29, Afternoon
Chair:  Gil Neiger

  16.00--16.30
   Anomalies in the Wait-Free Hierarchy , O. Rachman (Technion, Israel)

  16.30-17.00
   Exotic Behavior of Consensus Numbers , R. Cori (Univ. Bordeaux I &
Ecole Polytechnique, France), S. Moran (Technion, Israel)

  17.00--17.30
   Coping With Contention , A.K. Singh (Univ. California at Santa Barbara, USA),
M. Choy (Univ. California at Santa Barbara, USA)


     DINNER:  From 19:00 to 20.30.


    BUSINESS MEETING:   From 20:30 to
22:00.

    SESSION 5:  Friday, September 30, Morning
Chair: Gerard Tel

  9.00-9.50
   Distributed Secure Computation: Theory and Practice
(Invited Lecture), M. Yung (IBM T.J. Watson, USA)

  9:50--10:20
   Low Complexity Network Synchronization , L Shabtay (Technion, Israel),
A. Segall (Technion, Israel)

  10:20--10:50
Break

    SESSION 6:  Friday, September 30, Morning
Chair:  Amotz Bar-Noy

  10:50--11:20
   Fast, Long-Lived Renaming , M. Moir (Univ. North Carolina at Chapel
Hill, USA), J. Anderson (Univ. North Carolina at Chapel Hill, USA)

   11:20--11:50
   Fast Increment Registers , S. Chaudhuri (Iowa State Univ., USA),
M. R. Tuttle (DEC Cambridge Research Lab., USA)

  11:50--12:20
   Average and Randomized Complexity of Distributed Problems ,
N. Alanberg-Navony (Technion, Israel), A. Itai (Technion, Israel),
S. Moran (Technion, Israel)

    LUNCH:  Starting at 12:30.


    SESSION 7:  Friday, September 30, Afternoon
Chair: Bernadette Charron-Bost

  14:00--14:30
   A Scalable Approach to Routing in ATM Networks ,
I. Cidon (IBM T.J. Watson, USA), O. Gerstel (Technion, Israel),
S. Zaks (Technion, Israel & Univ. Hong Kong, Hong Kong)

  14:30--15:00
   An Incremental Distributed Algorithm for Computing Biconnected
Components , B. Swaminathan (Washington Univ., USA),
K. Goldman (Washington Univ., USA)

  15:00--15:30
   Finding the Extrema of a Distributed Multiset ,
P. Alimonti (Univ. Roma, Italy), P. Flocchini (Univ. Milan, Italy),
N. Santoro (Carleton Univ., Canada)

  15.30--16.00
Break

    SESSION 8:  Friday, September 30, Afternoon
Chair:  Ozalp Babaoglu

  16.00--16.30
   The Level of a Handshake Required for Establishing a Connection ,
H. Attiya (Technion, Israel), R. Rappoport (Technion, Israel)

  16.30--17.00
   An Algorithm with Optimal Failure Locality for the Dining Philosophers
Problem , Y.K. Tsay (Uppsala Univ., Sweden),
R.L. Bagrodia (Univ. California, Los Angeles, USA)

    TOUR OF `DODEMANSKISTEN':   From 17:15 to 20.00.

    BANQUET:   Starting 20:00



    SESSION 9:  Saturday, October 1, Morning
Chair: Maurice Herlihy

  9.00--9.50
   Realization of PRAM's: Processor Design (Invited Lecture) ,
W.J. Paul (Univ. Saarlandes, Saarbruecken, Germany)

  9.50--10.20
   Cheaper Matrix Clocks , F. Ruget (Chorus Systems, France)

  10:20--10:50
Break


    SESSION 10:  Saterday, October 1, Morning
Chair:  Amos Israeli

  10.50--11.20
   Linear-Time Snapshot Using Multi-Writer Multi-Reader Registers ,
M. Inoue (Osaka Univ., Japan), W. Chen (Nagoya Inst. Techn., Japan),
T. Masuzawa (Nara Inst. Sciences Techn., Japan), N. Tokura (Osaka Univ., Japan)

  11.20--11.50
   Space-Optimum Conflict-Free Construction of 1-Writer 1-Reader
Multivalued Atomic Variable , S. Haldar (Tata Inst., India),
P.S. Subramanian (Tata Inst., India)

  11.50--12.20
   Breakpoints and Time in Distributed Systems ,
T. Basten (Eindhoven Univ. Techn., Netherlands)

    LUNCH:  Starting at 12:30.

    END OF WORKSHOP.