CALL  FOR  PARTICIPATION

            __________________________________________________

             SECOND WORKSHOP ON RANDOMIZED PARALLEL COMPUTING
            __________________________________________________

                   Held in conjunction with IPPS '97

                         University of Geneva 
                         Geneva, Switzerland
                        April 1, Tuesday 1997

                 sponsored by the IEEE Computer Society
                           Technical Committee
                          on Parallel Processing


                           TECHNICAL PROGRAM
                           _________________


   ********************************************************************
   * 9:10 - 10:10  INVITED TALK:                                      *
   *               Randomised Parallel Almost-Uniform Generation,     *
   *               PAUL SPIRAKIS, Univ. of Patras.                    *
   ********************************************************************


    10:10 - 10:40  BREAK

    10:40 - 11:10  Parallel Algorithms for Maximal Linear Forests,
                   R. Uehara (Tokyo Woman's Christian University) and
                   Z. Chen (UC Berkeley).

    11:10 - 11:40  Faster Finding of Simple Cycles in Planar Graphs on
                   a randomized EREW PRAM,
                   C. Dorgerloh and J. Wirtgen, Institut fur
                   Informatik V, Universitat Bonn.

    11:40 - 13:30  LUNCH BREAK


   ********************************************************************
   *13:30 - 14:30  INVITED TALK:                                      *
   *               Expected Behavior Analysis of Long Packet Routing  *
   *               in Interconnection Networks                        *
   *               LUDEK KUCERA, Department of Applied Mathematics,   *
   *                      Charles University, Prague and ENS, LYON.   *
   ********************************************************************


    14:30 - 15:00  BREAK

    15:00 - 15:30  A randomised parallel approach to synthesis based
                   constraint satisfaction,
                   S. Nagarajan and S. D. Goodwin, Univ. of Regina.

    15:30 - 16:00  Improved Static Multiprocessor Scheduling using
                   Cyclic Task Graphs: A Genetic Approach,
                   F.E. Sandnes and G.M. Megson, The Univ. of Reading.

    16:00 -        Open discussion


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

        Program Committee:

                Susanne E. Hambrusch, Purdue U
                Frank Hsu, Fordham U
                Oscar Ibarra, U of California, Santa Barbara
                Joseph Ja Ja, U of Maryland
                Danny Krizanc, Carleton U
                Tom Leighton, MIT
                Bruce Maggs, CMU
                Rajeev Motwani, Stanford U
                Michael Palis, Rutgers U
                Greg Plaxton, UT Austin
                Sanguthevar Rajasekaran, U Florida (Chair)
                Satish Rao, NEC
                John Reif, Duke U
                Sartaj Sahni, U Florida
                Paul Spirakis, U Patras
                Jeff Vitter, Duke U

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


	Abstract for Paul Spirakis's talk:
	----------------------------------

	We show here how to generate combinatorial objects almost
        uniformly efficiently in parallel  via a randomised
	technique. The technique uses a rapidly mixing Markov
        Chain which converges to  the  uniform distribution and
        shows how to produce  a special quadratic system which
        converges to the same distribution in a logarithmic number
        of population generations. We indicate applications to
        matchings and the permanent approximation of dense graphs.

        This is joint work with J. Diaz, M. Serna, S. Nikoletseas and
        P. Psycharis.
        --------------------------------------------------------------

	Abstract for Ludek Kucera's talk:
	---------------------------------

	The expected behavior of several types of routing algorithms
        is studied under an assumption that the packet length is
        comparable or larger than node-to-node distancies in the
        network and assuming a permanent routing process with random
        origins, destinations and starting times of packets.

	A simple formula is given for the average latency of oblivious
        algorithms, valid also for the case of variable packet length.

	A fenomenon that might cause a saturation of network using
        a simple deflection algorithm is described. It is shown how
        its apperance is connected to connectivity properties of the
        network and its failure-tolerance. Methods preventing this
        type of network saturation are studied.


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