Cyclic debugging executes a program over and over track down bugs. However, for message-passing parallel programs, nondeterminacy makes cyclic debugging impossible executins, messsages must be traced for later replay. SIce parallel programs are long-running, providing fast response to debuggin gqueries requires incremental replay, whrere reexecution is started from intermediate states instead of from the beginning. To support incremental replay, processes must be chekpointed priodically and the contents of some messages traced, but the time and space cost of saving these messages longing algorithm hat kepps these costs low by logging only a fractio of the messages. Our algorithm dynamically tracks dependeces among messages to termne which caouse domino effects and mus be traced. THe domino effect can force a replay to start arbitrarily far back in the execution, and somino-free replay allows any part of the execution to be quickly reexecuted. experiments on an iPSC/860 hypercube indicate that our algorithm logs only 1-10% of the messages, a 1 to 2 order of magnitude reduction to be quickly reexecution needed to satisfy any request. Our new logging algorithm thus reduces the overhead of message logging shile bounding the response time to replay requests.