Vi anser den feltoleranta versionen av det sekventiella avsökningsproblemet. En rad identiska celler måste besökas av ett skannande huvud. Huvudet kan endast skilja en ände av linjen från en inre cell, men kan skilja varken den ena änden från den andra eller den ena inre cellen från den andra. När huvudet börjar vid en inre cell, dess första drag är i en riktning som väljs av motståndaren. När huvudet kommer till en inre cell från en granne, har det två möjliga drag: framåt, vilket betyder "gå till den andra grannen", och tillbaka som betyder "återvänd till den föregående grannen". Vid denna punkt motståndaren kan placera ett fel vars effekt är förändringen av rörelseriktningen (gå framåt i stället för bakåt och vice versa). Huvudet är inte medvetet om förekomsten av ett fel. Exekveringskostnaden för en sekventiell avsökningsalgoritm för en linje av längd n i närvaro av de flesta k-fel är det värsta antalet steg som huvudet måste utföra för att skanna hela raden. Det värsta fallet tas över alla motståndares beslut. Vi överväger två scenarier: när längden på linjen är känd för algoritmen och när den är okänd. Vårt mål är att konstruera sekventiella scan algoritmer med minsta möjliga utförandekostnad. Vi löser problemet helt och hållet för den kända linjestorleken. För alla parametrar k och n konstruerar vi en sekventiell scan algoritm, analyserar dess komplexitet och visar en matchande lägre gräns, vilket visar att vår algoritm är optimal. Problemet med feltolerant sekventiell scanning för okänd linjestorlek är delvis löst. För varje parameter k konstruerar vi en sekventiell scan algoritm som utforskar en linje av längd n med kostnad 2kn + o(kn), för godtycklig n. För k = 1 vår algoritm visas vara optimal. Men vi visar också en alternativ algoritm som har kostat högst O(kn) (med en konstant större än 2) för någon n och kostnad kn + o(kn) (som är asymptotiskt optimal) för oändligt många n. Därför är asymptotiska föreställningar av de två algoritmerna, för obundna k och n, ojämförbara.
En annan aspekt av feltolerant undersökning studerades i REF.
Fault-Tolerant Sequential Scan
{'venue': 'Theory of Computing Systems', 'journal': 'Theory of Computing Systems', 'mag_field_of_study': ['Mathematics', 'Computer Science']}