-------------------------------------------------------------------------------
*******************************************************************************
-------------------------------------------------------------------------------
                                       
                                       
		   B O S T O N   U N I V E R S I T Y
                                       
		      Computer Science Department
                                       
			  C O L L O Q U I U M
                                       
			 Monday March 18, 1996
                                       
				10:30 am
                                       
		      (Coffee served at 10:00 am)

			 Seminar Room / MCS 135

-------------------------------------------------------------------------------
*******************************************************************************
-------------------------------------------------------------------------------

		Optimal Fault-Tolerant Sorting Networks

				Yuan Ma
	       Stanford University and Rutgers University

   Sorting networks have been intensively studied for several decades, and
   they have proved to be very useful for a variety of applications,
   including circuit switching and packet routing.  With the rapid advance
   of computer technologies, the study of the fault-tolerance properties of
   sorting networks has gained increasing importance since the presence of
   faulty elements is inevitable in any large system.

   In this talk, I will present optimal networks and parallel algorithms
   for sorting that work correctly even when each comparator/comparison
   is independently faulty with a constant probability. These results
   settle several long-standing open questions in the literature. Both
   theoretical and simulation results will be presented.

   Some of the results are joint work with Tom Leighton and Greg Plaxton.

-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
   For more information contact Prof. Mark Crovella <crovella@bu.edu>
-------------------------------------------------------------------------------