2006-12-29

Concurrency Comparison

Coarse: Very large stacks (often several MiB, but may be dropped to around 10 KiB if the usage is predictable enough). Uses a lot of kernel resources. Significant costs in switching between them.
  • Processes: Transferring data between them is expensive. Effective for specific, independent operations. Allows low-level failures or corruption (which leads to crashes) to be isolated.
  • Preemptive threads: Shared, mutable, non-atomic data structures. Independent operations can be done in a straightforward manner, but it's very hard to ensure they really are independent, and mistakes are very hard to detect. Somewhat effective for specific, independent operations, but tends to be used more generally.
  • Cooperative threads with deep stacks: Doesn't scale to multiple CPUs. Easier to program with than preemptive threads, but possible to trigger a switch while in a function that does not expect it. Not obvious to the programmer where switching may occur.

Fine: Very small stacks (could be a few hundred bytes, or a lot more if not optimized by the language). Uses no kernel resources. Cheap to switch between them.
  • Coroutines: Can be used to implement Fine cooperative threads (and a few other things). More of a low-level tool than a high-level tool.
  • Generator-based tasks: Doesn't scale to multiple CPUs. Easy to use and switching locations are obvious, but can't cooperate with existing libraries that are not already designed to be asynchronous.
  • Event-driven state machines: Doesn't scale to multiple CPUs. Confusing spaghetti code. Doesn't require any special language features.
  • Erlang-style "processes": Scales to multiple CPUs. Interactions are easy and predictable. As a predominantly functional language, it is unpopular with those who would prefer a more imperative style.

It should be fairly obvious no single style is optimal in all situations. I believe a selection of complementary approaches is ideal, which I've explained in my previous post, Ideal Threading Model.

2006-12-18

Securely Establishing Wireless Connections

Current wireless mechanisms are very insecure. They either offer no security or securing them properly requires so much effort as to rarely be done properly. I propose a mechanism that would solve this.

In the most basic form, a person would touch two devices together (on specified contact points), and simultaneously press each of their connect buttons. Once done the devices could be separated, and would communicate securely as if there was a physical wire running between them.

Moving the devices in order to make a connection may be impractical, especially for larger devices such as a television. To connect them you would want to use an intermediary device, called a “wand”, with which you would first establish connections to both desired devices, then use these connections to instruct them to connect directly to each other. However, since this implies each device may have more than one connection, it requires a further mechanism to prevent a visitor from establishing connections and then surreptitious controlling or snooping on your devices.

The security of the basic form is done by exchanging public keys in a rapid burst, fast enough and carefully timed so as to ensure both ends are in very close proximity to each other (preferably a few centimeters, if not closer). A randomly generated number would be integrated into this key exchange protocol to prevent attackers from trying to send preemptive messages before they detect the communication.

This would not protect against tampering with the devices, including putting a false front on one of them.