Top

Distributed Computing

Published in:

26-09-2018

Making asynchronous distributed computations robust to noise

Authors: Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler

Published in: Distributed Computing | Issue 5/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating an optimal corruption of a \(\varTheta (1/n)\) fraction of all messages and incurring a moderate blowup of \(O(n\log ^2 n)\) in the communication complexity. Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network.

previous article Ordered and delayed adversaries and how to work against them on a shared channel

next article Non-blocking Patricia tries with replace operations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

To ease the readability, we write in parenthesis the functionality of each sent message, but we emphasize that messages in our construction contain no content at all, and the labels of Explore and Ack are given only for the analysis.

Throughout this work, all logarithms are taken to base 2.

While we focus here on deterministic protocols, our results also apply to randomized Monte-Carlo protocols.

This type of noise, commonly called insertion and deletion noise, is known to be more difficult to deal with in the interactive setting [8] and may be destructive for asynchronous protocols [14].

Note that additional messages may arrive from a sibling node as part of the BFS construction. Still, the next message arriving from the parent belongs to the coding scheme rather than to the BFS construction.

Later, in Sect. 5, we apply our root-triggered synchronizer to an input protocol on G which is fully-utilized on a spanning subgraph S of G.

E.g., when using an \(O(\log n)\)-spanner of size \(s=O(n)\) towards Corollary 13.

In Theorem 12 we allow \(\pi _{spanner}\) to be an asynchronous protocol. Note, however, that the same applies to synchronous protocols given as an inputs to our coding scheme: let every party speak at every round (sending dummies as needed); then redefine the protocol in an asynchronous model where each party sends the messages of a given round after receiving all the messages of a previous round. It follows that any synchronous protocol with time complexity \(\tau \) sending messages of size \(\sigma \) can be converted into an equivalent asynchronous protocol with message complexity \(O(\tau m)\) and communication complexity \(O(\tau m \sigma )\).

A different approach would be to add another bit that contains the parity of the message number. Then, the receiver will be able to distinguish whether a received bit is the continuation of a previous message, or the first bit of a new message.

By balancing the parts \(C_1\) and \(C_2\) in a weighted way one can obtain a slightly improved resilience of \(\mu _1\mu _2/(\mu _1+\mu _2)= \varTheta (1/(n+s))\) which is, however, asymptotically equivalent to \(\varTheta (1/s)\).

Alon, N., Braverman, M., Efremenko, K., Gelles, R., Haeupler, B.: Reliable communication over highly connected noisy networks. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC ’16, pp. 165–173 (2016). https://doi.org/10.1145/2933057.2933085

Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics. Wiley, New York (2004)CrossRef

Awerbuch, B.: Complexity of network synchronization. J. ACM 32(4), 804–823 (1985). https://doi.org/10.1145/4221.4227 MathSciNetCrossRefMATH

Awerbuch, B., Patt-Shamir, B., Peleg, D., Saks, M.E.: Adapting to asynchronous dynamic networks (extended abstract). In: STOC ’92: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pp. 557–570 (1992). https://doi.org/10.1145/129712.129767

Brakerski, Z., Kalai, Y.T., Naor, M.: Fast interactive coding against adversarial noise. J. ACM 61(6), 35:1–35:30 (2014). https://doi.org/10.1145/2661628 MathSciNetCrossRefMATH

Braverman, M., Efremenko, K.: List and unique coding for interactive communication in the presence of adversarial noise. SIAM J. Comput. 46(1), 388–428 (2017). https://doi.org/10.1137/141002001 MathSciNetCrossRefMATH

Braverman, M., Efremenko, K., Gelles, R., Haeupler, B.: Constant-rate coding for multiparty interactive communication is impossible. J. ACM 65(1), 4:1–4:41 (2017). https://doi.org/10.1145/3050218 MathSciNetCrossRefMATH

