Large parallel searches are now run on clusters for planning, model checking, and combinatorial optimization. Hash-distributed A (HDA) is the standard design: every search state has a fixed owner processor, chosen by hashing the state, and that owner alone keeps the state's entry in two lists. The open list holds states waiting to be expanded, and the closed list holds states already expanded, which lets the owner discard duplicates. These systems have no answer to a single crashed process. The dead worker's lists vanish, duplicate detection breaks, and the only remedy is to restart the whole run. We propose a recovery scheme built on one observation. Every state a worker owns either arrived as a message from another worker or was generated by the worker itself from states it owned. Senders can therefore keep, in RAM, a copy of every state they shipped across a partition boundary. That costs no extra network traffic, because the message is being sent anyway. After a crash, a replacement re-runs search only inside the dead partition, seeded from the logged boundary states. This rebuilds the lost open and closed lists exactly, and no survivor rolls back.
The idea borrows the "look sideways to your neighbors" principle from exact state reconstruction in linear solvers and from virtual-symbol repair in erasure-coded storage, and moves it into discrete graph search. The intersection matters for a specific reason. The method that made distributed search fast, abstraction-based hashing that keeps neighboring states on the same worker, is the same property that makes send logs small. The partitioning function therefore sets three costs at once: communication, load balance, and the price of recovery. Its unit of ownership, an abstract bucket, also turns out to be the right unit for moving work between processors without breaking duplicate detection.
Core Claim
In hash-partitioned best-first search, the lost state of a failed partition is the closure of its logged inbound boundary states under expansions that stay inside the partition. Replaying that closure has three properties. It restores exactly the open and closed lists the search would have had, so solution optimality is preserved. It costs roughly the expansions the dead worker had already done, not the whole run. It extends to concurrent failures with no extra stored data: the union of several dead partitions is simply a larger partition, seeded by the survivors' logs. The memory cost per worker is the number of states it has sent across boundaries. Under Abstract Zobrist Hashing that number equals the communication overhead fraction times the states generated, so a partition that is good for speed is automatically cheap to protect.
Relation to Prior Work
Two lines of work motivate the proposal by showing that sideways reconstruction beats global rollback. Pachajoa et al. store redundant search-direction vectors of the conjugate gradient solver in neighbors' RAM. They piggyback these copies on messages the solver already sends, and they rebuild a crashed node's iterate by solving a small local linear system. The related exactness result appears in Pachajoa et al.. CORE handles concurrent storage failures by treating some failed nodes as "virtual" survivors and solving for the symbols they would have supplied. We reuse two ideas from them: redundancy that rides on existing traffic, and treating concurrent failures as one larger reconstruction problem. Their mathematics, however, is linear algebra over fixed partitions. Our reconstruction operator is re-expansion over an irregular graph whose content depends on the heuristic.
SCAR constrains the design rather than supplying it. SCAR tolerates approximate recovery because an iterative optimizer contracts errors away. A* has no such contraction. A lost open-list state may lie on the only optimal path, so an approximate fill-in loses completeness rather than adding a small perturbation. Recovery here must be exact.
The search systems supply the setting. Abstract Zobrist Hashing maps each state to a coarser abstract state and hashes that, so most successors stay on the same worker. GRAZHDA* computes such projections automatically for planning by partitioning domain transition graphs. Hash-distributed beam search applies the same strict ownership to domain-independent dynamic programming. None of these has any recovery mechanism. The only fault-tolerant parallel combinatorial search in the file, Iamnitchi and Foster, recomputes missing subtrees from path codes. That works only for trees, where paths never reconverge, and it has no closed list to preserve. Our proposal differs from it in exactly those two respects.
Research Program
The system is built on AZHDA and GRAZHDA with abstract buckets numbering roughly 16 to 64 per worker. A small replicated routing table maps buckets to workers. Every cross-boundary message carries a state and its cost so far (its g-value), and the sender appends the message to a local send log indexed by destination bucket. Log entries for a bucket can be compacted to the best g-value seen per state, because only that value matters for replay.
When a worker fails, its buckets are reassigned across survivors by rewriting the routing table. We choose a spread across several survivors rather than a single spare, so that replay runs in parallel. Each new owner collects the log entries for its buckets from all survivors and inserts them as seeds. It then runs ordinary A* restricted to those buckets, expanding in f-order (f is the cost so far plus the heuristic estimate of remaining cost) up to the current global bound. After that it continues the normal search. Messages the replay emits toward survivors are already known there and are discarded by ordinary duplicate detection; sequence filtering can suppress them earlier. The initial state is treated as a permanent seed, so even total loss of a region degrades into a fresh restart of that region only.
We will prove three things. First, with a consistent heuristic, replay reproduces the dead partition's closed set at the global bound. Second, replay's expansions are bounded by the dead worker's expansions plus re-openings caused by out-of-order g-improvements. Third, concurrent failures are handled by replaying the union of dead buckets, provided at least one copy of each boundary message survives. When both endpoints of a message die, the message is regenerated inside the joint replay.
The same routing table supports load balancing. An overloaded worker hands an entire abstract bucket to an idle worker. It transfers that bucket's open and closed entries and forwards any stragglers sent under the old routing-table version. Because a whole bucket moves, the rule that one owner holds every copy of a state still holds. This addresses the conflict between work stealing and duplicate detection identified in the file. The beam-search variant applies replay layer by layer, where only the current layer needs rebuilding.
Baselines
The naive reference point is unmodified AZHDA or GRAZHDA that restarts from scratch on any failure. Its failure-free speed is the ceiling we must approach. The file reports AZHDA at a 7.8x speedup on 8 cores on the 24-puzzle versus 5.9x for ZHDA, and an average efficiency of 0.797 with 282.29s total wall-clock on PDDL planning (Abstract Zobrist Hashing). For beam search, Kuroiwa and Beck report average speedups of 9x to 39x on 32 threads. We reproduce these configurations and count failure-free slowdown against our own reruns.
The strongest competitor is buddy replication. Each owner forwards every state it inserts to a fixed backup worker, in the style of the successor-backup schemes of Wang et al., so a failure is absorbed instantly by promoting the backup. It is the right threat because its recovery time is near zero. It is run on the same partitions, cores, and memory caps.
We also run coordinated checkpoint/restart of all lists to shared storage, tuned over checkpoint intervals with the same tuning budget we give our log compaction. For a tree-search domain we include an Iamnitchi–Foster-style recompute-from-root-code baseline.
There is no reported result on Lacuna for any fault-tolerant HDA*-family system. The relevant prior figure is the roughly 15.6% fault-tolerance and load-balancing overhead reported by Iamnitchi and Foster for tree search in simulation.
Two ablations isolate the key ingredients. The first applies send logging on top of uniform Zobrist hashing. Its log should approach full replication in memory, which would show that abstraction is what makes logging cheap. The second disables bucket migration, which isolates the load-balancing contribution.
Beating the strongest baseline means three things together. Total time to an optimal solution under a realistic failure rate must be lower than buddy replication's. Failure-free overhead must be within a few percent of plain AZHDA*. Peak memory must be clearly below replication's, so that larger instances become solvable.
Why not just…?
Why not just replicate every state to a buddy worker? This is the real threat, and the experiments are built to settle it. Replication must copy every inserted state, including the many that AZH keeps local. It therefore adds network traffic roughly equal to all generated states, which erases the locality that made AZH faster than ZHDA*. It also roughly halves usable memory in a memory-bound search. Send logs add no traffic and store only boundary crossings. Replication wins if failures are frequent enough that replay time dominates. We measure the crossover failure rate directly, and if it sits within realistic cluster failure rates we will report that replication is preferable there.
Why not just checkpoint to shared storage? Pachajoa et al. and Su et al. both show global checkpointing is costly. The SCAR study reports that traditional checkpointing lost 7 epochs of work, against less than one epoch for partial recovery. Search lists grow to many gigabytes, and a cluster-wide barrier to flush them stalls every worker. The tuned checkpoint baseline will show whether that intuition holds for search.
Why not just recompute the dead worker's subproblems from scratch, as Iamnitchi and Foster do? In graph search there is no self-contained subproblem to recompute. A dead partition's states were reached through many other partitions, and recomputing without their boundary messages means re-searching from the initial state. The tree-domain comparison measures how much of the advantage survives even where path codes do apply.
Why not just drop the lost states and keep going? Losing a closed list only causes redundant work. Losing an open list can discard the optimal path, so the search returns a wrong answer or stops early. We include this variant to measure how often optimality actually breaks.
Proposed Experiments
The testbeds are the 15- and 24-puzzle, multiple sequence alignment, grid pathfinding, and the IPC domains used by GRAZHDA*, run on 8- to 128-core clusters as in Jinnai and Fukunaga. They also include the six dynamic-programming domains of Kuroiwa and Beck on 32 threads.
We inject process kills at uniformly random times, covering single failures, 2 to 8 concurrent failures, and correlated failures of logically adjacent workers. We measure failure-free slowdown, peak log memory as a fraction of state memory, recovery expansions relative to the dead worker's expansions, wall-clock time to an optimal solution, and solution cost against sequential A*.
The decisive checks are these. Solution cost must always match the optimum. Recovery expansions should track the dead workers' share of the work, not the global total. Log memory should scale with each partition's measured communication overhead, and should be clearly larger under uniform hashing than under AZH. Concurrent failures must recover with no stored data beyond the single-failure logs. Bucket migration should reduce idle time on skewed instances without increasing duplicate expansions.
If grid pathfinding, where expansion is fast and boundary traffic heavy, shows that log memory approaches replication's, that delimits where the method applies. It does not refute the method.
References
- How to Make the Preconditioned Conjugate Gradient Method Resilient Against Multiple Node Failures
- Algorithm-Based Checkpoint-Recovery for the Conjugate Gradient Method
- CORE: Augmenting regenerating-coding-based recovery for single and concurrent failures in distributed storage systems
- Fault Tolerance in Iterative-Convergent Machine Learning
- Abstract Zobrist Hashing: An Efficient Work Distribution Method for Parallel Best-First Search
- On Hash-Based Work Distribution Methods for Parallel Best-First Search
- Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming
- A Problem-Specific Fault-Tolerance Mechanism for Asynchronous, Distributed Systems
- ScalaRDF: A Distributed, Elastic and Scalable In-Memory RDF Triple Store