O problema do Papai Noel é um problema clássico na computação, foi proposto por Trono [1994], tendo como paradigma a programação concorrente. O problema é basicamente composto por dez elfos, nove renas e pelo Papai Noel. A vida do Papai Noel se resume a dormir até que ele seja acordado pelas nove renas ou por um grupo de três elfos. Caso seja acordado pelas renas, o Papai Noel as amarra ao trenó, distribui brinquedos, desamarra-as e volta a dormir. Caso seja acordado pelos elfos, o Papai Noel discute projetos de brinquedos e volta a dormir. A vida de uma rena se resume a entregar presentes e tirar férias até o próximo ano. A vida de um elfo se resume a fabricar brinquedos e se reunir com o Papai Noel. Papai Noel dorme em sua casa no Polo Norte, e só pode ser despertado por 9 renas (todas), quando estão voltando de suas férias de alguma ilha tropical, ou por alguns elfos, que estão tendo dificuldades em fazer os brinquedos. O problema de um elfo nunca é grave o suficiente para acordar o Papai Noel (caso contrário, ele pode nunca conseguir dormir), então, os elfos visitam o Papai Noel em um grupo de três. Quando os três elfos tem seus problemas resolvidos, qualquer outro elfo que deseje visitar o Papai Noel deve esperar que os elfos retornem. Se o Papai Noel acordar e encontrar três elfos esperando na porta de sua loja, junto com a última rena voltando dos trópicos, o Papai Noel decide que os elfos podem esperar até depois do Natal, porque é mais importante preparar seu trenó assim que que possível. Supõe-se que as renas não querem deixar as férias, portanto, ficam lá até o último momento possível.