Braverman, M., Gelles, R., Mao, J., Ostrovsky, R.: Coding for interactive communication correcting insertions and deletions. IEEE Trans. Inf. Theory 63(10), 6256–6270 (2017). https://doi.org/10.1109/TIT.2017.2734881 MathSciNetCrossRefMATH

Braverman, M., Rao, A.: Toward coding for maximum errors in interactive communication. IEEE Trans. Inf. Theory 60(11), 7248–7255 (2014). https://doi.org/10.1109/TIT.2014.2353994 MathSciNetCrossRefMATH

10.

Dasgupta, P.: Agreement under faulty interfaces. Inf. Process. Lett. 65(3), 125–129 (1998). https://doi.org/10.1016/S0020-0190(97)00202-0 MathSciNetCrossRefMATH

11.

Derbel, B., Mosbah, M., Zemmari, A.: Sublinear fully distributed partition with applications. Theory Comput. Syst. 47(2), 368–404 (2010). https://doi.org/10.1007/s00224-009-9190-x MathSciNetCrossRefMATH

12.

Efremenko, K., Gelles, R., Haeupler, B.: Maximal noise in interactive communication over erasure channels and channels with feedback. IEEE Trans. Inf. Theory 62(8), 4575–4588 (2016). https://doi.org/10.1109/TIT.2016.2582176 MathSciNetCrossRefMATH

13.

Feinerman, O., Haeupler, B., Korman, A.: Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. Distrib. Comput. 30(5), 339–355 (2017). https://doi.org/10.1007/s00446-015-0249-4 MathSciNetCrossRefMATH

14.

Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985). https://doi.org/10.1145/3149.214121 MathSciNetCrossRefMATH

15.

Franklin, M., Gelles, R., Ostrovsky, R., Schulman, L.J.: Optimal coding for streaming authentication and interactive communication. IEEE Trans. Inf. Theory 61(1), 133–145 (2015). https://doi.org/10.1109/TIT.2014.2367094 MathSciNetCrossRefMATH

16.

Gallager, R.G.: Distributed minimum hop algorithms. Technical report LIDS-P-1175, M.I.T. Laboratory for Information and Decision Systems (1982)

17.

Gelles, R.: Coding for interactive communication: a survey. Found. Trends Theor. Comput. Sci. 13(1–2), 1–157 (2017). https://doi.org/10.1561/0400000079 MathSciNetCrossRefMATH

18.

Gelles, R., Haeupler, B., Kol, G., Ron-Zewi, N., Wigderson, A.: Towards optimal deterministic coding for interactive communication. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1922–1936 (2016). https://doi.org/10.1137/1.9781611974331.ch135

19.

Gelles, R., Kalai, Y.T.: Constant-rate interactive coding is impossible, even in constant-degree networks. In: C.H. Papadimitriou (ed.) 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), Leibniz International Proceedings in Informatics (LIPIcs), vol. 67, pp. 21:1–21:13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017). https://doi.org/10.4230/LIPIcs.ITCS.2017.21

20.

Gelles, R., Moitra, A., Sahai, A.: Efficient coding for interactive communication. IEEE Trans. Inf. Theory 60(3), 1899–1913 (2014). https://doi.org/10.1109/TIT.2013.2294186 MathSciNetCrossRefMATH

21.

Ghaffari, M., Haeupler, B.: Optimal error rates for interactive coding II: Efficiency and list decoding. In: Proceedings of the 55th annual IEEE Symposium on Foundations of Computer Science, FOCS ’14, pp. 394–403 (2014). https://doi.org/10.1109/FOCS.2014.49

22.

Gong, L., Lincoln, P., Rushby, J.: Byzantine agreement with authentication: observations and applications in tolerating hybrid and link faults. In: Dependable Computing and Fault Tolerant Systems, vol. 10, pp. 139–158. IEEE Computer Society (1995). http://www.csl.sri.com/papers/dcca95/dcca95.pdf

23.

