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

Probabilistic Analysis of a 1-of-n Selection Algorithm using a Moderately Pessimistic Decision Criterion

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))
The 19th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC), Vancouver, British Columbia, Canada December 2-4, 2013. (1541-0110). (2013)
[Konferensbidrag, refereegranskat]

In this paper we are concerned with the fundamental problem of reaching agreement among a set of distributed processes in presence of an unbounded number of communication failures. We present a probabilistic analysis of a family of synchronous consensus algorithms that aim to solve the 1-ofn selection problem. In this problem, a set of n nodes are to select one common value among a set of n proposed values. There are two possible outcomes of each node's selection process: it can decide either to select a value, or to abort. Agreement implies that all nodes select the same value, or all nodes decide to abort. We know from previous research that it is impossible to guarantee agreement if there is no upper bound on the number of communication failures that can occur. Our aim is to study how the probability of disagreement varies for different decision criteria. The decision criterion consists of the logical expressions that determine whether a process will select a value or decide to abort based on its view of the system state. In this paper we propose and analyse a moderately pessimistic decision criterion. We compared this decision criterion with an optimistic and a pessimistic decision criterion, which we have investigated in our previous work. Our results show that the moderately pessimistic decision criterion for most configurations has a lower maximum probability of disagreement compared with the two other decision criteria. Furthermore, it provides a compromise between the optimistic and the pessimistic approaches since it reduces the probability of disagreement without increasing excessively the probability of agreeing to abort.

Nyckelord: communication failures; consensus; distributed algorithms; probabilistic analysis

Article number 6820842

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

Läs mer om Chalmers styrkeområden  

Denna post skapades 2013-12-12. Senast ändrad 2016-04-29.
CPL Pubid: 189060


Läs direkt!

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