Artículo de revista
Geodesic stability for memoryless binary long-lived consensus
Fecha
2015Registro en:
Journal of Computer and System Sciences 81(2015) 1210–1220
DOI: 10.1016/j.jcss.2015.03.002
Autor
Fernandes, Cristina G.
Stein, Maya
Institución
Resumen
The determination of the (in-)stability of the long-lived consensus problem is a fundamental open problem in distributed systems. We concentrate on the memoryless binary case with geodesic paths. For this case, we offer a conjecture on the instability, measured by the parameter inst, exhibit two classes of colourings which attain the conjectured bound, and improve the known lower bounds for all colourings. We also introduce a related parameter, winst, which measures the stability only for certain geodesics, and for which we also prove lower bounds.