We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Fault-Tolerant Sequential Scan.
- Authors
Flocchini, Paola; Pelc, Andrzej; Santoro, Nicola
- Abstract
We consider the fault-tolerant version of the sequential scan problem. A line of identical cells has to be visited by a scanning head. The head can only distinguish an end of the line from an internal cell but can distinguish neither one end from the other, nor one internal cell from another. When the head starts at an internal cell, its first move is in a direction chosen by the adversary. When the head comes to an internal cell from a neighbor, it has two possible moves: forward, which means “go to the other neighbor”, and back which means “return to the previous neighbor”. At this point the adversary can place a fault whose effect is the change of the motion direction (going forward instead of back and vice-versa). The head is not aware of the occurrence of a fault. The execution cost of a sequential scan algorithm for a line of length n in the presence of at most k faults is the worst-case number of steps that the head must perform in order to scan the entire line. The worst case is taken over all adversary’s decisions. We consider two scenarios: when the length of the line is known to the algorithm and when it is unknown. Our goal is to construct sequential scan algorithms with minimum execution cost. We completely solve this problem for known line size. For any parameters k and n we construct a sequential scan algorithm, analyze its complexity and prove a matching lower bound, thus showing that our algorithm is optimal. The problem of fault-tolerant sequential scan for unknown line size is solved partially. For any parameter k we construct a sequential scan algorithm which explores a line of length n with cost 2 kn+ o( kn), for arbitrary n. For k=1 our algorithm is shown to be optimal. However, we also show an alternative algorithm that has cost at most O( kn) (with a constant larger than 2) for any n and cost kn+ o( kn) (which is asymptotically optimal) for infinitely many n. Hence the asymptotic performances of the two algorithms, for unbounded k and n, are incomparable.
- Subjects
COMPUTER systems; COMPUTABLE functions; SEQUENTIAL processing (Computer science); SEQUENTIAL analysis; ALGORITHMS; MATHEMATICAL optimization
- Publication
Theory of Computing Systems, 2009, Vol 45, Issue 1, p1
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-007-9065-y