dans.algorithm

Class Algorithm

java.lang.Object

java.lang.Thread

dans.algorithm.Algorithm

All Implemented Interfaces:

java.lang.Runnable

Direct Known Subclasses:

BidirectionalLeaderElection, Broadcast, HelloWorld, HelloWorld2, LeaderElection, TreeLargestID, TreeSumID

public abstract class Algorithm
extends java.lang.Thread

This abstract class should be extended to create new algorithms to run in DANS. A algorithm() method must be provided that returns the results of the algorithm as a Java Object. This method should contain a main loop that runs until doMainLoop() returns false. For example:

 
 public Object algorithm() {
  //Setup anything needed for the algorithm
 
  while(doMainLoop) {
      //Do some calls to send and receive here.
  }
 
  //Running anything before the algorthim terminates
 
  return someResultHere
 }
 
 

Implementing classes should only reference or use classes or methods from the dans.algorithm and dans.utils packages. Use of any other class from the dans library can break the distributed algorithm model and/or the simulator. No methods in this class should be called in the constructor of implementing child classes. Doing so will result in a null value or equivalent being returned and possible exceptions. This may also break the simulation.

Version:

0.1beta

Author:

Daniel Servos

Nested Class Summary

Nested classes/interfaces inherited from class java.lang.Thread

java.lang.Thread.State, java.lang.Thread.UncaughtExceptionHandler

Field Summary

Fields

Modifier and Type	Field and Description
static int	FAIL_BYZAN A Byzantine failure has occurred.
static int	FAIL_CLEAN A clean failure has occurred.
static int	FAIL_NONE No failure has occurred.

Fields inherited from class java.lang.Thread

MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY

Constructor Summary

Constructors

Constructor and Description
Algorithm()

Method Summary

Modifier and Type	Method and Description
abstract java.lang.Object	algorithm() This method should be overridden by any implementing child class.
void	display(java.lang.String text) Displays some text above the processor in the GUI front-end.
void	display(java.lang.String text, int pos) Displays some text above or below the processor in the GUI front-end.
boolean	doMainLoop() This method should be checked once per cycle of the main loop in the algorithm() method.
void	fail() Causes the algorithm to experience a clean failure.
void	fail(boolean clean) Causes the algorithm to experience a failure.
int	getDefaultPort() Gets the default port number for the simulation.
int	getFailType() Gets a value indicating how this algorithm failed.
java.lang.String	getID() Gets the ID of the processor the algorithm is running on.
double	getLinkBandwidth(java.lang.String linkID) Gets the bandwidth of a given link.
int	getLinkDelay(java.lang.String linkID) Gets the delay of the given link.
java.lang.String[]	getLinks() Gets the set of directional links leaving this processor.
java.util.concurrent.ConcurrentHashMap<java.lang.String,java.lang.Object>	getMemory() Gets a reference to a ConcurrentHashMap that represents the shared memory of the processor the algorithm is running on.
java.lang.String	getNeighborDownLink(java.lang.String linkID) Finds the neighbor that a given link points to.
java.lang.String[]	getNeighbors() Gets the set of neighbors for this processor.
java.lang.String	getNeighborsLink(java.lang.String neighborID) Finds a link pointing to the given neighbor.
int	getPort() Gets the port the algorithm is listening on.
java.lang.String[]	getSourceLinks() Gets the set of links that point to this processor.
java.lang.String[]	getSources() Gets the set of processors that have a directional link to this processor.
java.lang.String	getStatus() Gets the current status of the algorithm.
int	getTick() Gets the current tick the simulation is on.
boolean	hasLink(java.lang.String linkID) Checks if the processor has a link with the given ID.
boolean	hasNeighbor(java.lang.String neighborID) Checks if the processor has a neighbor with the given ID.
boolean	isRoot() Deprecated. this method does not currently work correctly with the front-end.
void	pause() This method causes the algorithm to be paused.
void	print(java.lang.String msg) Writes some text to the log.
Message	receive() Returns the next message in the message buffer (the message input queue).
Message	receive(boolean asynchronous) Returns the next message in the message buffer (the message input queue).
void	run() This is an internal method that should not be called directly.
boolean	send(Message msg) Sends the given message.
boolean	send(java.lang.String id, java.lang.String msg) Sends the given message to a processor with the given ID.
boolean	send(java.lang.String id, java.lang.String msg, int port) Sends the given message to a processor with the given ID on the given port.
boolean	sendLink(java.lang.String linkID, java.lang.String msg) Sends the given message down the link with the given ID.
boolean	sendLink(java.lang.String linkID, java.lang.String msg, int port) Sends the given message down the link with the given ID on the given port.
void	terminate() Causes this algorithm to terminate cleanly and for doMainLoop() to return false the next time it is called.
void	unpause() This method causes the algorithm to be unpaused.

