Paxos protokolünün sağlamlığı, quorum kesişimi ilkesine dayanır: iki farklı quorum her zaman en az bir ortak üye paylaşır. Bu ilke, görünürde basit bir kümeler kuramı önermesi olsa da dağıtık sistemlerin tutarlılık garantilerinin tamamını taşıyan temel kiriştir. Protokolün iki fazlı yapısında, Faz 1 (Prepare/Promise) ve Faz 2 (Accept/Accepted) aşamalarının her biri bağımsız quorum'lar üzerinden ilerler. Bir değerin seçilmiş (chosen) sayılabilmesi için Faz 2'de bir quorum'un `Accepted` mesajı göndermesi gerekir. Farklı teklif numaraları altında iki değerin aynı anda seçilmesinin imkânsız olduğu, quorum kesişiminin doğrudan sonucudur: her iki Faz 2 quorum'unun kesişimindeki herhangi bir sunucu çelişkili iki değeri kabul etmiş olmak zorunda kalır, bu ise protokolün Promise mekanizmasıyla engellenir. Paxos quorum boyutlandırması genellikle N/2 + 1 formülüyle ifade edilir; burada N toplam sunucu sayısıdır. Ancak bu klasik çoğunluk quorum'u, Byzantine hataları göz ardı eden bir crash-fault-tolerant (CFT) bağlamda geçerlidir. Byzantine hatalarının dahil edildiği senaryolarda quorum boyutu 2f + 1 (tolerans edilen hata sayısı f için) yerine 3f + 1 gerektirir ve bu değişiklik matematiksel temeli kökten dönüştürür. Paxos protokolünün iki fazlı yapısı, safety ile liveness arasında doğrudan bir gerilim barındırır. FLP teoremi gereği, tamamen asenkron bir ağda hem safety hem de liveness garantisi sunmak mümkün değildir. Paxos bu çelişkiyi safety'i önceliklendirerek çözer: quorum ulaşılamazsa protokol duraklar, yanlış bir değer seçmez. Multi-Paxos ve ardından gelen Raft bu duraksama problemini lider otoritesi ve heartbeat mekanizmalarıyla pratikte giderir, ancak teorik FLP sınırı ortadan kalkmaz.
