Empirical study of unstable leaders in Paxos

This thesis studies the effect of unstable leaders in Paxos protocol. Paxos algorithm is one of the most popular solutions for distributed consensus, and is often used for building replicated state machines. Safety is guaranteed by Paxos algorithm regardless of various machine and communication failures. However, the liveness is compromised when multiple Paxos leaders exist at the same time. Also, despite the extensive literature in the field, implementing Paxos algorithm for practical systems is still non-trivial. This thesis first studies the implications of multiple Paxos leaders in practical systems and provides an optimization by using leases. A complete specification of classical Paxos protocol is provided. We evaluate our implementation and show the effect of unstable leaders in practical systems.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2013

Author dc:creator

• Kai, Long

Contributors dc:contributor

• Vaidya, Nitin H.

• Reliability
• Experimentation

Statement dc:rights

• Copyright 2013 Long Kai

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/45621

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/45621