Haeupler, B.: Interactive channel capacity revisited. In: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’14, pp. 226–235 (2014). https://doi.org/10.1109/FOCS.2014.32

24.

Harrington, M., Somani, A.K.: Synchronizing hypercube networks in the presence of faults. IEEE Trans. Comput. 43(10), 1175–1183 (1994). https://doi.org/10.1109/12.324543 CrossRefMATH

25.

Hoza, W.M., Schulman, L.J.: The adversarial noise threshold for distributed protocols. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 240–258 (2016). https://doi.org/10.1137/1.9781611974331.ch18

26.

Jain, A., Kalai, Y.T., Lewko, A.: Interactive coding for multiparty protocols. In: Proceedings of the 6th Conference on Innovations in Theoretical Computer Science, ITCS ’15, pp. 1–10 (2015). https://doi.org/10.1145/2688073.2688109

27.

Kol, G., Raz, R.: Interactive channel capacity. In: STOC ’13: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, pp. 715–724. ACM (2013). https://doi.org/10.1145/2488608.2488699

28.

Lewko, A.B., Vitercik, E.: Balancing communication for multi-party interactive coding (2015). arXiv:1503.06381

29.

Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco (1996)MATH

30.

Pelc, A.: Reliable communication in networks with byzantine link failures. Networks 22(5), 441–459 (1992). https://doi.org/10.1002/net.3230220503 CrossRefMATH

31.

Peleg, D.: Distributed computing: a locality-sensitive approach. Soc. Ind. Appl. Math. (2000). https://doi.org/10.1137/1.9780898719772 CrossRefMATH

32.

Peleg, D., Schäffer, A.A.: Graph spanners. J. Graph Theory 13(1), 99–116 (1989). https://doi.org/10.1002/jgt.3190130114 MathSciNetCrossRefMATH

33.

Rajagopalan, S., Schulman, L.: A coding theorem for distributed computation. In: STOC ’94: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 790–799 (1994). https://doi.org/10.1145/195058.195462

34.

Sayeed, H.M., Abu-Amara, M., Abu-Amara, H.: Optimal asynchronous agreement and leader election algorithm for complete networks with byzantine faulty links. Distrib. Comput. 9(3), 147–156 (1995). https://doi.org/10.1007/s004460050016 MathSciNetCrossRef

35.

Schulman, L.J.: Communication on noisy channels: a coding theorem for computation. In: Annual IEEE Symposium on Foundations of Computer Science, pp. 724–733 (1992). https://doi.org/10.1109/SFCS.1992.267778

36.

Schulman, L.J.: Coding for interactive communication. IEEE Trans. Inf. Theory 42(6), 1745–1756 (1996). https://doi.org/10.1109/18.556671 MathSciNetCrossRefMATH

37.

Singh, G.: Leader election in the presence of link failures. IEEE Trans. Parallel Distrib. Syst. 7(3), 231–236 (1996). https://doi.org/10.1109/71.491576 CrossRef

38.

Siu, H.S., Chin, Y.H., Yang, W.P.: Byzantine agreement in the presence of mixed faults on processors and links. IEEE Trans. Parallel Distrib. Syst. 9(4), 335–345 (1998). https://doi.org/10.1109/71.667895 CrossRef

39.

Tel, G.: Introduction to Distributed Algorithms, pp. 414–420. Cambridge University Press, Cambridge (2000)

Title: Making asynchronous distributed computations robust to noise
Authors: Keren Censor-Hillel
Ran Gelles
Bernhard Haeupler
Publication date: 26-09-2018
Publisher: Springer Berlin Heidelberg
Published in: Distributed Computing / Issue 5/2019
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI: https://doi.org/10.1007/s00446-018-0343-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 5/2019

Non-blocking Patricia tries with replace operations

Ordered and delayed adversaries and how to work against them on a shared channel

Secretary markets with local information

Consensus in rooted dynamic networks with short-lived stability

Premium Partner