CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

On probabilistic analysis of disagreement in synchronous consensus protocols

Negin Fathollah Nejad Asl (Institutionen för data- och informationsteknik, Datorteknik (Chalmers)) ; Emilia Villani ; Risat Mahmud Pathan (Institutionen för data- och informationsteknik, Datorteknik (Chalmers)) ; Raul Barbosa ; Johan Karlsson (Institutionen för data- och informationsteknik, Datorteknik (Chalmers))
10th European Dependable Computing Conference, EDCC 2014; Newcastle upon Tyne; United Kingdom; 13 May 2014 through 16 May 2014 p. 23-34. (2014)
[Konferensbidrag, refereegranskat]

This paper presents a probabilistic analysis of disagreement for a family of simple synchronous consensus algorithms aimed at solving the 1-of-n selection problem in presence of unrestricted communication failures. In this problem, a set of n nodes are to select one common value among n proposed values. There are two possible outcomes of each node's selection process: decide to select a value or abort. We have disagreement if some nodes select the same value while other nodes decide to abort. Previous research has shown that it is impossible to guarantee agreement among the nodes subjected to an unbounded number of message losses. Our aim is to find decision algorithms for which the probability of disagreement is as low as possible. In this paper, we investigate two different decision criteria, one optimistic and one pessimistic. We assume two communication failure models, symmetric and asymmetric. For symmetric communication failures, we present the closed-form expressions for the probability of disagreement. For asymmetric failures, we analyse the algorithm using a probabilistic model checking tool. Our results show that the choice of decision criterion significantly influences the probability of disagreement for the 1-of-n selection algorithm. The optimistic decision criterion shows a lower probability of disagreement compare to the pessimistic one when the probability of message loss is less than 30% to 70%. On the other hand, the optimistic decision criterion has in general a higher maximum probability of disagreement compared to the pessimistic criterion.

Nyckelord: consensus; distributed algorithms; reliability analysis; symmetric and asymmetric communication failures


Article number 6821085



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2014-01-26. Senast ändrad 2016-07-19.
CPL Pubid: 193078

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)