Correctness and Programming with Threads

Multi-core processors, common in modern embedded devices and computers, pose significant challenges to the programmer. Multi-threaded programs are increasingly common, hard to get right, and may fail tests non-deterministically. To deal with these challenges, developers use a variety of analysis tools to find concurrency bugs in multithreaded programs, and are even willing to add lightweight annotations.
But, what does correctness mean for multithreaded programs?