General Glossary

• [API]Application Program Interface: the syntactical one way description of an interface. An API typically says which functions can be called with which arguments and what will be returned. An API describes in a formal way how functions should be called. Together with this it can also describe what a function does in an informal way. We do not consider informal documentation to be part of the API.
• [asynchronous]In this dissertation we will use the term asynchronous to specify the behavior of a component that sends messages, without waiting for the return value from another component. This should not to be confused with non-blocking. It is clear that an asynchronous working client uses non-blocking primitives, however, not all non-blocking messages will result in an asynchronous working component.
• [behavior]The behavior of a component is the result of its internal programming. Typically the behavior of a component can be seen by looking at the message flow over its interface, however the exact program describing the behavior exactly is unknown.
• [blocking]Call and wait for return value.
• [call]a call is sending a request to another object or component and waiting for the answer. Calls always return a value (which possibly can be void)
• [component]A component is a process that can only communicate with other components by means of messages. Components do not share code and or data.
• [client]in this dissertation, a client is a component that requires a certain concurrency strategy from another component to be able to do its work.
• [component system]To be able to run components one needs the infrastructure that allows communication, naming and multitasking. This infrastructure is called the component system.
• [conflicting interface]Given a) two interfaces and b) an external (not specified in the interface) agreement on the expected behavior between the involved components, then these two interfaces are in conflict if this external behavior cannot be executed on the link between the two interfaces. For instance, a conflict might arise when a message cannot be understood by one of the involved components, or if a message will exhibit other behavior than the expected behavior, or simply if a sequence of actions leads to corruption of the internal state of the involved components.
• [co-NP]A problem $p$ is co-NP if $\neg p$ is NP. co-NP problems often seem harder than NP problems, however it is still an open question whether co-NP = NP.
• [event]See message.
• [EXPTIME]A problem of size $n$ is EXPTIME if there is a constant $c$ and the time to solve the problem takes at most $2^{n^{c}}$.
• [EXPTIME-complete]A problem is EXPTIME-complete if it is EXPTIME and other EXPTIME problems are reducible to it. Essentially this declares a class of problems which can be solved within exponential time. It is known that EXPTIME $\not=$ PTIME.
• [interface]An interface is a connection-point to a component. It is the only means to alter the internal state and/or the behavior of the component. In the component system interfaces are embodied under the form of ports which can be connected to other components.
• [machine]The term machine is used to refer to Turing machines.
• [message]A piece of data used to communicate between components. A message can be sent to another component or it can be received. Message never share data. Also called event.
• [multi-multi]A multi on multi interface conflict is a conflict between a number of interface providing components and a number of interface requiring components. This typically occurs in peer to peer systems.
• [non-blocking]Send a message and don't wait for an answer.
• [non-deterministic]A machine is non-deterministic if it may execute different branches parallel on the same input.
• [NP]A problem is NP if it can be solved in polynomial time by a nondeterministic machine.
• [NP-complete]A problem is NP-complete if other NP-complete problems can be reduced to it.
• [one-one]A one on one interface conflict is a conflict between two components. Typically one component is a server, the other component is a client.
• [one-multi]A one on multi interface conflict is a conflict between one server component and a number of client components.
• [process]A process is a program which is running in a separate code and data space. Processes can have multiple threads.
• [P]A problem of size $n$ is P if there is a constant $c$ and the time to solve the problem is at most $n^{c}$.
• [P-complete]A problem is P-complete if it is in P and other P-problems are reducible to it.
• [P-hard]A problem is P-hard if itself is not necessarily in P but other P-problems may reduce to it.
• [server]In this dissertation, a server is a component that provides a concurrency strategy towards a number of clients.
• [thread]A thread is an execution environment that runs in a process. A process can consist of multiple threads.
• [whiteboard]A typical application in distributed systems where many users join a place to discuss. Every user has a view on the shared data and can modify this as necessary. All other users will see those changes. A whiteboard is a tool in a group discussion system.