A parallel computer system comprising a plurality of nodes and synchronization apparatuses (6, 8) configured to perform barrier synchronization using an algorithm which divides parallel processing into a plurality of stages, each stage including communication of a synchronization message between a pair of nodes, each synchronization message comprising data including synchronization information indicating that synchronization is established, each of the plurality of nodes being provided with one of the plurality of synchronization apparatuses (6, 8), each of the plurality of synchronization apparatuses (6, 8) comprising: a receiving unit (61, 81) configured to: receive a first synchronization message of a previous stage of the parallel processing for synchronizing a current stage of the parallel processing from the synchronization apparatus (6, 8) of another, source node, and extract the synchronization information from the first synchronization message; a control unit (621, 821); a delay unit (624, 824); a receiving state register (622, 822) configured to store the extracted synchronization information and synchronization information of the control unit (621, 821), the synchronization information of the control unit (621, 821) being from a second synchronization message of the previous stage of the parallel processing returned by the control unit (621, 821) via the delay unit (624, 824) for synchronizing the current stage of the parallel processing; and a transmitting unit (63, 83) configured to transmit a third synchronization message for synchronizing a next stage of the parallel processing to the synchronization apparatus (6, 8) of another, destination node different from the source node; wherein the control unit (621, 821) is configured to: store the extracted synchronization information and the synchronization information of the control unit (621, 821) in the receiving state register (622, 822), and when the extracted synchronization information and the synchronization information of the control unit (621, 821) are both stored in the receiving state register (622, 822), return a fourth synchronization message for synchronizing the next stage of the parallel processing back to the control unit (621, 821) via the delay unit (624, 824) and cause the transmitting unit (63, 83) to transmit the third synchronization message to the destination node, and wherein the delay unit (624, 824) is configured to delay the return of the fourth synchronization message by a specified period of time which is substantially equal to a period of time required for the third synchronization message to be transmitted to the destination node. a receiving unit (61, 81) configured to: receive a first synchronization message of a previous stage of the parallel processing for synchronizing a current stage of the parallel processing from the synchronization apparatus (6, 8) of another, source node, and extract the synchronization information from the first synchronization message; receive a first synchronization message of a previous stage of the parallel processing for synchronizing a current stage of the parallel processing from the synchronization apparatus (6, 8) of another, source node, and extract the synchronization information from the first synchronization message; a control unit (621, 821); a delay unit (624, 824); a receiving state register (622, 822) configured to store the extracted synchronization information and synchronization information of the control unit (621, 821), the synchronization information of the control unit (621, 821) being from a second synchronization message of the previous stage of the parallel processing returned by the control unit (621, 821) via the delay unit (624, 824) for synchronizing the current stage of the parallel processing; and a transmitting unit (63, 83) configured to transmit a third synchronization message for synchronizing a next stage of the parallel processing to the synchronization apparatus (6, 8) of another, destination node different from the source node; wherein the control unit (621, 821) is configured to: store the extracted synchronization information and the synchronization information of the control unit (621, 821) in the receiving state register (622, 822), and when the extracted synchronization information and the synchronization information of the control unit (621, 821) are both stored in the receiving state register (622, 822), return a fourth synchronization message for synchronizing the next stage of the parallel processing back to the control unit (621, 821) via the delay unit (624, 824) and cause the transmitting unit (63, 83) to transmit the third synchronization message to the destination node, and store the extracted synchronization information and the synchronization information of the control unit (621, 821) in the receiving state register (622, 822), and when the extracted synchronization information and the synchronization information of the control unit (621, 821) are both stored in the receiving state register (622, 822), return a fourth synchronization message for synchronizing the next stage of the parallel processing back to the control unit (621, 821) via the delay unit (624, 824) and cause the transmitting unit (63, 83) to transmit the third synchronization message to the destination node, and wherein the delay unit (624, 824) is configured to delay the return of the fourth synchronization message by a specified period of time which is substantially equal to a period of time required for the third synchronization message to be transmitted to the destination node.