This paper shows an asymptotically tight analysis of the Certified Write-All algorithm called AWT that was introduced by Anderson and Woll, SIAM J. Comput. 26 (1997) 1277, and a method for creating near-optimal instances of the algorithm. This algorithm is the best known deterministic algorithm that can be used to simulate n synchronous parallel processors on n asynchronous processors. The algorithm is instantiated with q permutations on {1,..., q}, where q can be chosen from a wide range of values. When implementing a simulation on a specific parallel system with n processors, one would like to select the best possible value of q and the best possible q permutations, in order to maximize the efficiency of the simulation.
展开▼