Methods inherited from class java.lang.Thread

activeCount, checkAccess, clone, countStackFrames, currentThread, destroy, dumpStack, enumerate, getAllStackTraces, getContextClassLoader, getDefaultUncaughtExceptionHandler, getId, getName, getPriority, getStackTrace, getState, getThreadGroup, getUncaughtExceptionHandler, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, join, join, join, resume, setContextClassLoader, setDaemon, setDefaultUncaughtExceptionHandler, setName, setPriority, setUncaughtExceptionHandler, sleep, sleep, start, stop, stop, suspend, toString, yield

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

FAIL_NONE

public static final int FAIL_NONE

No failure has occurred.

See Also:

Constant Field Values

FAIL_CLEAN

public static final int FAIL_CLEAN

A clean failure has occurred.

See Also:

Constant Field Values

FAIL_BYZAN

public static final int FAIL_BYZAN

A Byzantine failure has occurred.

See Also:

Constant Field Values

Constructor Detail

Algorithm

public Algorithm()

Method Detail

getMemory

public java.util.concurrent.ConcurrentHashMap<java.lang.String,java.lang.Object> getMemory()

Gets a reference to a ConcurrentHashMap that represents the shared memory of the processor the algorithm is running on. This shared memory object allows algorithms on the same processor to communicate and share resources. While the HashMap its self is thread safe it is up to the algorithm to ensure any objects or values stored in the HashMap are properly synchronized.

Returns:

a ConcurrentHashMap instance that is shared with all other algorithms running on the same processor.

getFailType

public int getFailType()

Gets a value indicating how this algorithm failed.

Returns:

one of FAIL_NONE, FAIL_CLEAN, or FAIL_BYZAN.

getTick

public final int getTick()

Gets the current tick the simulation is on.

Returns:

the current tick value.

getDefaultPort

public final int getDefaultPort()

Gets the default port number for the simulation. This is not necessarily the port the algorithm is listening on. Use getPort() to find the port the algorithm is listening on.

Returns:

a port number.

See Also:

getPort()

getPort

public final int getPort()

Gets the port the algorithm is listening on. The algorithm will only receive messages sent to the processor on this port.

Returns:

a port number.

getLinkBandwidth

public final double getLinkBandwidth(java.lang.String linkID)

Gets the bandwidth of a given link. Returns -1 if there is no link from this processor to another with the given ID.

Parameters:

linkID - a link ID.

Returns:

the bandwidth of the link in messages per tick or -1.

getLinkDelay

public final int getLinkDelay(java.lang.String linkID)

Gets the delay of the given link. Returns -1 if there is no link from this processor to another with the given ID.

Parameters:

linkID - a link ID.

Returns:

the delay of the link in ticks or -1.

hasNeighbor

public final boolean hasNeighbor(java.lang.String neighborID)

Checks if the processor has a neighbor with the given ID. A neighbor is considered to be a processor that the current processor has a directional link to. Processors that have a directional link to this processor but this processor does not have a directional link back to are NOT counted as neighbors.

Parameters:

neighborID - the processor ID to check.

Returns:

true if the processor has a directional link to the given processor. Otherwise false.

See Also:

hasLink(java.lang.String)

hasLink

public final boolean hasLink(java.lang.String linkID)

Checks if the processor has a link with the given ID. Only links leaving from this processor to another are considered.

Parameters:

linkID - the link ID to check.

Returns:

true if the processor has a link with the given ID. Otherwise false.

See Also:

hasNeighbor(java.lang.String)

getNeighborDownLink

public final java.lang.String getNeighborDownLink(java.lang.String linkID)

Finds the neighbor that a given link points to.

Parameters:

linkID - the ID of the link to find a processor down.

Returns:

a processor ID for the processor this link points to or null if the link could not be found.

See Also:

getNeighborsLink(java.lang.String)

getNeighborsLink

public final java.lang.String getNeighborsLink(java.lang.String neighborID)

Finds a link pointing to the given neighbor.

Parameters:

neighborID - the ID of the neighbor to find a link to.

Returns:

a link ID or null if no such link could be found.

See Also:

getNeighborDownLink(java.lang.String)

getNeighbors

public final java.lang.String[] getNeighbors()

Gets the set of neighbors for this processor. A neighbor is considered to be a processor that the current processor has a directional link to. Processors that have a directional link to this processor but this processor does not have a directional link back to are NOT counted as neighbors.

Returns:

an array of processor IDs.

See Also:

getLinks()

getLinks

public final java.lang.String[] getLinks()

Gets the set of directional links leaving this processor. This does not include links that only point to this processor.

Returns:

an array of link IDs.

See Also:

getNeighbors()

getSources

public final java.lang.String[] getSources()

