Distributed Computing

Hagit Attiya, Jennifer Welch

Mentioned 1

The explosive growth of distributed computing systems makes understanding them imperative. To make this notoriously difficult subject accessible, 'Distributed Computing; Fundamentals, Simulations, and Advanced Topics; Second Edition', provides a solid introduction to the mathematical foundations and theory of distributed computing, highlighting common themes and basic techniques. The authors present the fundamental issues underlying the design of distributed systems - communication, coordination, synchronization, and uncertainty - as well as fundamental algorithmic concepts and lower-bound techniques. The book’s unifying approach emphasizes the similarities between different models and explains inherent discrepancies between them.

More on Amazon.com

Mentioned in questions and answers.

I've been studying the actor model (specifically the implementation in Scala) but I can't understand why there's a requirement that messages arrive in no particular order.

It seems like there are at least some elegant, actor-based solutions to concurrency problems that would work if only the messages arrived in order (e.g. producer-consumer variants, deferred database writes, concurrency-safe caches).

So why don't actor messages arrive in order? Is it to permit efficient implementation or maybe to prevent some kind of deadlock that would arise when messages are ordered?

I'm not privy to the reasons why Scala's Actors (those in the standard library, at any rate -- there are also Akka, Lift and Scalaz implementations of Actors) chose that particular implementation. Probably as a copy of Erlang's own restrictions -- but without the guarantees for communication between two single threads. Or maybe with that guarantee as well -- I wish Phillip Haller was here to comment.

BUT, I do question your statement about concurrency problems. When studying asynchronous distributed algorithms, a basic tenet is that you can't guarantee any ordering of message receipt.

To quote Distributed Computing: Fundamentals, Simulation and Advanced Topics, by Hagit Attiya and Jennifer Welch,

A system is said to be asynchronous if there is no fixed upper bound on how long it takes for a message to be delivered or how much time elapses between consecutive steps of a processor.

The actor model is an asynchronous one. That enables it to work over distributed hardware -- be it different computers communicating through a network, or different processors on a system that does not provide synchronous guarantees.

Furthermore, even the multi-threading model on a multi-core processor is mostly asynchronous, with the primitives that enable synchronism being extremely expensive.

So a simple answer to the question might be:

Messages are not guaranteed to arrive in order because that's an underlying limitation of asynchronous systems, which is the basic model of computation used by actors.

This model is the one we actually have on any system distributed over TCP/IP, and the most efficient over i386/x64 multicore/multiprocessor hardware.

Realated tags