Abstract
A snapshot of systems during their computation is useful for global state detection problems such as detecting system's stable property or taking a global state for efficient backward recovery. A replay of a system during its computation is a recovery of the system state to a desirable global state recorded in a snapshot. The combination of snapshot and replay protocols yields a mechanism for fault-tolerant applications or interactive distributed debugger. In this thesis, the lower bounds of snapshot and replay problems are derived. Also, we provide a snapshot protocol for non-FIFO systems. without recording the complete message history of each node and provide a message-optimal replay protocol for FIFO systems.