Livelocks in parallel programs

Abstract

This paper is the first of a two-part series exploring the subtle correctness criterion of the absence of livelocks in parallel programs. In this paper we formalize the underlying basic concepts. A classification of livelocks into two types according to their causes of formation is also introduced. In Part 2 we shall address the issue of proving the absence of livelocks.

Keywords:

• Parallel program
• deadlock
• livelock
• correctness
• verification

C.R. Categories:

• 4.3
• 5.24
• 6.9
• 8.1