×

Ordered and delayed adversaries and how to work against them on a shared channel. (English) Zbl 1452.68270

Summary: An execution of a distributed algorithm is often seen as a game between the algorithm and a conceptual adversary causing specific distractions to the computation. In this work we define a class of ordered adaptive adversaries, which cause distractions – in particular crashes – online according to some partial order of the participating stations, which is fixed by the adversary before the execution. We distinguish: Linearly-Ordered adversary, restricted by some pre-defined linear order of (potentially) crashing stations; Anti-Chain-Ordered adversary, previously known as the Weakly-Adaptive adversary, which is restricted by some pre-defined set of crash-prone stations (it can be seen as an ordered adversary with the order being an anti-chain, i.e., a collection of incomparable elements, consisting of these stations); \(k\)-Thick-Ordered adversary restricted by partial orders of stations with a maximum anti-chain of size \(k\). We initiate a study of how they affect performance of algorithms. For this purpose, we focus on the well-known Do-All problem of performing \(t\) tasks by \(p\) synchronous crash-prone stations communicating on a shared channel. The channel restricts communication by the fact that no message is delivered to the operational stations if more than one station transmits at the same time. The question addressed in this work is how the ordered adversaries controlling crashes of stations influence work performance, defined as the total number of available processor steps during the whole execution and introduced by P. C. Kanellakis and A. A. Shvartsman [Distrib. Comput. 5, No. 4, 201–217 (1992; Zbl 0744.68060)] in the context of Write-All algorithms. The first presented algorithm solves the Do-All problem with work \({\mathcal{O}}(t+p \sqrt{t}\log p)\) against the Linearly-Ordered adversary. Surprisingly, the upper bound on performance of this algorithm does not depend on the number of crashes \(f\) and is close to the absolute lower bound \(\varOmega (t+p\sqrt{t})\) proved in [B. S. Chlebus et al., Distrib. Comput. 18, No. 6, 435–451 (2006; Zbl 1266.68207)]. Another algorithm is developed against the Weakly-Adaptive adversary. Work done by this algorithm is \(\mathcal{O}(t + p\sqrt{t} + p\min \left\{ p/(p-f),t\right\} \log p ),\) which is close to the lower bound \(\varOmega (t + p\sqrt{t} + p\min \left\{ p/(p-f),t\right\} )\) proved in [Chlebus, loc. cit.] and answers the open questions posed there. We generalize this result to the class of \(k\)-Thick-Ordered adversaries, in which case the work of the algorithm is bounded by \(\mathcal{O}(t + p\sqrt{t} + p\min \left\{ p/(p-f),k,t\right\} \log p ).\) We complement this result by proving the almost matching lower bound \(\varOmega (t + p\sqrt{t} + p\min \{ p/(p-f),k,t\} ).\) Independently from the results for the ordered adversaries, we consider a class of delayed adaptive adversaries, which could see random choices with some delay. We present an algorithm that works efficiently against the 1-RD adversary, which could see random choices of stations with one round delay, achieving close to optimal \({\mathcal{O}}(t+p \sqrt{t}\log ^2 p)\) work complexity. This shows that restricting the adversary by not allowing it to react on random decisions immediately makes it significantly weaker, in the sense that there is an algorithm achieving (almost) optimal work performance.

MSC:

