This article is on k-set agreement (kSA) in an n-process synchronous message-passing system in which up to t processes can commit Byzantine failures. kSA is a decision problem in which at least each correct (i.e., non...
详细信息
This article is on k-set agreement (kSA) in an n-process synchronous message-passing system in which up to t processes can commit Byzantine failures. kSA is a decision problem in which at least each correct (i.e., non-Byzantine) process is assumed to propose and decide a value such that at most k different values are decided by the correct processes, in such a way that, if all the correct processes propose the same value v, they will decide v. This article investigates the possibility/impossibility domain of kSA in the presence of Byzantine processes. To this end it first extends a previous result and shows that kSA cannot be solved when (n < 2t + t/k) boolean AND (n - t >= k + 1). On the positive side, it presents two synchronous round-based algorithms that solve Byzantine kSA. These algorithms are optimal with respect to the value of k and the number of rounds. The first algorithm is a one-roundalgorithm that has two instances. The first assumes n > 2t + 1 and solves kSA for k >= [ n-t n-2t ] + 1, while the second assumes n <= 2t + 1 and solves kSA for k >= t +1 (so this second case does not require a majority of correct processes). The second algorithm is based on two new notions denoted Square and Regions that allow each correct process to locally build a global knowledge on which processes proposed which values. This algorithm has also two instances. The first assumes n = 3t and solves 2SA. The second assumes 2t + 1 < n <= 3t and solves kSA where k = n-t n-2t is an integer. It is worth noticing that the results presented in this article "almost" complete the possibility/impossibility cartography of kSA in synchronous Byzantine systems. The only case that remains open is when (n-t)/n-2t is not an integer.
The k-set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a Value such that a decided value is a proposed value. and at ...
详细信息
The k-set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a Value such that a decided value is a proposed value. and at most k different Values are decided. It has been shown that any algorithm that solves the k-set agreement problem in synchronous systems that can suffer up to t crash failures requires left perpendicular1/kright perpendicular rounds in the worst case. It has also been shown that it is possible to design early deciding algorithms where no process decides and halts after min (left perpendicular f/k right perpendicular + 2, left perpendicular t/k right perpendicular + 1) rounds, where f is the number of actual crashes in a run (0 <= f <= t). This paper explores a new direction to solve the k-set agreement problem in a synchronous system. It considers that the system is enriched with base objects (denoted has left perpendicular m, l right perpendicular_SA objects) that allow solving the l-set agreement problem in a set of m processes (m < n). The paper makes several contributions. it first proposes a synchronous k-set agreement algorithm that benefits from such underlying base objects. This algorithm requires O(tl/mk) rounds, more precisely, left perpendicular t/Delta right perpendicular + 1 rounds, where Delta = m left perpendicular k/l right perpendicular + (k mod l). The paper then shows that this bound, that involves all the parameters that characterize both the problem (k) and its environment (t, m and e), is a lower bound. The proof of this lower bound sheds additional light on the deep connection between synchronous efficiency and asynchronous Computability. Finally, the paper extends its investigation to the early deciding case. It presents a k-set agreement algorithm that directs the processes to decide and stop by round min (left perpendicular f/Delta right perpendicular + 2, left perpendicular t/Delta right perpendicular + 1). These bounds genera
We introduce the notion of a swift algorithm. Informally, an algorithm that solves the repeated consensus is swift if, in a partial synchronous run of this algorithm, eventually no timeout expires, i.e., the algorithm...
详细信息
ISBN:
(纸本)9780769542508
We introduce the notion of a swift algorithm. Informally, an algorithm that solves the repeated consensus is swift if, in a partial synchronous run of this algorithm, eventually no timeout expires, i.e., the algorithm execution proceeds with the actual speed of the system. This definition differs from other efficiency criteria for partial synchronous systems. Furthermore, we show that the notion of swiftness explains why failure detector basedalgorithms are typically more efficient than round-based algorithms, since the former are naturally swift while the latter are naturally non-swift. We show that this is not an inherent difference between the models, and provide a round implementation that is swift, therefore performing similarly to failure detector algorithms while maintaining the advantages of the round model.
暂无评论