I had a test today, there was a question that was a bit confusing. Anyway I am asking the question, from memory, and explaining what I answered. It would be great if someone could explain if I did answer it correctly or not.
The question is that assume a ring of 6 processes in an asynchronous system(each process runs the code as soon the as the conditions of its code becomes true). Each of these processes have a number x. The number's value is changed based on an algorithm as such:
Do if there exists a neighbor of process i whose value X value is less than process i's X value, then skip the loop For all process i's neighbors, if process i's X value is less than it's neighbors X value plus one (X+1) then process i's X = X + 1(increment one)
So basically my answer was that the maximum difference can be 1. Because every process needs to check two neighbors and based on the first condition, it cannot increment if it is bigger than it's neighbors. Suppose they all start from one, and process 0 checks process 1's X value. Since its also zero, then the second condition will be true and it will increment and become 1. it will check process 5. Suppose by now process 5 has run the same program and become 1. Since value of process 5 is 1 process 1 will increment its value by one, and becomes 2. But after it becomes two, it will check process 1. if it was still one, then the first condition is true and it will not increment. if it wasn't then it will become 3. But if this becomes three then process 5, will run the code and become 2. So in no condition the difference will be more than 1. This scenario can be extended to all six values.
Now what I am not sure is if my assumptions are true. Since it's an asynchronous system, is it possible that on of the processes, and it's neighbors will keep adding it's value of X while some other process remains zero? I doubt that, since based on the algorithm, it seems that the will at most add 2 value to its X, but not more than that.