Abstract
We consider the problem of how to schedule t similar and independent tasks to be performed in a synchronous distributed system of p stations communicating via multiple-access channels. Stations are prone to crashes whose patterns of occurrence are specified by adversarial models. Work, defined as the number of the available processor steps, is the complexity measure. We consider only reliable algorithms that perform all the tasks as long as at least one station remains operational. It is shown that every reliable algorithm has to perform work Ω(t+p√t) even when no failures occur. An optimal deterministic algorithm for the channel with collision detection is developed, which performs work \({\mathcal O}\)(t+p√t). Another algorithm, for the channel without collision detection, performs work \({\mathcal O}\)(t+p √t+ p min {f,t}), where f < p is the number of failures. This algorithm is proved to be optimal, provided that the adversary is restricted in failing no more than f stations. Finally, we consider the question if randomization helps against weaker adversaries for the channel without collision detection. A randomized algorithm is developed which performs the expected minimum amount \({\mathcal O}\)(t+p√t) of work, provided that the adversary may fail a constant fraction of stations and it has to select failure-prone stations prior to the start of an execution of the algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Dwork, C., Halpern, J., Waarts, O.: Performing work efficiently in the presence of faults. SIAM J. Comput. 27, 1457–1491 (1998)
Chlebus, B.S.: Randomized communication in radio networks, a chapter. In: Pardalos, P.M., Rajasekaran, S., Reif, J.H., Rolim, J.D.P. (eds.), Handbook on Randomized Computing, vol 1, pp. 401–456. Kluwer Academic Publisher, Drodrecht (2001)
Gallager, R.G.: A perspective on multiaccess channels. IEEE Trans. Inform. Theor. 31, 124–142 (1985)
Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd edn. John Wiley, New York (2004)
Kanellakis, P.C., Shvartsman, A.A.: Fault-Tolerant Parallel Computation. Kluwer Academic Publisher, Drodrecht (1997)
Chlebus, B.S., De Prisco, R., Shvartsman, A.A.: Performing tasks on synchronous restartable message-passing processors. Distribut. Comput. 14, 49–64 (2001)
Chlebus, B.S., Gąsieniec, L., Kowalski, D.R., Shvartsman, A.A.: Balancing work and communication in robust cooperative computation. In: Proceedings of the 16th International Symposium on Distributed Computing (DISC). LNCS 2508, pp. 295–310 (2002)
Chlebus, B.S., Kowalski, D.R.: Randomization helps to perform independent tasks reliably. Random Struct. Algorithms 24, 11–41 (2004)
De Prisco, R., Mayer, A., Yung, M.: Time-optimal message-efficient work performance in the presence of faults. In: Proceedings of the 13th ACM Symposium on Principles of Distributed Computing (PODC), pp. 161–172 (1994)
Galil, Z., Mayer, A., Yung, M.: Resolving message complexity of Byzantine agreement and beyond. In: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 724–733 (1995)
Kanellakis, P.C., Shvartsman, A.A.: Efficient parallel algorithms can be made robust. Distribut. Comput. 5, 201–217 (1992)
Georgiou, C., Kowalski, D.R., Shvartsman, A.A.: Efficient gossip and robust distributed computation. In: Proceedings of the 17th International Symposium on Distributed Computing (DISC), LNCS 2848, pp. 224–238 (2003)
Kowalski, D.R., Shvartsman, A.A.: Performing work with asynchronous processors: message-delay-sensitive bounds. In: Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 265–274 (2003)
Georgiou, C., Russell, A., Shvartsman, A.A.: Work-competitive scheduling for cooperative computing with dynamic groups. SIAM J. Comput. 34, 848–862 (2005)
Georgiou, C., Russell, A., Shvartsman, A.A.: The complexity of synchronous iterative Do-All with crashes. Distribut. Comput. 17, 47–63 (2004)
Fernández, A., Georgiou, C., Russell, A., Shvartsman, A.A.: The Do-All problem with Byzantine processor failures. Theor. Comput. Sci. 333, 433–454 (2005)
Clementi, A.E.F., Monti, A., Silvestri, R.: Optimal F-reliable protocols for the do-all problem on single-hop wireless networks. In: Proceedings of thes 13th International Symposium on Algorithms and Computation (ISAAC), LNCS 2518, pp. 320–331 (2002)
Abramson, N.: Development of the Alohanet. IEEE Trans. Inform. Theor. 31, 119–123 (1985)
Metcalfe, R.M., Boggs, D.R.: Ethernet: distributed packet switching for local computer networks. Commun. ACM 19, 395–404 (1976)
Goldberg, L.A., Jerrum, M., Kannan S., Paterson, M.: A bound on the capacity of backoff and acknowledgement-based protocols. SIAM J. Comput. 33, 313–331 (2004)
Goldberg, L.A., MacKenzie, P., Paterson, M., Srinivasan, A.: Contention resolution with constant expected delay. J. ACM 47, 1048–1096 (2000)
Hå stad, J., Leighton, T., Rogoff, B.: Analysis of backoff protocols for multiple access channels. SIAM J. Comput. 25, 740–774 (1996)
Raghavan, P., Upfal, E.: Stochastic contention resolution with short delays. SIAM J. Comput. 28, 709–719 (1998)
Willard, D.E.: Log-logarithmic selection resolution protocols in a multiple access channel. SIAM J. Comput. 15, 468–477 (1986)
Kushilevitz, E., Mansour, Y.: An Ω(D log (N/D)) lower bound for broadcast in radio networks. SIAM J. Comput. 27, 702–712 (1998)
Martel, C.U.: Maximum finding on a multiple access broadcast network. Inform. Process. Lett. 52, 7–13 (1994)
Komlós, J., Greenberg, A.G.: An asymptotically nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Trans. Inform. Theor. 31, 303–306 (1985)
Kowalski, D.R.: On selection problem in radio networks. In: Proceedings of the 24th ACM Symposium on Principles of Distributed Computing (PODC), pp. 158–166 (2005)
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, 589–596 (1985)
Jurdziński, T., Kutył owski, M., Zatopiański, J.: Efficient algorithms for leader election in radio networks. In: Proceedings of the 21th ACM Symposium on Principles of Distributed Computing (PODC), pp. 51–57 (2002)
Chlebus, B.S., Gołąb, K., Kowalski, D.R.: Broadcasting spanning forests on a multiple access channel. Theor. Comput. Syst. 36, 711–733 (2003)
Gąsieniec, L., Pelc, A., Peleg, D.: The wakeup problem in synchronous broadcast systems. SIAM J. Discrete Math. 14, 207–222 (2001)
Jurdziński, T., Stachowiak, G.: Probabilistic algorithms for the wakeup problem in single-hop radio networks. In: Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC), LNCS 2518, pp. 535–549 (2002)
Chrobak, M., Gąsieniec, L., Kowalski, D.R.: The wake-up problem in multi-hop radio networks. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 985–993 (2004)
Indyk, P.: Explicit constructions of selectors and related combinatorial structures, with applications. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 697–704 (2002)
Chlebus, B.S., Kowalski, D.R.: A better wake-up in radio networks. In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 266–274 (2004)
Fich, F., Ruppert, E.: Lower bounds in distributed computing. In: Proceedings of the 14th International Symposium on Distributed Computing (DISC), LNCS 1914, pp. 1–28 (2000)
Halpern, J.Y., Moses, Y.: Knowledge and common knowledge in a distributed environment. J. ACM 37, 549–587 (1990)
McDiarmid, C.: Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.), Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195–248. Springer-Verlag, Berlin (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of the first author is supported by the NSF Grant 0310503. A preliminary version of this paper appeared as “The do-all problem in broadcast networks,” in Proceedings, 20th ACM Symposium on Principles of Distributed Computing, Newport, Rhode Island, 2001, pp. 117–126.
Rights and permissions
About this article
Cite this article
Chlebus, B.S., Kowalski, D.R. & Lingas, A. Performing work in broadcast networks. Distrib. Comput. 18, 435–451 (2006). https://doi.org/10.1007/s00446-005-0153-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-005-0153-4