In the DO-ALL problem, a set of t tasks must be performed by using a synchronous network of p processors. Processors may fail by permanent crashing. We investigate the time and the work complexity of F-reliable protocols for the DO-ALL problem on 1-hop wireless networks without collision detection. An F-reliable protocol is a protocol that guarantees the execution of all tasks if at most F < p faults happen during its execution. Previous results for this model are known only for the case F = p - 1. We obtain the following tight bounds. -The completion time of F-reliable protocols on 1-hop wireless networks without collision detection is Θ(t/(p-F) + min{(tF)/p, F + t~(1/2)}). -The work complexity of F-reliable protocols on 1-hop wireless networks without collision detection is Θ(t + F · min{t, F}). The two lower bounds hold even when the faults only happen at the very beginning of the protocol execution.
展开▼
