Among key desirable features of a distributed system is the fault tolerance which is understood here as the ability to recover a system state after a random failure. In the article we introduce a multi-agent system (MAS) model, equipped with the mechanism increasing the reliability. The considered MAS operates on a distributed graph representation, namely on a slashed form of a graph, being the effective distributed graph model, which is additionally enhanced by fault-tolerance capabilities introduced for a MAS deployed on it.