Search

The problem is to let n processes concurrently and repeatedly search for free addresses in a range of m addresses. The search must be wait-free: a searching process finds an address in a bounded number of steps. Three solutions are presented. The first one has large atomic actions. The second one is only correct if m greater than or equal to (r + 1). n where r is the maximum number of used addresses. The third solution is always partially correct. It is wait-free if m > r + 2 . n. This solution has a worst-case waiting time quadratic in n and an amortized waiting time linear in n, even linear in the number of active processes.

Implementation of atomic actions in a distributed system in the presence of fail-stop failures is investigated. Worst case time and message complexities of the protocols realizing this are studied on complete graphs, rings, trees, and arbitrary graphs. Two modes of communication are considered — point-to-point and broadcast. Individual lower and upper bounds on time and messages are presented and the simultaneous achievability of the optimum message and time bounds is shown impossible in all the interesting cases.