A Difference in Efficiency between Synchronous and Asynchronous Systems
Eshrat Arjomandi, Michael J. Fischer, Nancy Ann Lynch · 1981
A system of parallel processes is said to be synchronous if all processes run using the same clock, and it is asynchronous if each process has its own independent clock. For any s, n, a particular distributed problem is defined involving system behavior at n “ports”. This problem can be solved in time s by a synchronous system but requires time at least (s-1) log n on any asynchronous system.