Geodesic stability for memoryless binary long-lived consensus

Fernandes, Cristina G.; Stein, Maya

Advanced search

Search - Use quotation marks to get a more specific result

Index

Field of knowledge

Start date

Betweenand

(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Geodesic stability for memoryless binary long-lived consensus

Full text
Author(s):	Fernandes, Cristina G. ^[1] ; Stein, Maya ^[2] Total Authors: 2
Affiliation:	^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508 Sao Paulo - Brazil ^[2] Univ Chile, Ctr Modelamiento Matemat, Santiago - Chile Total Affiliations: 2
Document type:	Journal article
Source:	JOURNAL OF COMPUTER AND SYSTEM SCIENCES; v. 81, n. 7, p. 1210-1220, NOV 2015.
Web of Science Citations:	0
Abstract
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)

Short URL