Atomic-delayed execution: A concurrent programming model for incomplete graph-based computations

The sheer size of data sets from application domains such as biomedical and social networks will lead to the need to develop algorithms that have strict time bounds and can tolerate temporary unavailability of data if they are to produce acceptable results in feasible time. In this paper we describe a simple, yet powerful, object-based concurrent programming model that features atomicity, timed execution and tolerance to data unavailability. We describe the underlying concepts and illustrate their use in a sample computation on large graphs. This experience shows that it is possible to augment existing concurrent programming models to support developers in developing and reasoning about incomplete computations, we believe, will become, an increasingly important class of algorithms.