Processor assignment and execution sequence for multiversion software

Yiu Wing LEUNG*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)1371-1377
Number of pages7
JournalIEEE Transactions on Computers
Volume46
Issue number12
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'Processor assignment and execution sequence for multiversion software'. Together they form a unique fingerprint.

Cite this