Вполне себе возможно. Параллельность означает не то, что все потоки выполняются одновременно, а то, что мы не можем предсказать, как каждый поток будет выполняться относительно других потоков. Потому, для взаимодействия потоков необходимы специальные механизмы синхронизации. С точки зрения логики работы программы, потоки выполняются параллельно... А что там "под капотом": реальное раскидывание на несколько ядер, вытесняющая многозадачность с диспетчером, переключающим потоки, кооперативная многозадачность, основанная на неявных сопрограммах - это не важно. От этого зависит только скорость работы программы, но никак не её результат. P.S. Одна из самых известных книг по теории параллельных вычислений называется "Взаимодействующие последовательные процессы".