The Byzantine Brides Problem

Abstract : 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.
Complete list of metadatas
Contributor : Sébastien Tixeuil <>
Submitted on : Tuesday, January 21, 2014 - 3:10:39 PM
Last modification on : Tuesday, May 14, 2019 - 10:14:49 AM

Links full text



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⟩



Record views