Desired Attributes of an Algorithm
First and foremost the algorithm should be able to synchronize the type of network we are looking at for almost all (if not all) initial conditions. A good algorithm should be able to handle most upsets of the system: processor death, startup of processors not synchronized with the rest, processors losing or changing state randomly, etc. In general, if an algorithm can handle almost all initial conditions, it can handle these upsets. One of the stricter requirements is that the algorithm work in the face of lag. It is unrealistic to have instantaneous transmission & response times, and many algorithms fail without this assumption. This is the focus of my current work. The algorithm should also work quickly (preferably O(n^2) or less). We would like the algorithm's speed to be dependent on the diameter of the network rather than the number of nodes (it usually means it works much faster), and it would also be nice if it were something we could analyze, but these are obviously just wishes.
A Note On Lag
When including lag in a simulation, there are a few things to consider. With processing time on the receiving end, we can assume that as soon as a message is received it is timestamped, so that while a processor cannot respond immediately, it does know exactly when it received a message. It is important to keep in mind that we must wait for a message to finish sending, so that the transmission time may not only be due to the physical transmission of information but also the length of the message. Transmissions can also be timestamped by the transmitting processor so that we know exactly when a transmission was sent. If we know both the transmission and processing time, and we have the timestamps, we can sometimes account for these. In many situations, however, we cannot simply erase lag by doing this: you cannot simulate instantaneous interactions even with this knowledge, because a processor can never go back in time and spike.