Leader Election in the Timed Finite Average Response Time Model Export

@inproceedings{citeulike:2755725, abstract = {Leader election is one of the fundamental problems in distributed systems. A leader is a correct process that can be used to coordinate the work of a set of processes. An algorithm has to implement two properties to solve the leader election problem: (1) safety, (2) liveness. In this work we show that the stabilization property is not necessary for the leader election problem. We do this by examine the ability to solve leader election in the FAR model. The FAR model does neither assume the existence of an upper bound on the communication or computation delays nor that the system stabilizes. Instead it assumes that the system is in a certain balance: computation is not infinitely fast, the communication subsystem has rudimentary congestion control and the average response time between two correct processes is finite. Our contribution is twofold: (1) we show that leader election is not solvable in the pure FAR model and (2) that it becomes solvable with local clocks with a bounded drift rate}, author = {Fetzer, Christof and Subkraut, Martin}, booktitle = {Dependable Computing, 2006. PRDC '06. 12th Pacific Rim International Symposium on}, citeulike-article-id = {2755725}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/PRDC.2006.41}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4041926}, citeulike-linkout-2 = {http://wwwse.inf.tu-dresden.de/index.php?language=English&site=publications&file=index}, doi = {10.1109/PRDC.2006.41}, journal = {Dependable Computing, 2006. PRDC '06. 12th Pacific Rim International Symposium on}, keywords = {2007, average\_response\_time, election, leader, model, timed}, pages = {375--376}, posted-at = {2008-05-05 09:44:40}, priority = {0}, title = {Leader Election in the Timed Finite Average Response Time Model}, url = {http://dx.doi.org/10.1109/PRDC.2006.41}, year = {2006} }

TY - CONF ID - citeulike:2755725 L3 - citeulike-article-id:2755725 N2 - Leader election is one of the fundamental problems in distributed systems. A leader is a correct process that can be used to coordinate the work of a set of processes. An algorithm has to implement two properties to solve the leader election problem: (1) safety, (2) liveness. In this work we show that the stabilization property is not necessary for the leader election problem. We do this by examine the ability to solve leader election in the FAR model. The FAR model does neither assume the existence of an upper bound on the communication or computation delays nor that the system stabilizes. Instead it assumes that the system is in a certain balance: computation is not infinitely fast, the communication subsystem has rudimentary congestion control and the average response time between two correct processes is finite. Our contribution is twofold: (1) we show that leader election is not solvable in the pure FAR model and (2) that it becomes solvable with local clocks with a bounded drift rate JF - Dependable Computing, 2006. PRDC '06. 12th Pacific Rim International Symposium on EP - 376 TI - Leader Election in the Timed Finite Average Response Time Model T2 - Dependable Computing, 2006. PRDC '06. 12th Pacific Rim International Symposium on SP - 375 KW - 2007 KW - average_response_time KW - election KW - leader KW - model KW - timed AU - Fetzer, Christof AU - Subkraut, Martin PY - 2006/// UR - http://dx.doi.org/10.1109/PRDC.2006.41 ER -