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)


the system can be imagined to be like this: System Image

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.

  • $\begingroup$ Welcome to CS.SE! We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Is there a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Oct 15 '15 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.