In order to make a dependable distributed computer system resilient to arbitrary failures of its processors, deterministic interactive consistency algorithms (ICAs) are required. Thus far, in order to guarantee interactive consistency, all ICAs found in the literature require that all correct processors in the system start the algorithm simultaneously. In a distributed system, it is hard to satisfy this requirement. Therefore, in this paper, we describe a new class of self-synchronizing ICAs that guarantee interactive consistency without the above-mentioned requirement.