Aleksandar Prokopec
ABSTRACT
Distributed systems are often built from the simplest building blocks such as message sends and RPCs. Since many communication patterns have to be reinvented every time a distributed system is created, implementing a high-level system is usually expensive. The recently proposed reactor model alleviates this cost by expressing distributed computations as reusable components, however, encodings for various communications patterns in this model are missing.
This paper investigates how to encode the router, client-server, scatter-gather, rendezvous, two-way communication, reliable communication and the backpressure protocol in the reactor model. These protocols are used to implement the core of a distributed streaming framework, and the performance of these implementations is evaluated.
- 2015. Erlang/OTP Documentation. (2015). http://www.erlang.org/Google Scholar
- 2016. Akka Documentation. (2016). http://akka.io/docs/Google Scholar
- 2016. Akka Streams Documentation. (2016). http://doc.akka.io/docs/ akka/2.4.3/scala/stream/index.htmlGoogle Scholar
- 2016. Reactive Streams. (2016). http://www.reactive-streams.org/Google Scholar
- 2016. Reactors.IO website. (2016). http://reactors.io/Google Scholar
- Gul Agha. 1986. Actors: A Model of Concurrent Computation in Distributed Systems. MIT Press, Cambridge, MA, USA.Google ScholarCross Ref
- Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni. 2009. Streaming k-means approximation. In NIPS.Google Scholar
- Cosmin Arad, Jim Dowling, and Seif Haridi. 2012. Message-passing Concurrency for Scalable, Stateful, Reconfigurable Middleware. In Proceedings of the 13th International Middleware Conference (Middleware ’12). Springer-Verlag New York, Inc., New York, NY, USA, 208–228.Google Scholar
- J.-P. Briot. 1988. From Objects to Actors: Study of a Limited Symbiosis in Smalltalk-80. In Proceedings of the 1988 ACM SIGPLAN Workshop on Object-based Concurrent Programming (OOPSLA/ECOOP ’88). ACM, New York, NY, USA, 69–72. DOI: Google ScholarDigital Library
- Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache Flink™: Stream and Batch Processing in a Single Engine. IEEE Data Eng. Bull. 38, 4 (2015), 28–38. http://sites.computer.org/debull/A15dec/p28.pdfGoogle Scholar
- Graham Cormode and S. Muthukrishnan. 2005. An Improved Data Stream Summary: The Count-min Sketch and Its Applications. J. Algorithms 55, 1 (April 2005), 58–75. DOI: Google ScholarDigital Library
- Tom Van Cutsem, Elisa Gonzalez Boix, Christophe Scholliers, Andoni Lombide Carreton, Dries Harnie, Kevin Pinte, and Wolfgang De Meuter. 2014. AmbientTalk: programming responsive mobile peerto-peer applications with actors. Computer Languages, Systems and Structures, SCI Impact factor in 2013: 0.296, 5 year impact factor 0.329 (to appear) (2014).Google Scholar
- Iulian Dragos and Martin Odersky. 2009. Compiling generics through user-directed type specialization. In Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems (ICOOOLPS ’09). ACM, New York, NY, USA, 42–47. DOI: Google ScholarDigital Library
- Patrick Th. Eugster, Pascal A. Felber, Rachid Guerraoui, and AnneMarie Kermarrec. 2003. The Many Faces of Publish/Subscribe. ACM Comput. Surv. 35, 2 (June 2003), 114–131. DOI: Google ScholarDigital Library
- Philippe Flajolet, ÃĽric Fusy, Olivier Gandouet, and et al. 2007. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In IN AOFA âĂŹ07: PROCEEDINGS OF THE 2007 INTERNATIONAL CONFERENCE ON ANALYSIS OF ALGORITHMS.Google Scholar
- Message Passing Interface Forum. 2012. MPI: A Message-Passing Interface Standard Version 3.0. (09 2012). Chapter author for Collective Communication, Process Topologies, and One Sided Communications.Google Scholar
- Cédric Fournet and Georges Gonthier. 2002. The Join Calculus: A Language for Distributed Mobile Programming. Springer Berlin Heidelberg, Berlin, Heidelberg, 268–332. DOI: Google ScholarCross Ref
- Andy Georges, Dries Buytaert, and Lieven Eeckhout. 2007. Statistically Rigorous Java Performance Evaluation. SIGPLAN Not. 42, 10 (Oct. 2007), 57–76. DOI: Google ScholarDigital Library
- J.Y. Girard. 1972. Interprétation fonctionnelle et élimination des coupures de l’arithmétique d’ordre supérieur. https://books.google.hr/books?id= IRcVHAAACAAJGoogle Scholar
- Rachid Guerraoui and Luís Rodrigues. 2006. Introduction to reliable distributed programming. Springer.Google Scholar
- Philipp Haller and Martin Odersky. 2006. Event-Based Programming without Inversion of Control. In Proc. Joint Modular Languages Conference (Springer LNCS). Google ScholarDigital Library
- Philipp Haller, Aleksandar Prokopec, Heather Miller, Viktor Klang, Roland Kuhn, and Vojin Jovanovic. 2012. Scala Improvement Proposal: Futures and Promises (SIP-14). http://docs.scala-lang.org/sips/ pending/futures-promises.htmlGoogle Scholar
- Benjamin Hindman, Andy Konwinski, Matei Zaharia, Ali Ghodsi, Anthony D. Joseph, Randy Katz, Scott Shenker, and Ion Stoica. 2011. Mesos: A Platform for Fine-grained Resource Sharing in the Data Center. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (NSDI’11). USENIX Association, Berkeley, CA, USA, 295–308. http://dl.acm.org/citation.cfm?id=1972457.1972488Google ScholarDigital Library
- C. A. R. Hoare. 1978. Communicating Sequential Processes. Commun. ACM 21, 8 (Aug. 1978), 666–677. DOI: Google ScholarDigital Library
- Shams M. Imam and Vivek Sarkar. 2014. Selectors: Actors with Multiple Guarded Mailboxes. In Proceedings of the 4th International Workshop on Programming Based on Actors Agents and Decentralized Control (AGERE! ’14). ACM, New York, NY, USA, 1–14. DOI: Google ScholarDigital Library
- Nancy A. Lynch. 1996. Distributed Algorithms. MK Publishers Inc., San Francisco, CA, USA.Google Scholar
- Erik Meijer. 2012. Your Mouse is a Database. Commun. ACM 55, 5 (May 2012), 66–73. DOI: Google ScholarDigital Library
- Robin Milner, Joachim Parrow, and David Walker. 1992. A Calculus of Mobile Processes, I. Inf. Comput. 100, 1 (Sept. 1992), 1–40. DOI: Google ScholarDigital Library
- Thomas D. Newton. 1987. An implementation of Ada tasking. (1987).Google Scholar
- Martin Odersky. 2002. An Introduction to Functional Nets. Springer Berlin Heidelberg, Berlin, Heidelberg, 333–377. DOI: Google ScholarCross Ref
- Martin Odersky and al. 2004. An Overview of the Scala Programming Language. Technical Report IC/2004/64. EPFL Lausanne, Switzerland.Google Scholar
- Benjamin C. Pierce. 2002. Types and Programming Languages. MIT Press, Cambridge, MA, USA.Google Scholar
- Rob Pike, Dave Presotto, Ken Thompson, and Gerard Holzmann. 1991. Process Sleep and Wakeup on a Shared-memory Multiprocessor. (1991).Google Scholar
- Aleksandar Prokopec. 2014. ScalaMeter Website. (2014). http:// scalameter.github.ioGoogle Scholar
- Aleksandar Prokopec. 2016. Pluggable Scheduling for the Reactor Programming Model. In Proceedings of the 6th International Workshop on Programming Based on Actors, Agents, and Decentralized Control (AGERE 2016). ACM, New York, NY, USA, 41–50. DOI: Google ScholarDigital Library
- Aleksandar Prokopec, Philipp Haller, and Martin Odersky. 2014. Containers and Aggregates, Mutators and Isolates for Reactive Programming. In Proceedings of the Fifth Annual Scala Workshop (SCALA ’14). ACM, 51–61. DOI: Google ScholarDigital Library
- Aleksandar Prokopec and Martin Odersky. 2015. Isolates, Channels, and Event Streams for Composable Distributed Programming. In 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!) (Onward! 2015). ACM, New York, NY, USA, 171–182.Google ScholarDigital Library
- M. Shreedhar and George Varghese. 1995. Efficient Fair Queueing Using Deficit Round Robin. SIGCOMM Comput. Commun. Rev. 25, 4 (Oct. 1995), 231–242. DOI: Google ScholarDigital Library
- Sriram Srinivasan and Alan Mycroft. 2008. Kilim: Isolation-Typed Actors for Java. Springer Berlin Heidelberg, Berlin, Heidelberg, 104– 128. DOI: Google ScholarDigital Library
- Robert Virding, Claes Wikström, and Mike Williams. 1996. Concurrent Programming in ERLANG (2nd Ed.). Prentice Hall International (UK) Ltd., Hertfordshire, UK, UK.Google Scholar
- Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2012. Resilient Distributed Datasets: A Fault-tolerant Abstraction for In-memory Cluster Computing. In Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (NSDI’12). USENIX Association, Berkeley, CA, USA, 2–2. http://dl.acm.org/citation.cfm?id=2228298.2228301Google ScholarDigital Library
- Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (HotCloud’10). USENIX Association, Berkeley, CA, USA, 10–10. http://dl.acm.org/citation.cfm?id=1863103.1863113Google ScholarDigital Library
- Matei Zaharia, Tathagata Das, Haoyuan Li, Timothy Hunter, Scott Shenker, and Ion Stoica. 2013. Discretized Streams: Fault-tolerant Streaming Computation at Scale. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP ’13). ACM, New York, NY, USA, 423–438. DOI: Google ScholarDigital Library
Index Terms
- Encoding the building blocks of communication
Recommendations
Towards Configurable Building Blocks for the Development of Distributed Services: Resource Selection and Communication Protocols
3PGCIC '11: Proceedings of the 2011 International Conference on P2P, Parallel, Grid, Cloud and Internet ComputingIn this paper we argue our view for providing a set of configurable building blocks for the development of distributed services and discuss in detail the architecture of two such blocks: a fault-tolerant, fully decentralized resource selection component ...
Bounds on the Efficiency of Message-Passing Protocols for Parallel Computers
This paper considers the problem of creating message-passing protocols for parallel computers. It is assumed that the processors are connected by a network that provides guaranteed delivery of every message, provided that each message delivered ...
Abstract Communication Model for Distributed Systems
In some distributed and mobile communication models, a message disappears in one place and miraculously appears in another. In reality, of course, there are no miracles. A message goes from one network to another; it can be lost or corrupted in the ...
Comments