Abstract
In the problem of reliable multiparty computation (RC), there are n parties, each with an individual input, and the parties want to jointly compute a function f over n inputs. The problem is complicated by the fact that an omniscient adversary controls a hidden fraction of the parties.
We describe a self-healing algorithm for this problem. In particular, for a fixed function f, with n parties and m gates, we describe how to perform RC repeatedly as the inputs to f change. Our algorithm maintains the following properties, even when an adversary controls up to \(t \leq (\frac{1}{4} - \epsilon) n\) parties, for any constant ε > 0. First, our algorithm performs each reliable computation with the following amortized resource costs: O(m + n logn) messages, O(m + n logn) computational operations, and O(ℓ) latency, where ℓ is the depth of the circuit that computes f. Second, the expected total number of corruptions is O(t (log* m)2 ), after which the adversarially controlled parties are effectively quarantined so that they cause no more corruptions.
This research is partially supported by NSF grants: CISE-1117985 and CNS-1017509.
The full paper is located at: http://cs.unm.edu/ saad/Papers/compute.pdf
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
Fiat, A., Saia, J.: Censorship resistant peer-to-peer networks. Theory of Computing 3(1), 1–23 (2007)
Hildrum, K., Kubiatowicz, J.: Asymptotically efficient approaches to fault-tolerance in peer-to-peer networks. In: Fich, F.E. (ed.) DISC 2003. LNCS, vol. 2848, pp. 321–336. Springer, Heidelberg (2003)
Naor, M., Wieder, U.: A simple fault tolerant distributed hash table. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol. 2735, pp. 88–97. Springer, Heidelberg (2003)
Scheideler, C.: How to spread adversarial nodes? rotate! In: STOC 2005, pp. 704–713 (2005)
Fiat, A., Saia, J., Young, M.: Making chord robust to Byzantine attacks. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 803–814. Springer, Heidelberg (2005)
Awerbuch, B., Scheideler, C.: Towards a scalable and robust DHT. Theory of Computing Systems 45(2), 234–260 (2009)
King, V., Lonargan, S., Saia, J., Trehan, A.: Load balanced scalable Byzantine agreement through quorum building, with full information. In: Aguilera, M.K., Yu, H., Vaidya, N.H., Srinivasan, V., Choudhury, R.R. (eds.) ICDCN 2011. LNCS, vol. 6522, pp. 203–214. Springer, Heidelberg (2011)
Frisanco, T.: Optimal spare capacity design for various protection switching methods in ATM networks. ICC 1997, vol. 1, pp. 293–298 (1997)
Iraschko, R.R., MacGregor, M.H., Grover, W.D.: Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks. IEEE/ACM Transactions on Networking 6(3), 325–336 (1998)
Murakami, K., Kim, H.S.: Comparative study on restoration schemes of survivable ATM networks. INFOCOM 1997, vol. 1, pp. 345–352 (1997)
Van Caenegem, B., Wauters, N., Demeester, P.: Spare capacity assignment for different restoration strategies in mesh survivable networks, ICC 1997, vol. 1, pp. 288–292 (1997)
Xiong, Y., Mason, L.G.: Restoration strategies and spare capacity requirements in self-healing ATM networks. IEEE/ACM Transactions on Networking 7(1), 98–110 (1999)
Boman, I., Saia, J., Abdallah, C.T., Schamiloglu, E.: Brief announcement: Self-healing algorithms for reconfigurable networks. In: Datta, A.K., Gradinariu, M. (eds.) SSS 2006. LNCS, vol. 4280, pp. 563–565. Springer, Heidelberg (2006)
Saia, J., Trehan, A.: Picking up the pieces: Self-healing in reconfigurable networks. In: IPDPS 2008, pp. 1–12 (2008)
Hayes, T., Rustagi, N., Saia, J., Trehan, A.: The forgiving tree: A self-healing distributed data structure. In: PODC 2008, pp. 203–212 (2008)
Hayes, T.P., Saia, J., Trehan, A.: The forgiving graph: A distributed data structure for low stretch under adversarial attack. In: PODC 2009, pp. 121–130 (2009)
Pandurangan, G., Trehan, A.: Xheal: localized self-healing using expanders. In: PODC 2011, pp. 301–310 (2011)
Sarma, A.D., Trehan, A.: Edge-preserving self-healing: keeping network backbones densely connected. In: IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 226–231 (2012)
Knockel, J., Saad, G., Saia, J.: Self-healing of Byzantine faults. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds.) SSS 2013. LNCS, vol. 8255, pp. 98–112. Springer, Heidelberg (2013)
Yao, A.C.: Protocols for secure computations. In: SFCS 1982, pp. 160–164 (1982)
Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: STOC 1988, pp. 1–10 (1988)
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority. In: STOC 1989, pp. 73–85 (1989)
Asharov, G., Lindell, Y.: A full proof of the BGW protocol for perfectly-secure multiparty computation. Electronic Colloquium on Computational Complexity (ECCC) 18, 36 (2011)
Prabhakaran, M., Sahai, A.: Secure Multi-Party Computation, vol. 10. IOS Press (2013)
Kate, A., Goldberg, I.: Distributed key generation for the internet. In: ICDCS 2009, pp. 119–128 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Saad, G., Saia, J. (2014). Self-healing Computation. In: Felber, P., Garg, V. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2014. Lecture Notes in Computer Science, vol 8756. Springer, Cham. https://doi.org/10.1007/978-3-319-11764-5_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-11764-5_14
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11763-8
Online ISBN: 978-3-319-11764-5
eBook Packages: Computer ScienceComputer Science (R0)