CODEWITHSUNDEEP
javamultithreadingfifoconsensus
Keaton Pennells
Keaton Pennells

Reputation: 199

Implementing a consensus protocol using a FIFO queue and peek() method

I need to implement a consensus protocol that makes use of a queue with a peek() method in order to show that a a consensus can be reached for any number of threads, i.e the queue with a peek() method has an infinite consensus number

This is my code

import java.util.LinkedList;
import java.util.Queue;
public class PeekConsensus extends ConsensusProtocol<Integer>   
{
    Queue<Integer> queue ;
    public PeekConsensus(int threadCount)   
    {
        super(threadCount); //threadCount is a command line argument from the main class specifying the number of threads to handle this process 
        queue = new LinkedList<Integer>() //FIFO queue
    }

    public Integer decide(Integer value)    
    {
        this.propose(value); // stores "value" in a vector named proposed, at index ThreadID.get()  
        int i = ThreadID.get() ;
        queue.add(i) 
        System.out.println("Thread " + i + " : " + i) ; // Required by specifications to print thread id and the value added when an item is enqueued 
        System.out.println("Thread " + i + " : " + queue.peek()) ; // Required by specifications to print thread id and the value of peek() when when peek() is called
        return proposed.elementAt(queue.peek()) ;

    }   
}

From my understanding this should work since if two threads return different values, peek() would of have to have returned different thread ids and validity is ensured because each thread writes its own value into proposed before pushing its thread id.

Is anybody able to figure where about i am going wrong and guide me in correcting my code

Upvotes: 3

Views: 1936

Answers (1)

jubueche
jubueche

Reputation: 793

The protocol looks fine to me. But have you thought about how peek() is implemented? Since peek() is really a pop() followed by a push() we can have bad interleavings in this code. This consensus protocol would work, assuming peek() can be performed atomically.

How can you change it?

Just so your code runs, you could add synchronized to peek(), but this would defeat the purpose of a consensus protocol since a thread could die, holding the lock.

Try using AtomicReference. This allows you to atomically get, even set, a value. In this case, the pointer would be head.

Now the question arises: How is AtomicReference implemented in Java. Unfortunately, it is implemented using a CAS, which again would defeat the purpose of a consensus protocol using only a FIFO queue.

At the end: Officially, FIFO queues have consensus number 2. Your protocol, assuming peek() is performed atomically, is valid. However, the correct implementation requires some sort of CAS or synchronized.

Upvotes: 3

Related Questions