What are good (semi-) asynchronous algorithms?

Question

I am looking for some data parallel algorithms on data structures such as lists or graphs which do not use synchronisation but make use of critical sections in order to keep the states consistent.

So far I have only come across algorithms that are either

• synchronous: they work on local copies of the data that they change and at certain timeslots exchange their current state for the next step (e.g. single walk parallel local search), or are

• race-condition free: they subdivide the data structure such that each part can be handled seperately and safely with shared memory (e.g. parallel Quicksort)

Do you know any comprehensible (semi-) asynchronous algorithm which

1. subdivides the data that must be processed by multiple processors individually,
2. exchanges some of the data that is generated in each step by the processors via shared memory (e.g. by using critical sections) and is, thus,
3. only sychronized loosely but does not rely on a heart-beat scheme or other heavy-weight synchronization measure?

EDIT: I am using the terminology from the Technical Report Synchronized and asynchronous parallel algorithms for multiprocessors by H. T. Kung.

EDIT2: Just to clarify the terminology, the paper distinguishes different kinds of algorithms:

• synchronized (e.g. heart-beat approach for the game of life)
• asynchronous: Every processor can work mainly independently and may communicate it's results to other processors via shared memory at any time. The communication might then influence the next step of computation in the other processors (e.g. finding zero of a function in a monotonely converging interval via parallel binary search)
• semi-asynchronous/synchronized: Synchronization happens, but more rarely than in a synchronized algorithm.

Answer 1

Asynchronous: there are parallel versions of iterative algorithms like belief propagation and successive over-relaxation that, unlike Life, tolerate stale data and thus don't need a heartbeat. (Real implementations on systems that are not sequentially consistent might need a write barrier though.)

Semi-asychronous: pretty much every data structure with fine-grained locking. The usual idea is to lock only the part being worked on (e.g., for a binary search tree, lock the path from the root, probably with reader-writer locks).

Answer 2

I'm not sure if this qualifies as "on data structures such as lists or graphs," but parallel genetic algorithms maintain a shared pool of promising genes. A free processor takes one and executes a generation of evolution, placing superior results (and perhaps randomly selected inferior ones for genetic diversity) back in the pool.