Modern supercomputers nowadays consist of millions of compute cores. This still growing number increases the likelihood of process failures, making fault tolerant programs essential, especially on clusters. Traditionally, fault tolerance is achieved with Checkpoint/Restart (C/R), where process states are periodically saved to disk, and a collective restart is performed after failure. This general-purpose approach is transparent to application programmers, but incurs a high running time overhead. The present paper, in contrast, deals with a specific fault tolerance technique for Asynchronous Many-Task (AMT) programs, called task-level checkpointing (TC). This technique is more efficient than C/R, and transparent to application programmers, as well. AMT programs divide the computation into tasks that are processed by worker processes running on, e.g., different cluster nodes. For load balancing, the workers often employ work stealing, in which idle workers steal tasks from other workers. TC operates in the runtime system and saves the data of clearly defined task interfaces instead of process states. So far, TC has only been applied to restricted classes of AMT runtimes, chiefly to runtimes with independent or nested fork-join tasks under cooperative work stealing, i.e., victims participate in steals. This paper adapts the technique to a runtime with task communication through futures under coordinated work stealing, i.e., thieves directly take data from victim memory. We present and evaluate first checkpointing algorithms for this setting, observing overheads of up to 12 % at 1280 workers.