at-most-once semantics in asynchronous shared memory
This paper investigates the feasibility of implementing at-most-once access semantics in a model where a collection of actions is to be performed by failure-prone, asynchronous shared-memory processes. We introduce the At-Most-Once problem for performing a set of n jobs using m processors, and we define the notion of efficiency for such protocols, called effectiveness , that allows the classification of algorithms solving the problem. The effectiveness for an at-most-once implementation is the number of jobs safely completed by the implementation, expressed as a function of the number of jobs n , the number of processes m , and the number of process crashes f . We prove a lower bound of n -- f on the effectiveness of any algorithm. We then present two process solutions that offer a trade off between work and space complexity. Finally, we generalize a two-process solution for the multi-process setting using a hierarchical algorithm that achieves effectiveness of n --log m  o ( n ), coming reasonably close, asymptotically, to the corresponding lower bound.
at-most-once semantic shared memory