Реализация консенсусного протокола с использованием очереди FIFO и метода peek()

Question

Мне нужно реализовать консенсусный протокол, который использует очередь с методом peek(), чтобы показать, что можно достичь консенсуса для любого количества потоков , то есть очереди с методом быстрого взгляда() имеет бесконечное консенсусное число

Это мой код

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()) ; 

    } 
} 

в моем понимании это должно работать, так как если два поток возвращают разные значения, заглядывать() будет от того, чтобы возвратить различные идентификаторы потоков, и действительность гарантирована, потому что каждый поток записывает свое собственное значение в предложение, прежде чем нажимать свой идентификатор потока.

ли кто-нибудь в состоянии понять, где о я буду неправильно и вести меня в исправлении моего кода

Answer 1

Протокол выглядит хорошо для меня. Но вы подумали о том, как реализован peek()? С peek() действительно pop(), за которым следует push(), у нас могут быть плохие интермедии в этом коде. Этот консенсусный протокол будет работать, предполагая, что peek() может выполняться атомарно.

Как вы можете изменить?

Просто так что ваш код работает, вы можете добавить synchronized к peek(), но это было бы поражение цели протокола консенсуса, так как поток может умереть, держа замок.

Попробуйте использовать AtomicReference. Это позволяет атомарно получать, даже задавать значение. В этом случае указатель будет head.

Возникает вопрос: как работает AtomicReference на Java. К сожалению, он реализован с использованием CAS, что снова победит цель консенсусного протокола, используя только очередь FIFO.

В конце: Официально очереди FIFO имеют консенсусный номер 2. Ваш протокол, если peek() выполняется атомарно, действителен. Однако правильная реализация требует своего рода CAS или synchronized.