Abstract
We address two problems, the g-tight group renaming task and what we call, safe-consensus task, and show the relations between them. We show that any g-tight group renaming task, the first problem, implements g processes consensus. We show this by introducing an intermediate task, the safe-consensus task, the second problem, and showing that g-tight group renaming implements g-safe-consensus and that the latter implements g-consensus. It is known that with g-consensus g-tight group renaming is solvable, making the two problems equivalent.
The safe-consensus task, is of independent interest. In it the validity condition of consensus is weakened as follows: if the first processor to invoke the task returns before any other processor invokes, i.e., it runs in solo, then it outputs its input; Otherwise the consensus output can be arbitrary, not even the input of any process. We show the equivalence between safe-(set-)consensus and (set-)consensus.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic Snapshots of Shared Memory. Journal of the ACM 40(4), 873–890 (1993)
Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. J. ACM 37(3), 524–548 (1990)
Afek, Y., Gamzu, I., Levy, I., Merritt, M., Taubenfeld, G.: Group renaming. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 58–72. Springer, Heidelberg (2008)
Borowsky, E., Gafni, E.: The Implication of the Borowsky-Gafni Simulation on the Set-Consensus Hierarchy. Technical Report 930021, Department of Computer Science, UCLA (1993)
Afek, Y., Gafni, E., Rajsbaum, S., Raynal, M., Travers, C.: Simultaneous consensus tasks: A tighter characterization of set-consensus. In: Chaudhuri, S., Das, S.R., Paul, H.S., Tirthapura, S. (eds.) ICDCN 2006. LNCS, vol. 4308, pp. 331–341. Springer, Heidelberg (2006)
De Prisco, R., Malkhi, D., Reiter, M.: On k-Set Consensus Problems in Asynchronous Systems. IEEE Transactions on Parallel and Distributed Systems 12(1), 7–21 (2001)
Chaudhuri, S.: More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems. Information and Computation 105, 132–158 (1993)
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM 32(2), 374–382 (1985)
Gafni, E.: Group-solvability. In: Guerraoui, R. (ed.) DISC 2004. LNCS, vol. 3274, pp. 30–40. Springer, Heidelberg (2004)
Guerraoui, R., Kuznetsov, P.: The gap in circumventing the impossibility of consensus. J. Comput. Syst. Sci. 74(5), 823–830 (2008)
Herlihy, M.P.: Wait-Free Synchronization. ACM Transactions on Programming Languages and Systems 13(1), 124–149 (1991)
Herlihy, M.P., Wing, J.M.: Linearizability: a Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems 12(3), 463–492 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Afek, Y., Gafni, E., Lieber, O. (2009). Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus. In: Keidar, I. (eds) Distributed Computing. DISC 2009. Lecture Notes in Computer Science, vol 5805. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04355-0_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-04355-0_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04354-3
Online ISBN: 978-3-642-04355-0
eBook Packages: Computer ScienceComputer Science (R0)