FIRST-CLASS SYNCHRONIZATION BARRIERS

Our purpose is to promote a second-class mechanism - the synchronizati on barrier - to a first-class value. We introduce the synchron, a nove l synchronization mechanism that enables the coordination of a dynamic ally varying set of concurrent threads that share access to a first-cl ass synchronization token. We demonstrate how synchrons can be used to modularly manage resources in cases where existing techniques are eit her inapplicable or non-modular. In particular, synchronized lazy aggr egates enable the first space-efficient aggregate data decomposition o f a wide range of algorithms. We also introduce explicit-demand graph reduction, a new semantic framework that we have developed to describe concurrency and explain the meaning of a synchron rendezvous.