Correct, robust and efficient concurrent computation

点击翻译按钮获取中文摘要

My research aims for correct, robust and efficient solutions to problems that arise from systems that use many processing components simultaneously.       Asynchronous shared memory architectures use elaborate hardware and software to speed computation.  Message-passing architectures are similarly complicated by a variety of message delivery services, which provide differing constraints on message ordering.  These mechanisms cause subtle, unexpected behaviour that can differ dramatically from what algorithm designers expect.  Thus, without using synchronization primitives, "natural" solutions to "simple" problems are not correct.  The catch is: the elaborate speed-enhancing mechanisms complicate the programming task to such a degree that programmers add excessive synchronization, which, in turn, slows down computation.  Thus, the speed-up advantages intended by special components can be entirely defeated!  A major focus of my research is to construct algorithms that are correct given only the weak guarantees that come with these systems, and that still exploit their speed.       An exciting application of my research is to the new and emerging multi- and many-core computers.  Even commodity desktop and laptop computers these days have "dual cores".  The near horizon promises "many-core" architectures that place possibly hundreds of different processing units on one chip.  Scientists' knowledge of how to program these machines correctly while exploiting their available concurrency is far behind their knowledge of how to build them.  My research aims to define the behaviour of these machines so that they are easier to program.     Even when individual components are very reliable, a failure somewhere in a large system is likely because there are so many components.  A related goal of my research is to design programs that continue to operate well in spite of some dead components, or that can automatically return our systems to correct behaviour after a burst of temporary faults.