Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Renaming and the weakest family of failure detectors

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

We address the question of the weakest failure detector to circumvent the impossibility of \((2n-2)\)-renaming in a system of up to \(n\) participating processes. We derive that in a restricted class of eventual failure detectors there does not exist a single weakest oracle, but a weakest family of oracles \(\zeta _n\): every two oracles in \(\zeta _n\) are incomparable, and every oracle that allows for solving renaming provides at least as much information about failures as one of the oracles in \(\zeta _n\). As a by product, we obtain one more evidence that renaming is strictly easier to solve than set agreement.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. In the \(k\)-set consensus task (\(k\)-SC), the processes start with private inputs and produce outputs so that the set of output values is a subset of the set of inputs of size at most \(k\). In \(\mathcal E ^n\), we say simply set consensus (SC) for \((n-1)\)-set consensus.

  2. We slightly reformulate the properties of [30] to match our definitions. Specifically, property Z3 is rewritten to conform with the standard failure detector formalism [11].

  3. However its value is bounded between \(\nu ={{m \atopwithdelims ()2n-1}}/{{m-n \atopwithdelims ()(2n-1)-n}}={{m \atopwithdelims ()n}}/ {{2n-1 \atopwithdelims ()n}}\), which is the number of sets of size \(2n-1\) divided by the number of sets of this size covered by each \(\zeta \), and \(\nu \cdot \left[1+ln\left({m-n \atopwithdelims ()m-(2n-1)}\right)\right]\) due to [26].

References

  1. Afek, Y., Nir, I.: Failure detectors in loosely named systems. In: PODC, pp. 65–74 (2008)

  2. Attiya, H., Bar-Noy, B., Dolev, D., Peleg, D., Reischuk, R., et al.: Renaming in an asynchronous environment. J. ACM 37(3), 524–548 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  3. Attiya, H., Fouren, A.: Polynomial and adaptive long-lived (2k–1) renaming. In: DISC, pp. 149–163 (2000)

  4. Attiya, H., Rajsbaum, S.: The combinatorial structure of wait-free solvable tasks. SIAM J. Comput. 31(4), 1286–1313 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  5. Attiya, H., Welch, J.: Distributed Computing. Fundamentals, Simulations, and Advanced Topics. McGraw-Hill, New York (1998)

    Google Scholar 

  6. Borowsky, E., Gafni, E.: Generalized FLP impossibility result for \(t\)-resilient asynchronous computations. In: STOC, pp. 91–100. ACM Press, New york (1993)

  7. Borowsky, E., Gafni, E., Lynch, N., Rajsbaum, S.: The BG distributed simulation algorithm. Distrib. Comput. 14(3), 127–146 (2001)

    Google Scholar 

  8. Castañeda, A., Rajsbaum, S.: New combinatorial topology upper and lower bounds for renaming. In: PODC, pp. 295–304 (2008)

  9. Castañeda, A.: New combinatorial topology upper and lower bounds for renaming: the lower bound. Distrib. Comput. 52(5–6), 287–301 (2010)

    Article  Google Scholar 

  10. Castañeda, A.,. Rajsbaum, S. : New combinatorial topology upper and lower bounds for renaming: the upper bound. J. ACM 59(1), 3:1–3:49 (2012)

    Google Scholar 

  11. Chandra, T.D., Hadzilacos, V., Toueg, S.: The weakest failure detector for solving consensus. J. ACM 43(4), 685–722 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  12. Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225–267 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  13. Chaudhuri, S.: Agreement is harder than consensus: set consensus problems in totally asynchronous systems. In: PODC, pp. 311–324 (1990)

  14. Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  15. Gafni E.: Renaming with k-set-consensus: an optimal algorithm into \(n + k - 1\) slots. In: OPODIS, pp. 36–44 (2006)

  16. Gafni, E., Kuznetsov, P.: On set consensus numbers. Distrib. Comput. 24(3–4), 149–163 (2011)

    Article  MATH  Google Scholar 

  17. Gafni, E., Mostéfaoui, A., Raynal, M., Travers, C.: From adaptive renaming to set agreement. Theor. Comput. Sci. 410, 1328–1335 (2009)

    Article  MATH  Google Scholar 

  18. Gafni E., Rajsbaum S.: Distributed programming with tasks. In: OPODIS, pp. 205–218 (2010)

  19. Gafni E., Rajsbaum S., Herlihy, M.: Subconsensus tasks: renaming is weaker than set agreement. In: DISC, pp. 329–338 (2006)

  20. Gordon, D.M., Kuperberg, G., Patashnik, O.: New constructions for covering designs. J. Combin. Des. 3, 269–284 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  21. Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 123–149 (1991)

    Article  Google Scholar 

  22. Herlihy, M., Rajsbaum, S.: Algebraic spans. Math. Struct. Comput. Sci. 10(4), 549–573 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  23. Herlihy, M., Shavit, N.: The asynchronous computability theorem for \(t\)-resilient tasks. In: STOC, pp. 111–120 (1993)

  24. Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(2), 858–923 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  25. Jayanti, P., Toueg, S.: Every problem has a weakest failure detector. In: PODC, pp. 75–84 (2008)

  26. Lovász, L.: On the ratio of optimal integral and fractional covers. Discret. Math. 13, 383–390 (1975)

    Article  MATH  Google Scholar 

  27. Raynal, M.: \(K\)-anti-Omega, August 2007. Rump session at PODC (2007)

  28. Saks, M., Zaharoglou, F.: Wait-free \(k\)-set agreement is impossible: the topology of public knowledge. In: STOC, pp. 101–110. ACM Press, New York (1993)

  29. Schönheim, J.: On coverings. Pac. J. Math. 14, 1405–1411 (1964)

    Google Scholar 

  30. Zielinski, P.: Automatic classification of eventual failure detectors. In: DISC, pp. 465–479 (2007)

  31. Zieliński, P.: Anti- omega: the weakest failure detector for set agreement. Distrib. Comput. 22(5–6), 335–348 (2010)

    Article  MATH  Google Scholar 

Download references

Acknowledgments

We are grateful to Eli Gafni, Piotr Zieliński and the anonymous referees of DISC and this journal, for many fertile discussions, helping us to strengthen the results and improve the presentation.

Author information

Authors and Affiliations

  1. Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel

    Yehuda Afek & Israel Nir

  2. TU Berlin/Deutsche Telekom Laboratories, Berlin, Germany

    Petr Kuznetsov

Authors
  1. Yehuda Afek
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Petr Kuznetsov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Israel Nir
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yehuda Afek.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Afek, Y., Kuznetsov, P. & Nir, I. Renaming and the weakest family of failure detectors. Distrib. Comput. 25, 411–425 (2012). https://doi.org/10.1007/s00446-012-0177-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-012-0177-5

Keywords

Search

Navigation