TY - GEN
T1 - On convergence of concurrent systems under regular interactions
AU - Prabhakar, Pavithra
AU - Mitra, Sayan
AU - Viswanathan, Mahesh
PY - 2009
Y1 - 2009
N2 - Convergence is often the key liveness property for distributed systems that interact with physical processes. Techniques for proving convergence (asymptotic stability) have been extensively studied by control theorists. In particular, for the asynchronous model of computation Tsitsiklis [8] provides a set of necessary and sufficient conditions for proving stability and convergence under the assumption that each asynchronous operator (state transition function) is applied infinitely often. This paper generalize these results to obtain necessary and sufficient conditions for systems where the infinite sequence of operators is a member of an arbitrary omega regular language. This enables us to apply our theory to distributed systems with changing communication topology, node failures and joins. We illustrate an application of the new set of conditions in verifying the convergence of a simple (continuous) consensus protocol.
AB - Convergence is often the key liveness property for distributed systems that interact with physical processes. Techniques for proving convergence (asymptotic stability) have been extensively studied by control theorists. In particular, for the asynchronous model of computation Tsitsiklis [8] provides a set of necessary and sufficient conditions for proving stability and convergence under the assumption that each asynchronous operator (state transition function) is applied infinitely often. This paper generalize these results to obtain necessary and sufficient conditions for systems where the infinite sequence of operators is a member of an arbitrary omega regular language. This enables us to apply our theory to distributed systems with changing communication topology, node failures and joins. We illustrate an application of the new set of conditions in verifying the convergence of a simple (continuous) consensus protocol.
UR - http://www.scopus.com/inward/record.url?scp=70349884043&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349884043&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-04081-8_35
DO - 10.1007/978-3-642-04081-8_35
M3 - Conference contribution
AN - SCOPUS:70349884043
SN - 3642040802
SN - 9783642040801
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 527
EP - 541
BT - CONCUR 2009 - Concurrency Theory - 20th International Conference, CONCUR 2009, Proceedings
T2 - 20th International Conference on Concurrency Theory, CONCUR 2009
Y2 - 1 September 2009 through 4 September 2009
ER -