The Byzantine Brides Problem - Sorbonne Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

The Byzantine Brides Problem

Résumé

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 et versions

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

Identifiants

Citer

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 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More