An Analysis of Rollback-Based Simulation
| dc.contributor.author | Lubachevsky, Boris D. | en_US |
| dc.contributor.author | Shwartz, A. | en_US |
| dc.contributor.author | Weiss, A. | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T09:47:49Z | |
| dc.date.available | 2007-05-23T09:47:49Z | |
| dc.date.issued | 1991 | en_US |
| dc.description.abstract | We present and analyze a general model of rollback in parallel processing. The analysis points out three possible modes where rollback may become excessive; we provide an example of each type. We identify the parameters which determine a stability, or efficiency region for the simulation. Our analysis suggests the possibility of a dangerous "phase-transition" from stability to instability in the parameter space. In particular, a rollback algorithm may work efficiently for a small system but become inefficient for a large system. Moreover, for a given system, it may work quickly for a while and then suddely slow down.<P>On the positive side, we give a tunable algorithm, Filtered Rollback, that is designed to avoid the failure modes. Under appropriate assumptions, we provide a rigorous mathematical proof that Filtered Rollback is efficient, if implemented on a reasonably efficient multiprocessor. In particular: we show that the average time t to complete the simulation of a system with N nodes and R events on a p -processor PRAM satisfies t = 0 ((R/p) + (R/N) log p).<P>The analysis is based on recent work by the authors on Branching Random Walks with a barrier. | en_US |
| dc.format.extent | 2219674 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/5085 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1991-37 | en_US |
| dc.subject | time warp | en_US |
| dc.subject | efficiency of algorithms discrete-event simulation | en_US |
| dc.subject | branching random walks | en_US |
| dc.subject | Communication | en_US |
| dc.subject | Signal Processing Systems | en_US |
| dc.title | An Analysis of Rollback-Based Simulation | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1