On the Possibility of Consensus in Asynchronous Systems with Finite Average Response Times Export

@inproceedings{citeulike:2755746, abstract = {It has long been known that the consensus problem cannot be solved deterministically in completely asynchronous distributed systems, i.e., systems (1) without assumptions on communication delays and relative speed of processes and (2) without access to real-time clocks. In this paper, we define a new asynchronous system model. Instead of assuming reliable channels with finite transmission delays, stubborn channels with a finite average response time was assumed (if neither the sender nor the receiver crashes), and it is assumed that there exists some unknown physical bound on how fast an integer can be incremented. Note that there is no limit on how slow a program can be executed or how fast other statements can be executed. Also, there exists no upper or lower bound on the transmission delay of messages or the relative speed of processes. The are no additional assumptions about clocks, failure detectors, etc. that would aid in solving consensus either. It is shown that consensus can nevertheless be solved deterministically in this asynchronous system model}, author = {Fetzer, C. and Schmid, U. and Susskraut, M.}, booktitle = {Distributed Computing Systems, 2005. ICDCS 2005. Proceedings. 25th IEEE International Conference on}, citeulike-article-id = {2755746}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/ICDCS.2005.57}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1437091}, citeulike-linkout-2 = {http://wwwse.inf.tu-dresden.de/index.php?language=English&site=publications&file=index}, doi = {10.1109/ICDCS.2005.57}, journal = {Distributed Computing Systems, 2005. ICDCS 2005. Proceedings. 25th IEEE International Conference on}, keywords = {2005, asynchronous, average, consensus, finite, model, possibility, response\_time, stubborn}, pages = {271--280}, posted-at = {2008-05-05 09:54:06}, priority = {0}, title = {On the Possibility of Consensus in Asynchronous Systems with Finite Average Response Times}, url = {http://dx.doi.org/10.1109/ICDCS.2005.57}, year = {2005} }

TY - CONF ID - citeulike:2755746 L3 - citeulike-article-id:2755746 N2 - It has long been known that the consensus problem cannot be solved deterministically in completely asynchronous distributed systems, i.e., systems (1) without assumptions on communication delays and relative speed of processes and (2) without access to real-time clocks. In this paper, we define a new asynchronous system model. Instead of assuming reliable channels with finite transmission delays, stubborn channels with a finite average response time was assumed (if neither the sender nor the receiver crashes), and it is assumed that there exists some unknown physical bound on how fast an integer can be incremented. Note that there is no limit on how slow a program can be executed or how fast other statements can be executed. Also, there exists no upper or lower bound on the transmission delay of messages or the relative speed of processes. The are no additional assumptions about clocks, failure detectors, etc. that would aid in solving consensus either. It is shown that consensus can nevertheless be solved deterministically in this asynchronous system model JF - Distributed Computing Systems, 2005. ICDCS 2005. Proceedings. 25th IEEE International Conference on EP - 280 TI - On the Possibility of Consensus in Asynchronous Systems with Finite Average Response Times T2 - Distributed Computing Systems, 2005. ICDCS 2005. Proceedings. 25th IEEE International Conference on SP - 271 KW - 2005 KW - asynchronous KW - average KW - consensus KW - finite KW - model KW - possibility KW - response_time KW - stubborn AU - Fetzer, C AU - Schmid, U AU - Susskraut, M PY - 2005/// UR - http://dx.doi.org/10.1109/ICDCS.2005.57 ER -