loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
25th IEEE International Conference on Distributed Computing Systems (ICDCS'05)
On the Possibility of Consensus in Asynchronous Systems with Finite Average Response Times
Columbus, Ohio, USA
June 06-June 10
ISBN: 0-7695-2331-5
Christof Fetzer, Technical University of Dresden
Ulrich Schmid, Technical University of Wien
Martin S?sskraut, Technical University of Dresden
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 paper1 we define a new asynchronous system model: Instead of assuming reliable channelswith finite transmission delays, we assume stubborn channels with a finite average response time (if neither the sender nor the receiver crashes), and we assume 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. We show that consensus can nevertheless be solved deterministically in this asynchronous system model.
Index Terms:
impossibility, consensus, asynchronous systems, eventually perfect failure detector
Citation:
Christof Fetzer, Ulrich Schmid, Martin S?sskraut, "On the Possibility of Consensus in Asynchronous Systems with Finite Average Response Times," icdcs, pp.271-280, 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.