Geodesic stability for memoryless binary long-lived consensus

Autor(es)

Fernandes, Cristina G. ^[1] ; Stein, Maya ^[2]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508 Sao Paulo - Brazil

^[2] Univ Chile, Ctr Modelamiento Matemat, Santiago - Chile

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMPUTER AND SYSTEM SCIENCES; v. 81, n. 7, p. 1210-1220, NOV 2015.
• Citações Web of Science: 0

Resumo

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. (C) 2015 Elsevier Inc. All rights reserved. (AU)

• Processo FAPESP: 05/54051-9 - Problemas finitos e infinitos da teoria dos grafos e hipergrafos.
• Beneficiário: Maya Jakobine Stein
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado