Coordination Strategies: Models

• Full crossbar
  In a full crossbar, every agent must communicate with every other agent on a regular basis.
  • Advantages:
    • Algorithms with are most easily implemented with a full crossbar (e.g., those that also tend to experience O(n^2) growth) are easy to implement if the individual agents also communicate in a full crossbar.
    • Communication cost are predictable.
    • There is no single point of failure in the resulting net of agents, assuming that failure of a single agent anywhere does not result in all agents becoming inoperable.
  • Disadvantages:
    • This is a worst-case for communications traffic, which is high and grows quadratically with the number of agents. It is particularly inappropriate in a WAN (e.g., on the Internet).
    • If every agent does depend on every other agent for the system as a whole to operate, then this multiplies the failure probability of the system as a whole.
    • If the algorithm requires global synchronization of all agents, then not only will a partition break it (see the point immediately above), but the speed of operation of the entire network will devolve to the speed of the slowest link between a pair of agents.
  Because of the many disadvantages of
• Random point-to-point
  This model is what is used in most email, and also describes Web client/server activity as well as that of the domain name system. It is probably the most common model.
  • Advantages:
    • Bandwidth is lower than a full crossbar solution.
    • Actual message traffic presumably reflects the current structuring of the problem. (For example, as used in the domain name system, only paths along [not across] the delegation trees are traversed, and only upon demand. Loose consistency and caching help make this the performance of the resulting system reasonable.)
  • Disadvantages:
    • If most agents nonetheless need to talk to most others, communications costs can approach that of a full crossbar solution. (This is the scaling problem with email lists that led, among other things, to Usenet news.)
    • It can be difficult to know if all peers have been found, or to find a particular peer.
• Broadcast/fill
  This model is used in Usenet news, and implies that some agents are willing to carry traffic that they themselves might not use, in order to facilitate its eventual transfer to a third-party agent. In Usenet news, each news node accepts all messages from its neighbors that it has not already received, regardless of whether it has local readers of those messages, and similarly passes these messages along to those neighbors which have not yet received them.
  • Advantages:
    • If most agents must see most of the traffic, yet loose consistency is all that is required, the resulting message traffic is much less than either random point-to-point or full crossbar solutions.
    • Assuming a reasonable connection mesh, the system is quite robust against even multiple failures of individual hosts or their communications links.
  • Disadvantages:
    • Latency of messaging can be high and quite variable.
    • It can be difficult or impossible to guarantee tight consistency for algorithms with require it. Even if high latency is tolerable in syncing the caches (which is doubtful in an application that requires tight consistency), Byzantine failures become more probable in this sort of architecture.
    • A single misbehaving host can effectively flood all hosts unless per-host throttles are in place.
    • Privacy must be achieved with encryption, because, by definition, many third parties will see any given message traffic.
    • Any solution must include duplicate-rejection and similar logic, or infinitely-circulating messages are guaranteed.
• Directed multicast
  This model is used in, e.g., the MBONE for transmission of realtime audio and especially video. It is also used in some multiplayer simulations (e.g., SGI Dog).
  • Advantages:
    • If the number of hosts involved is relatively low, this solution can use existing network bandwidth most efficiently than multipoint solutions.
    • This is an appropriate solution for discovery and bootstrapping of peer agents in an unknown network, when such discovery must cross LAN boundaries. (Ethernets, for example, support directed multicast across router segments, but do not support undirected broadcast across segments. Similarly, the Internet itself allows directed multicast without regard to network boundaries, but specifically disallows undirected broadcast propagation so as not to fill up the entire Internet with the sum total of all broadcasts in the world.)
  • Disadvantages:
    • Not all routers properly support directed multicast. This makes, e.g., the MBONE a dicey proposition in certain environments.
    • Directed multicast is a best-effort transmission medium, more similar to UDP and IP than it is to TCP. Hence, applications which require guaranteed and/or in-order delivery must implement their own protocols on top of multicasting to ensure correct reception.
    • If the number of agents involved is large, directed multicast ceases to be an efficient proposition, and some sort of broadcast/fill is more appropriate.
    • The IP address of all hosts to be communicated with must be known at the time of the multicast.
• Central hub
  This model is most common when there is only one central agent, acting as a server, to which numerous clients connect. This is the model of a Web server, for example.
  • Advantages:
    • Easy to analyze and maintain.
    • Algorithms are generally straightforward.
  • Disadvantages:
    • The central hub is a single point of both failure or compromise, and of overload.
    • Load on the central hub, in general, will increase quadratically with the number of agents/clients which must communicate with it or through it.
    • The central hub is likely to be a substantial fraction of a network diameter away from the majority of its users. This increases network load in adjacent network segments to the hub, and can also greatly increase latency for such clients and maybe all agents (if they are using the central hub to ensure tight consistency, for example, then their performance will degrade to that of the slowest link).

Previous | Up | Table of contents | Next