标题： 移位寄存器的共识数等于其宽度 显示英文标题

标题： The consensus number of a shift register equals its width

摘要： 一个支持逻辑左移和右移操作的 w 位寄存器的共识数正好是 w，这为实践广泛实现的一类类型提供了一个例子，这些类型填充了共识层次结构的所有级别。 这个结果推广到更大的字母表上的 w 宽移位寄存器。 相比之下，提供算术右移的寄存器（该操作复制最高有效位而不是将其替换为零）被证明可以解决固定数量进程的共识问题，只要其宽度至少为二。 显示英文摘要

摘要： The consensus number of a w-bit register supporting logical left shift and right shift operations is exactly w, giving an example of a class of types, widely implemented in practice, that populates all levels of the consensus hierarchy. This result generalizes to w-wide shift registers over larger alphabets. In contrast, a register providing arithmetic right shift, which replicates the most significant bit instead of replacing it with zero, is shown to solve consensus for any fixed number of processes as long as its width is at least two.