Title | ||
---|---|---|
Relating stabilizing timing assumptions to stabilizing failure detectors regarding solvability and efficiency |
Abstract | ||
---|---|---|
We investigate computational models with stabilizing properties. Such models include e.g. the partially synchronous model [Dwork et al. 1988], where after some unknown global stabilization time the system complies to bounds on computing speeds and message delays, or the asynchronous model augmented with unreliable failure detectors [Chandra et al. 1996], where after some unknown global stabilization time failure detectors stop making mistakes. Using algorithm transformations (a notion we introduce in this paper) we show that many (families of such) models are equivalent regarding solvability. We also analyze the efficiency of such transformations regarding not only the number of steps in a model M1 necessary to emulate a step in a model M2, but also the stabilization shift, which bounds the number of steps in M2 required to provide properties of M2 after the stabilization of M1. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-76627-8_4 | SSS |
Keywords | Field | DocType |
synchronous model,unreliable failure detector,algorithm transformation,unknown global stabilization time,asynchronous model,failure detector,stabilization shift,model m1,timing assumption,computational model,model m2,computer model | Asynchronous communication,Asynchronous system,Computer science,Algorithm,Computational model,Detector,Distributed computing | Conference |
Volume | ISSN | ISBN |
4838 | 0302-9743 | 3-540-76626-X |
Citations | PageRank | References |
4 | 0.38 | 22 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martin Biely | 1 | 98 | 9.12 |
Martin Hutle | 2 | 141 | 10.14 |
Lucia Draque Penso | 3 | 196 | 20.46 |
Josef Widder | 4 | 229 | 23.99 |