Gets the set of processors that have a directional link to this processor. This is not necessarily the same as set returned by getNeighbors() as it only includes processors that have a link TO this processor and not necessarily FROM this processor. If the network is setup in a directional tree such that all child processor point to their parent, this set would contain the children of the processor.

Returns:

an array of processor IDs.

See Also:

getNeighbors(), getSourceLinks()

getSourceLinks

public final java.lang.String[] getSourceLinks()

Gets the set of links that point to this processor. This set does not include any links FROM this processor TO other processors, only directional links that point TO this processor.

Returns:

an array of link IDs.

See Also:

getSources(), getLinks()

getID

public final java.lang.String getID()

Gets the ID of the processor the algorithm is running on. This ID is not guaranteed to be an Integer or even a number. Note that the function getId() (with a lower case 'd') is not the same as this function and should not be used.

Returns:

the ID of the processor.

isRoot

public final boolean isRoot()

Deprecated. this method does not currently work correctly with the front-end.

Checks if this processor is set as the root of the network graph. Currently this feature is not supported in the GUI front-end so this function should not be used. Instead the ID of the root processor should be set to something like "root" and getID() should be used to check if the processor has this ID.

Returns:

true if the processor is set as the root. Otherwise false.

See Also:

getID()

algorithm

public abstract java.lang.Object algorithm()

This method should be overridden by any implementing child class. It is called when the processor is started and should contain a loop that runs until doMainLoop() returns false. If the algorithm is finished it can break or return out of this loop immediately with out checking doMainLoop(). All calls to send(dans.algorithm.Message) and receive() should be contained in such a loop. A value maybe returned and will be displayed next to the node in the front-end when the algorithm terminates. Otherwise null can be returned. See the description of the Algorithm class for more details. This method should not be called directly, just overridden by a child class.

Returns:

any value with a toString method or null.

See Also:

Algorithm

run

public final void run()

This is an internal method that should not be called directly.

Specified by:

run in interface java.lang.Runnable

Overrides:

run in class java.lang.Thread

getStatus

public final java.lang.String getStatus()

Gets the current status of the algorithm. This method is not intended to be called from a child class.

Returns:

a string containing the status of the algorithm.

print

public final void print(java.lang.String msg)

Writes some text to the log. This is a thread safe way for the algorithm to output text to the console and logging system. This method should be used in place of System.out.print or System.out.println.

Parameters:

msg - the text to be written to the log.

See Also:

display(java.lang.String)

display

public final void display(java.lang.String text)

Displays some text above the processor in the GUI front-end. The text should be short.

Parameters:

text - the text to display.

See Also:

print(java.lang.String), display(java.lang.String, int)

display

public final void display(java.lang.String text,
                          int pos)

Displays some text above or below the processor in the GUI front-end. If a pos of 0 is given the text will be displayed above the processor, if a pos of 1 is given the text will be displayed under the processor. Note that the result of the algorithm will overwrite any text displayed under the processor when the algorithm terminates. The text should be short.

Parameters:

text - the text to display.

pos - the position to display the text in. 0 for above, 1 for below, any other value is equivalent to calling print(java.lang.String).

See Also:

print(java.lang.String), display(java.lang.String)

send

public final boolean send(Message msg)

Sends the given message. This should be a new and unsent Message object. The Message object must contain either a processor ID or link ID to send the message to. This method does NOT block or wait for the message to be delivered. Depending on the failure settings delivery is not necessarily guaranteed. This method returning true does not necessarily guarantee the message was delivered.

Parameters:

msg - a new Message object that has not been sent.

Returns:

true if the message was successfully added to the links output queue. Otherwise false if the send operation fails (e.g. if there is no link from this processor to one with the given processor ID).

See Also:

Message, send(java.lang.String, java.lang.String), send(java.lang.String, java.lang.String, int), sendLink(java.lang.String, java.lang.String), sendLink(java.lang.String, java.lang.String, int)

send

public final boolean send(java.lang.String id,
                          java.lang.String msg)

Sends the given message to a processor with the given ID. This method does NOT block or wait for the message to be delivered. Depending on the failure settings delivery is not necessarily guaranteed. This method returning true does not necessarily guarantee the message was delivered.

Parameters:

id - the ID of the processor to send the message to.

msg - the message to send to the processor.

Returns:

true if the message was successfully added to the links output queue. Otherwise false if the send operation fails (e.g. if there is no link from this processor to one with the given processor ID).

See Also:

send(dans.algorithm.Message), send(java.lang.String, java.lang.String, int), sendLink(java.lang.String, java.lang.String), sendLink(java.lang.String, java.lang.String, int)

send

public final boolean send(java.lang.String id,
                          java.lang.String msg,
                          int port)

Sends the given message to a processor with the given ID on the given port. Specifying a port allows this algorithm to send messages to algorithms running on different ports on different processors. This method does NOT block or wait for the message to be delivered. Depending on the failure settings delivery is not necessarily guaranteed. This method returning true does not necessarily guarantee the message was delivered.

Parameters:

id - the ID of the processor to send the message to.

msg - the message to send to the processor.

port - the port to send the message to on the receiving processor.

Returns:

true if the message was successfully added to the links output queue. Otherwise false if the send operation fails (e.g. if there is no link from this processor to one with the given processor ID).

See Also:

send(dans.algorithm.Message), send(java.lang.String, java.lang.String), sendLink(java.lang.String, java.lang.String), sendLink(java.lang.String, java.lang.String, int)

sendLink

public final boolean sendLink(java.lang.String linkID,
                              java.lang.String msg)

Sends the given message down the link with the given ID. This method does NOT block or wait for the message to be delivered. Depending on the failure settings delivery is not necessarily guaranteed. This method returning true does not necessarily guarantee the message was delivered.

Parameters:

linkID - the ID of the link to send the message down.

msg - the message to send down the link.

Returns:

true if the message was successfully added to the links output queue. Otherwise false if the send operation fails (e.g. if there is no link from this processor with the given link ID).

See Also:

send(dans.algorithm.Message), send(java.lang.String, java.lang.String), send(java.lang.String, java.lang.String, int), sendLink(java.lang.String, java.lang.String, int)

sendLink

public final boolean sendLink(java.lang.String linkID,
                              java.lang.String msg,
                              int port)

Sends the given message down the link with the given ID on the given port. Specifying a port allows this algorithm to send messages to algorithms running on different ports on different processors. This method does NOT block or wait for the message to be delivered. Depending on the failure settings delivery is not necessarily guaranteed. This method returning true does not necessarily guarantee the message was delivered.

Parameters:

linkID - the ID of the link to send the message down.

msg - the message to send down the link.

port - the port to send the message to on the receiving processor.

Returns:

true if the message was successfully added to the links output queue. Otherwise false if the send operation fails (e.g. if there is no link from this processor with the given link ID).

See Also:

send(dans.algorithm.Message), send(java.lang.String, java.lang.String), send(java.lang.String, java.lang.String, int), sendLink(java.lang.String, java.lang.String)

receive

public final Message receive()

Returns the next message in the message buffer (the message input queue). This method does not block or wait for messages and returns immediately. At most one message will be returned with each call to receive.

Returns:

a message sent to this processor/algorithm or null if the message buffer is empty (no more messages to get).

See Also:

Message, receive(boolean)

receive

public final Message receive(boolean asynchronous)

Returns the next message in the message buffer (the message input queue). Depending on the value given to this method it will either return immediately or block/wait until a message is received. If the method waits, it will sleep and disregard the tick system. There is no guarantee the algorithm will ever wake before it is terminated (e.g. if no message is sent to the processor). After the algorithm wakes and a message is returned it will resume running at a speed dictated by the tick system.

Parameters:

asynchronous - if true the method will return immediately and function like receive(). If false the method will block/wait until a message is received.

Returns:

a message sent to this processor/algorithm or null if the message buffer is empty (no more messages to get).

See Also:

Message, receive()

doMainLoop

public final boolean doMainLoop()

This method should be checked once per cycle of the main loop in the algorithm() method. The main loop should be terminated if this function returns false. This method both ensures that the algorithm is running at the speed dictated by the tick system and updates dictated about the algorithm. It also allows the simulation to be paused/restarted and handles failures. See Algorithm for more details and an example of its use.

Returns:

false if the algorithm's main loop should be terminated. Otherwise true.

See Also:

Algorithm

terminate

public final void terminate()

Causes this algorithm to terminate cleanly and for doMainLoop() to return false the next time it is called. Commands after calling terminate will still be executed.

unpause

public final void unpause()

This method causes the algorithm to be unpaused. This method should not be called by a child of the Algorithm class.

pause

public final void pause()

This method causes the algorithm to be paused. This method should not be called by a child of the Algorithm class.

fail

public final void fail()

Causes the algorithm to experience a clean failure. All messages will be sent and then the algorithm will be terminated. This should not be called to simply terminate the algorithm, the terminate() method should be used for that purpose. This method should only be used to simulate a clean failure.

See Also:

terminate()

fail

public final void fail(boolean clean)

Causes the algorithm to experience a failure. The type of failure depends on the value passed to the method. If a clean failure is chosen all messages will be sent and then the algorithm will be terminated. If a unclean failure is chosen no guarantee is made that this method will send all messages before it terminates. This method should not be called by a child of the Algorithm class.

Parameters:

clean - true if it is a clean failure. Otherwise false.