The Byzantine Brides Problem - Sorbonne Université Access content directly
Conference Papers Year : 2012

The Byzantine Brides Problem


We investigate the hardness of establishing as many stable marriages (that is, marriages that last forever) in a population whose memory is placed in some arbitrary state with respect to the considered problem, and where traitors try to jeopardize the whole process by behaving in a harmful manner. On the negative side, we demonstrate that no solution that is completely insensitive to traitors can exist, and we propose a protocol for the problem that is optimal with respect to the traitor containment radius.

Dates and versions

hal-00934055 , version 1 (21-01-2014)



Swan Dubois, Sébastien Tixeuil, Nini Zhu. The Byzantine Brides Problem. FUN 2012 - 6th International Conference Fun with Algorithms, Jun 2012, Venice, Italy. pp.107-118, ⟨10.1007/978-3-642-30347-0_13⟩. ⟨hal-00934055⟩
282 View
0 Download



Gmail Facebook X LinkedIn More