How to create simulator for distributed algorithms written in simple language

Question

I started development of simulator for simulation of distributed algorithms in language C. My work consist of creating simple language for algorithm description and simulator which takes the described algorithm and simulates it.

At first I decided how to represent distributed environment. This simulator will run on single machine so there was need to somehow simulate entities which create distributed environment and do some task according to provided algorithm. Every entity will be represented as data structure called Entity. This data structure will contain all data related to entity, for example state of the entity, local registers of the entity.

For representing topology and connections I want to use some library for graphs in C to represent topology as set of vertices and edges. This vertices and edges will certainly be part of Entity so it can get access it's neighbors for example when it is sending data to them.

Next step was to create simple language so user can easily describe the algorithm and simulate it.

For better depiction here is the example of algorithm flooding.

STATUS = INITIATOR, IDLE, DONE;
INIT = INITIATOR, IDLE;
TERM = DONE;
REGISTERS = ;

INITIATOR
  RANDOM
    begin
      SEND(x, NEIGHBORS);
      BECAME(DONE);
    end

IDLE
  RECEIVE(x)
    begin
      SEND(x, NEIGHBORS - SENDER)
      BECAME(DONE);
    end

At this stage I am working on specification for this language and I got stuck. I am not sure how to properly specify this language. It should be simple but when i for example want to implement command for sending message to another entity I must consider that targets may be various. Targets could be all neighbors or all neighbors except sender or maybe only sender or later in development it should by possible to declare specific target from all entities in environment.

At this point I have two options in mind.

First is using Flex and Bison to analyze and parse input. then gather all data needed and run threads and let them behave according to all possible behaviors in input file with algorithm.

Second option is not to use Flex and Bison and implement every command as C macro. User will use this macros to write input file with algorithm and this file will be linked to simulator with gcc compiler, so when user uses macro in wrong way the compiler will throw an error.

I would like to ask if someone was developing something similar or what kind of approach or technique to choose if exists. I want to implement it in C but maybe other language would be more better for this type of thing.

Answer 1

Why would you use lowest-possible level language, C, for an involved task like this? Or, rather, several tasks?

If I needed results quickly and painlessly, I'd take a purpose-built tool, like Erlang or Elixir, to run a distributed system. Upsides: these are used in real distributed systems, allow for crazy amounts of parallelism even on a single box, and have tracing / diagnostic / introspection tools to actually watch what's happening.

Write Erlang functions that map more or less straightforwardly to the elements of your input language, and you can start playing with systems even without any parsers.

Should you want somehow more performance at the cost of a significantly less expressive, but still easy language, take a look at Go. It handles concurrency well out of the box.

Writing a parser in C also looks counter-productive to me. A higher-level language, like Python, or Ruby, or even Java or Haskell, helps do this faster and more conveniently. Defining a parser using e.p. pyparsing and compiling your input language into Elixir or Erlang should be pretty easy, and way easier than doing something comparable in C.

What the layered approach would help with is doing one small, well-defined thing at a time. (An attempt to do everything at once is certain a way to failure, you know.)

Answer 2

If you're not sure whether you should us a real parser generator, then you should use it. Only eschew the real parser generators like Flex and Bison if you are utterly positive you don't need them.

Every language you write like this grows. It's the nature of the task at hand. Your language will grow. When it grows, if you used C macros, you'll have to fit that growth into the general syntax of the C language. If it grows with Flex or Bison you have parser generators that are literally designed to help you with this sort of growth.

Also, if someone messes up a C macro, the error messages can be horrendous and incomprehensible.

Also, if you have a language grammar handy, you're one step closer to permitting solutions like a Python script which generates content in your language.

The only cases I would personally use the C macro style language would be:

• If I needed to directly interact with the code (such as getting pointers to members and such), and for some reason could not use a more robust approach like reflection to expose those members
• I was operating on an embedded machine where every single byte matters.

Also, I would only use it if I was positive that I was 100% okay with every user of my software having to compile code to use my simulator.

If you really want to take advantage of the power of the C preprocessor, there are full grammars which will do the preprocessor step for you and then let you use lexx/bison/antlr/flex to process the results.

Answer 3

promela and spin if the point is to actually verify it. these are protocol simulation tools.