使用FIFO队列和peek()方法实现共识协议

Question

我需要实现一个共识协议，利用一个带有peek()方法的队列来展示任意数量线程可以达成一致。即队列带有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()) ;

    }   
}

据我理解，这应该是有效的，因为如果两个线程返回不同的值，peek()必须返回不同的线程ID，并且确保有效性，因为每个线程在将其线程ID推入之前都会将自己的值写入proposed。

有人能否找出我的错误并指导我纠正代码？

- Keaton Pennells

---

我们首先需要知道它出了什么问题。 - ChiefTwoPencils

不清楚您遇到了什么错误，但一个可能的问题是LinkedList不是线程安全的。使用线程安全的Queue变体可能会有所帮助。 - Oliver Dain

将新的LinkedList更改为新的LinkedBlockingQueue()可能会让你达到一半以上的进展... - lscoughlin

Answer 1

这个协议在我看来没问题。但你有没有考虑过如何实现peek()？由于peek()实际上是一个pop()后面跟着一个push()，所以在这段代码中可能会出现糟糕的交错。

假设可以原子化地执行peek()，那么这个共识协议就可以正常工作。 怎样改进它？ 为了使你的代码运行，你可以在peek()上添加synchronized，但这将背离共识协议的目的，因为一个线程可能死亡，并持有锁。

尝试使用AtomicReference，这允许您原子化地获取甚至设置一个值。在这种情况下，指针将是head。

现在问题出现了：Java中如何实现AtomicReference。不幸的是，它是使用CAS实现的，这又将背离只使用FIFO队列的共识协议的目的。 最后：官方认为FIFO队列的共识数为2。假设可以原子化地执行peek()，则此协议有效。然而，正确的实现需要某种形式的CAS或synchronized。

- jubueche