68W15 Distributed algorithms
68M14 Distributed systems
68M15 Reliability, testing and fault tolerance of networks and computer systems
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
91A80 Applications of game theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abramson, N.: Development of the alohanet. IEEE Trans. Inf. Theor. 31(2), 119-123 (2006) · Zbl 0563.94001 · doi:10.1109/TIT.1985.1057021
[2] Awerbuch, B., Richa, A.W., Scheideler, C.: A jamming-resistant MAC protocol for single-hop wireless networks. In Bazzi, R.A., Patt-Shamir, B., (eds.) Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008, pp. 45-54. ACM (2008) · Zbl 1301.68041
[3] Bender, M.A., Fineman, J.T., Gilbert, S., Young, M.: How to scale exponential backoff: constant throughput, polylog access attempts, and robustness. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 636-654. SIAM (2016) · Zbl 1410.68066
[4] Brandes, Philipp; Kardas, Marcin; Klonowski, Marek; Pająk, Dominik; Wattenhofer, Roger, Approximating the Size of a Radio Network in Beeping Model, 358-373 (2016), Cham · Zbl 1437.68012 · doi:10.1007/978-3-319-48314-6_23
[5] Chen, B., Zhou, Z., Yu, H.: Understanding RFID counting protocols. In: Helal, S., Chandra, R., Kravets, R. (eds.) The 19th Annual International Conference on Mobile Computing and Networking, MobiCom’13, Miami, FL, USA, September 30-October 04, 2013, pp. 291-302. ACM (2013)
[6] Chlebus, BS; Pardalos, PM (ed.); Rajasekaran, S. (ed.); Reif, JH (ed.); Rolim, JDP (ed.), Randomized communication in radio networks, a chapter, No. 1 (2001), Dordrecht
[7] Chlebus, B.S., De Prisco, R., Shvartsman, A.A.: Performing tasks on synchronous restartable message-passing processors. Distrib. Comput. 14(1), 49-64 (2001) · Zbl 1448.68083 · doi:10.1007/PL00008926
[8] Chlebus, Bogdan S.; Gasieniec, Leszek; Kowalski, Dariusz R.; Shvartsman, Alex A., Bounding Work and Communication in Robust Cooperative Computation, 295-310 (2002), Berlin, Heidelberg · Zbl 1029.68519
[9] Chlebus, B.S., Gołąb, K., Kowalski, D.R.: Broadcasting spanning forests on a multiple access channel. Theory Comput. Syst. 36, 711-733 (2003) · Zbl 1101.68322 · doi:10.1007/s00224-003-1149-8
[10] Chlebus, B.S., Kowalski, D.R.: Randomization helps to perform independent tasks reliably. Random Struct. Algorithms 24(1), 11-41 (2004) · Zbl 1036.68126 · doi:10.1002/rsa.10104
[11] Chlebus, B.S., Kowalski, D.R., Lingas, A.: Performing work in broadcast networks. Distrib. Comput. 18(6), 435-451 (2006) · Zbl 1266.68207 · doi:10.1007/s00446-005-0153-4
[12] Chlebus, B.S., De Prisco, R., Shvartsman, A.A.: Performing tasks on synchronous restartable message-passing processors. Distrib. Comput. 14(1), 49-64 (2001) · Zbl 1448.68083 · doi:10.1007/PL00008926
[13] Clementi, Andrea E. F.; Monti, Angelo; Silvestri, Riccardo, Optimal F-Reliable Protocols for the Do-All Problem on Single-Hop Wireless Networks, 320-331 (2002), Berlin, Heidelberg · Zbl 1019.68503 · doi:10.1007/3-540-36136-7_29
[14] De Prisco, R., Mayer, A., Yung, M.: Time-optimal message-efficient work performance in the presence of faults. In: Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’94, pp. 161-172. ACM, New York (1994) · Zbl 1373.68090
[15] Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51(1), 161-166 (1950) · Zbl 0038.02003 · doi:10.2307/1969503
[16] Dwork, C., Halpern, J.Y., Waarts, O.: Performing work efficiently in the presence of faults. SIAM J. Comput. 27(5), 1457-1491 (1998) · Zbl 0907.68099 · doi:10.1137/S0097539793255527
[17] Galil, Z., Mayer, A., Yung, M.: Resolving message complexity of byzantine agreement and beyond. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS ’95, pp. 724. IEEE Computer Society, New York (1995) · Zbl 0938.68658
[18] Gallager, R.G.: A perspective on multiaccess channels. IEEE Trans. Inf. Theory 31, 124-142 (1985) · Zbl 0587.94001 · doi:10.1109/TIT.1985.1057022
[19] Georgiou, C., Kowalski, D.R., Shvartsman, A.A.: Efficient gossip and robust distributed computation. Theor. Comput. Sci. 347(1-2), 130-166 (2005) · Zbl 1080.68112 · doi:10.1016/j.tcs.2005.05.019
[20] Georgiou, C., Shvartsman, A.: Do-All Computing in Distributed Systems: Cooperation in the Presence of Adversity. Springer, Berlin (2008) · doi:10.1007/978-0-387-69045-2
[21] Georgiou, C., Shvartsman, A.A.: Cooperative task-oriented computing: algorithms and complexity. Synth. Lect. Distrib. Comput. Theory 2(2), 1-167 (2011) · doi:10.2200/S00376ED1V01Y201108DCT007
[22] Greenberg, A.G., Winograd, S.: A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. J. ACM 32(3), 589-596 (1985) · Zbl 0628.68026 · doi:10.1145/3828.214125
[23] Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco (2008)
[24] Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13-30 (1963) · Zbl 0127.10602 · doi:10.1080/01621459.1963.10500830
[25] Jurdziński, T., Kutyłowski, M., Zatopiański, J.: Efficient algorithms for leader election in radio networks. In: Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing, PODC ’02, pp. 51-57. ACM, New York (2002) · Zbl 1292.68013
[26] Kanellakis, P.C., Shvartsman, A.A.: Efficient parallel algorithms can be made robust. Distrib. Comput. 5(4), 201-217 (1992) · Zbl 0744.68060 · doi:10.1007/BF02277667
[27] Klonowski, M., Pajak, D.: Electing a leader in wireless networks quickly despite jamming. In: Blelloch, G.E., Agrawal, K. (eds.) Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, pap. 304-312. ACM, Portland (2015)
[28] Komlos, J., Greenberg, A.: An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Trans. Inf. Theor. 31(2), 302-306 (2006) · Zbl 0561.94004 · doi:10.1109/TIT.1985.1057020
[29] Kowalski, D.R.: On selection problem in radio networks. In: Proceedings of the Twenty-fourth Annual ACM Symposium on Principles of Distributed Computing, PODC ’05, pp. 158-166. ACM, New York (2005) · Zbl 1314.68028
[30] Kowalski, D.R., Shvartsman, A.A.: Performing work with asynchronous processors: Message-delay-sensitive bounds. In: Proceedings of the Twenty-second Annual Symposium on Principles of Distributed Computing, PODC ’03, pp. 265-274. ACM, New York (2003) · Zbl 1321.68086
[31] Kushilevitz, E., Mansour, Y.: An \[\omega (d\log (n/d))\] ω(dlog(n/d)) lower bound for broadcast in radio networks. SIAM J. Comput. 27(3), 702-712 (1998) · Zbl 0908.68067 · doi:10.1137/S0097539794279109
[32] Martel, C.U.: Maximum finding on a multiple access broadcast network. Inf. Process. Lett. 52(1), 7-13 (1994) · doi:10.1016/0020-0190(94)90133-3
[33] Metcalfe, R.M., Boggs, D.R.: Ethernet: distributed packet switching for local computer networks. Commun. ACM 19(7), 395-404 (1976) · doi:10.1145/360248.360253
[34] Richa, A.W., Scheideler, C., Schmid, S., Zhang, J.: Competitive and fair medium access despite reactive jamming. In: 2011 International Conference on Distributed Computing Systems, ICDCS 2011, June 20-24, 2011, pp. 507-516. IEEE Computer Society, Minneapolis (2011)
[35] Richa, A.W., Scheideler, C., Schmid, S., Zhang, J.: An efficient and fair MAC protocol robust to reactive interference. IEEE ACM Trans. Netw. 21(3), 760-771 (2013) · doi:10.1109/TNET.2012.2210241
[36] Willard, D.E.: Log-logarithmic selection resolution protocols in a multiple access channel. SIAM J. Comput. 15(2), 468-477 (1986) · Zbl 0612.94001 · doi:10.1137/0215032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.