Performing work in broadcast networks

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)