Abstract
Consider the problem of assigning N software versions of a multiversion software to M processors for execution. When a processor completes executing a software version, it sends the output to a voter immediately. The voter executes a voting strategy to estimate the correct output. When it has made a sufficiently reliable estimation (e.g., it has received ⌈(N/2)⌉ identical outputs under majority voting), it accepts this estimated output and terminates the execution of all the unfinished versions. Therefore, some software versions may not be executed to completion. In this paper, we analyze the mean time to reach correct consensus for four voting strategies. To minimize the mean time to reach correct consensus, we show that the processor assignment problem is NP-hard and we propose a heuristic to find suboptimal assignments. When two or more versions are assigned to a processor, these versions are executed one after the other and we derive the optimal execution sequence for them.
Original language | English |
---|---|
Pages (from-to) | 1371-1377 |
Number of pages | 7 |
Journal | IEEE Transactions on Computers |
Volume | 46 |
Issue number | 12 |
DOIs | |
Publication status | Published - Dec 1997 |
Scopus Subject Areas
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics
User-Defined Keywords
- Execution sequence
- Fault-tolerance
- Multiversion software
- Processor assignment
- Reliability
- Voting