# HG changeset patch
# User suikwasha
# Date 1350572741 -32400
# Node ID 38a110b13db1103ff730a5f300fe29ca5ec918e3
added SimpleDistributedAlgorithmFramework.
added NaiveAlgorithm
added ChangRobertsAlgorithm
added PertersonAlgorithm
diff -r 000000000000 -r 38a110b13db1 pom.xml
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/pom.xml Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,30 @@
+
+ 4.0.0
+
+ suikwasha
+ distributedalgorithm
+ 0.0.1-SNAPSHOT
+ jar
+
+ distributedalgorithm
+ http://maven.apache.org
+
+
+ UTF-8
+
+
+
+
+ junit
+ junit
+ 3.8.1
+ test
+
+
+ org.functionaljava
+ functionaljava
+ 3.0
+
+
+
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/App.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/App.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,13 @@
+package suikwasha.distributedalgorithm;
+
+/**
+ * Hello world!
+ *
+ */
+public class App
+{
+ public static void main( String[] args )
+ {
+ System.out.println( "Hello World!" );
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/algorithms/cr/ChangRoberts.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/algorithms/cr/ChangRoberts.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,30 @@
+package suikwasha.distributedalgorithm.algorithms.cr;
+
+import java.util.LinkedList;
+
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.link.ReliableLinkBuilder;
+import suikwasha.distributedalgorithm.machines.SimpleMachineBuilder;
+import suikwasha.distributedalgorithm.simulator.Simulator;
+import suikwasha.distributedalgorithm.simulator.Summary;
+import suikwasha.distributedalgorithm.topologies.RingTopologyBuilder;
+
+public class ChangRoberts
+{
+ public static void main(String _args[]) throws InterruptedException
+ {
+ LinkedList algoList = new LinkedList();
+
+ for(long num = 0;num <= 40;num ++){
+ algoList.add(new ChangRobertsAlgorithm(num));
+ }
+
+ ReliableLinkBuilder linkBuilder = new ReliableLinkBuilder();
+ SimpleMachineBuilder machineBuilder = new SimpleMachineBuilder();
+ RingTopologyBuilder ringBuilder = new RingTopologyBuilder();
+
+ Simulator sim = new Simulator(algoList,linkBuilder,machineBuilder,ringBuilder);
+ Summary sum = sim.startSimulation();
+ sum.print();
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/algorithms/cr/ChangRobertsAlgorithm.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/algorithms/cr/ChangRobertsAlgorithm.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,79 @@
+package suikwasha.distributedalgorithm.algorithms.cr;
+
+import java.nio.ByteBuffer;
+import java.util.Iterator;
+
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.framework.Context;
+import suikwasha.distributedalgorithm.framework.Message;
+import suikwasha.distributedalgorithm.framework.Port;
+
+public class ChangRobertsAlgorithm implements Algorithm
+{
+ private final long num;
+ private long max;
+
+ public ChangRobertsAlgorithm(long _num)
+ {
+ max = -1;
+ num = _num;
+ }
+
+ public static ByteBuffer toByteBuffer(boolean _max,long _value)
+ {
+ ByteBuffer b = ByteBuffer.allocate(9); // size of (flagbit + long)
+ if(_max){
+ b.put((byte)1);
+ }else{
+ b.put((byte)0);
+ }
+
+ b.putLong(_value);
+ b.rewind(); // do not forget rewind() after reading/writing
+ return b.asReadOnlyBuffer(); // message is read-only
+ }
+
+ public void execute(Context _c)
+ {
+ Iterator ports = _c.getPorts().iterator();
+ Port receiving = ports.next();
+ Port sending = ports.next();
+
+ max = num;
+ Message newMessage = new Message(toByteBuffer(false,max));
+ sending.send(newMessage);
+
+ while(true){
+ Message receivedMessage = null;
+ try{
+ receivedMessage = receiving.blockingReceive();
+ }catch(InterruptedException _e){
+ _e.printStackTrace();
+ }
+
+ ByteBuffer b = receivedMessage.getMessage();
+ byte flagMax = b.get();
+ long value = b.getLong();
+ if(flagMax == (byte)1){
+ // maximum value detected.
+ newMessage = receivedMessage.newMessage(toByteBuffer(true,value));
+ sending.send(newMessage);
+ //stop
+ return;
+ }else{
+ if(value == max){
+ newMessage = receivedMessage.newMessage(toByteBuffer(true,max));
+ sending.send(newMessage);
+ //stop
+ return;
+ }
+ if(value > max){
+ max = value;
+ newMessage = receivedMessage.newMessage(toByteBuffer(false,max));
+ sending.send(newMessage);
+ }
+ }
+ }
+ }
+
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/algorithms/naive/Naive.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/algorithms/naive/Naive.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,34 @@
+package suikwasha.distributedalgorithm.algorithms.naive;
+
+import java.util.LinkedList;
+
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.link.ReliableLinkBuilder;
+import suikwasha.distributedalgorithm.machines.SimpleMachineBuilder;
+import suikwasha.distributedalgorithm.simulator.Simulator;
+import suikwasha.distributedalgorithm.simulator.Summary;
+import suikwasha.distributedalgorithm.topologies.RingTopologyBuilder;
+
+public class Naive
+{
+ public static void main(String _args[]) throws InterruptedException
+ {
+ LinkedList algoList = new LinkedList();
+
+ long num = 1;
+ algoList.add(new NaiveStartAlgorithm(num));
+
+ num ++;
+ for(;num <= 40;num ++){
+ algoList.add(new NaiveStandbyAlgorithm(num));
+ }
+
+ ReliableLinkBuilder linkBuilder = new ReliableLinkBuilder();
+ SimpleMachineBuilder machineBuilder = new SimpleMachineBuilder();
+ RingTopologyBuilder ringBuilder = new RingTopologyBuilder();
+
+ Simulator sim = new Simulator(algoList,linkBuilder,machineBuilder,ringBuilder);
+ Summary sum = sim.startSimulation();
+ sum.print();
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/algorithms/naive/NaiveStandbyAlgorithm.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/algorithms/naive/NaiveStandbyAlgorithm.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,78 @@
+package suikwasha.distributedalgorithm.algorithms.naive;
+
+import java.util.Iterator;
+
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.framework.Context;
+import suikwasha.distributedalgorithm.framework.Message;
+import suikwasha.distributedalgorithm.framework.Port;
+
+import static suikwasha.distributedalgorithm.algorithms.naive.NaiveStartAlgorithm.toByteBuffer;
+
+/*
+ * this standby algorithm for NAIVE using UnidirectedRing
+ * Port1 : receiving only
+ * Port2 : sending only
+ */
+public class NaiveStandbyAlgorithm implements Algorithm
+{
+ private long max;
+ private final long num;
+
+ public NaiveStandbyAlgorithm(long _num)
+ {
+ max = -1;
+ num = _num;
+ }
+
+ public long getValue()
+ {
+ return max;
+ }
+
+ public void execute(Context _c)
+ {
+ Iterator ports = _c.getPorts().iterator();
+ Port receiving = ports.next();
+ Port sending = ports.next();
+
+ Message receivedMessage = null;
+ try{
+ receivedMessage = receiving.blockingReceive();
+ }catch(InterruptedException _e){
+ Thread.currentThread().interrupt();
+ _e.printStackTrace();
+ }
+
+ long value = receivedMessage.getMessage().getLong();
+ max = Math.max(num,max);
+
+ Message m1 = receivedMessage.newMessage(toByteBuffer(num));
+ Message m2 = receivedMessage.newMessage(toByteBuffer(value));
+
+ sending.send(m1);
+ sending.send(m2);
+
+ while(true){
+ try{
+ receivedMessage = receiving.blockingReceive();
+ }catch(InterruptedException _e){
+ _e.printStackTrace();
+ Thread.currentThread().interrupt();
+ return;
+ }
+
+ value = receivedMessage.getMessage().getLong();
+ if(max == value){
+ Message newMessage = receivedMessage.newMessage(toByteBuffer(max));
+ sending.send(newMessage);
+ return;
+ }
+
+ max = Math.max(max,value);
+ Message newMessage = receivedMessage.newMessage(toByteBuffer(value));
+ sending.send(newMessage);
+ }
+ }
+
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/algorithms/naive/NaiveStartAlgorithm.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/algorithms/naive/NaiveStartAlgorithm.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,73 @@
+package suikwasha.distributedalgorithm.algorithms.naive;
+
+
+import java.nio.ByteBuffer;
+import java.util.Iterator;
+
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.framework.Context;
+import suikwasha.distributedalgorithm.framework.Message;
+import suikwasha.distributedalgorithm.framework.Port;
+
+/*
+ * this start algorithm for NAIVE using UnidirectedRing
+ * Port1 : receiving only
+ * Port2 : sending only
+ */
+public class NaiveStartAlgorithm implements Algorithm
+{
+ private long max;
+ private final long num;
+
+ public NaiveStartAlgorithm(long _num)
+ {
+ max = -1;
+ num = _num;
+ }
+
+ public long getValue()
+ {
+ return max;
+ }
+
+ public static ByteBuffer toByteBuffer(long _value)
+ {
+ ByteBuffer b = ByteBuffer.allocate(8); // size of long in java
+ b.putLong(_value);
+ b.rewind(); // do not forget rewind() after reading/writing
+ return b.asReadOnlyBuffer(); // message is read-only
+ }
+
+ public void execute(Context _c)
+ {
+ Iterator ports = _c.getPorts().iterator();
+ Port receiving = ports.next();
+ Port sending = ports.next();
+
+ max = num;
+ Message firstMessage = new Message(toByteBuffer(num));
+ sending.send(firstMessage);
+
+ while(true){
+ Message receivedMessage;
+ try{
+ receivedMessage = receiving.blockingReceive();
+ }catch(InterruptedException _e){
+ _e.printStackTrace();
+ Thread.currentThread().interrupt();
+ return;
+ }
+
+ long value = receivedMessage.getMessage().getLong();
+ if(max == value){
+ Message newMessage = receivedMessage.newMessage(toByteBuffer(max));
+ sending.send(newMessage);
+ return;
+ }
+
+ max = Math.max(max,value);
+ Message newMessage = receivedMessage.newMessage(toByteBuffer(value));
+ sending.send(newMessage);
+ }
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/algorithms/peterson/Perterson.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/algorithms/peterson/Perterson.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,31 @@
+package suikwasha.distributedalgorithm.algorithms.peterson;
+
+import java.util.LinkedList;
+
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.link.ReliableLinkBuilder;
+import suikwasha.distributedalgorithm.machines.SimpleMachineBuilder;
+import suikwasha.distributedalgorithm.simulator.Simulator;
+import suikwasha.distributedalgorithm.simulator.Summary;
+import suikwasha.distributedalgorithm.topologies.RingTopologyBuilder;
+
+public class Perterson
+{
+ public static void main(String _args[]) throws InterruptedException
+ {
+ LinkedList algoList = new LinkedList();
+
+ for(long num = 0;num <= 10;num ++){
+ algoList.add(new PertersonAlgorithm(num));
+ }
+
+ ReliableLinkBuilder linkBuilder = new ReliableLinkBuilder();
+ SimpleMachineBuilder machineBuilder = new SimpleMachineBuilder();
+ RingTopologyBuilder ringBuilder = new RingTopologyBuilder();
+
+ Simulator sim = new Simulator(algoList,linkBuilder,machineBuilder,ringBuilder);
+ Summary sum = sim.startSimulation();
+ sum.print();
+ }
+
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/algorithms/peterson/PertersonAlgorithm.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/algorithms/peterson/PertersonAlgorithm.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,123 @@
+package suikwasha.distributedalgorithm.algorithms.peterson;
+
+import java.nio.ByteBuffer;
+import java.util.Iterator;
+
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.framework.Context;
+import suikwasha.distributedalgorithm.framework.Message;
+import suikwasha.distributedalgorithm.framework.Port;
+
+public class PertersonAlgorithm implements Algorithm
+{
+ private final long num;
+ private long max;
+
+ public PertersonAlgorithm(long _num)
+ {
+ max = -1;
+ num = _num;
+ }
+
+ public static ByteBuffer toByteBuffer(boolean _max,long _value)
+ {
+ ByteBuffer b = ByteBuffer.allocate(9); // size of (flag + long)
+ if(_max){
+ b.put((byte)1);
+ }else{
+ b.put((byte)0);
+ }
+
+ b.putLong(_value);
+ b.rewind(); // do not forget rewind() after reading/writing
+ return b.asReadOnlyBuffer(); // message is read-only
+ }
+
+ public void execute(Context _c)
+ {
+ Iterator ports = _c.getPorts().iterator();
+ Port in = ports.next();
+ Port out = ports.next();
+
+ /*
+ * Active
+ */
+
+ long temp = num;
+ out.send(new Message(toByteBuffer(false,temp)));
+
+ Message receivedMessage = null;
+ try{
+ receivedMessage = in.blockingReceive();
+ }catch(InterruptedException _e){
+ _e.printStackTrace();
+ }
+
+ ByteBuffer b = receivedMessage.getMessage();
+ long next = -1;
+ if(b.get() == (byte)0){
+ next = b.getLong();
+ }else{
+ System.out.println("b.get() != 0");
+ }
+
+ Message newMessage;
+ while(temp != next){
+ newMessage = receivedMessage.newMessage(toByteBuffer(false,next));
+ out.send(newMessage);
+ try{
+ receivedMessage = in.blockingReceive();
+ }catch(InterruptedException _e){
+ _e.printStackTrace();
+ }
+ long nnext = -1;
+ b = receivedMessage.getMessage();
+ if(b.get() == (byte)0){
+ nnext = b.getLong();
+ }
+ if(next < Math.max(temp,nnext)){
+ break;
+ }
+ if(next > Math.max(temp,nnext)){
+ temp = next;
+ }
+ newMessage = receivedMessage.newMessage(toByteBuffer(false,temp));
+ out.send(newMessage);
+ newMessage = receivedMessage.newMessage(toByteBuffer(false,next));
+ out.send(newMessage);
+ }
+
+ if(temp == next){
+ max = temp;
+ newMessage = receivedMessage.newMessage(toByteBuffer(true,max));
+ out.send(newMessage);
+
+ // stop
+ return;
+ }
+
+ /*
+ * Passive
+ */
+ while(true){
+ try{
+ receivedMessage = in.blockingReceive();
+ }catch(InterruptedException _e){
+ _e.printStackTrace();
+ }
+ b = receivedMessage.getMessage();
+ if(b.get() == (byte)1){
+ max = b.getLong();
+ newMessage = receivedMessage.newMessage(toByteBuffer(true,max));
+ out.send(newMessage);
+
+ //stop
+ return;
+ }
+
+ long value = b.getLong();
+ newMessage = receivedMessage.newMessage(toByteBuffer(false,value));
+ out.send(newMessage);
+ }
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/Algorithm.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/Algorithm.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,6 @@
+package suikwasha.distributedalgorithm.framework;
+
+public interface Algorithm
+{
+ public void execute(Context _c);
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/Context.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/Context.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,6 @@
+package suikwasha.distributedalgorithm.framework;
+
+public interface Context
+{
+ public Iterable getPorts();
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/Link.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/Link.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,7 @@
+package suikwasha.distributedalgorithm.framework;
+
+public interface Link
+{
+ public Port getPort1();
+ public Port getPort2();
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/LinkBuilder.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/LinkBuilder.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,6 @@
+package suikwasha.distributedalgorithm.framework;
+
+public interface LinkBuilder
+{
+ public Link build();
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/Machine.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/Machine.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,7 @@
+package suikwasha.distributedalgorithm.framework;
+
+public abstract class Machine extends Thread
+{
+ public abstract void addPort(Port _p);
+ public abstract void run();
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/MachineBuilder.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/MachineBuilder.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,6 @@
+package suikwasha.distributedalgorithm.framework;
+
+public interface MachineBuilder
+{
+ public Machine createMachine(Algorithm _algo);
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/Message.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/Message.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,42 @@
+package suikwasha.distributedalgorithm.framework;
+
+import java.nio.ByteBuffer;
+
+public class Message
+{
+ private final ByteBuffer message;
+ private final MessageChain chain;
+
+ public Message(ByteBuffer _message)
+ {
+ message = _message;
+ chain = MessageChain.NIL_MESSAGECHAIN;
+ }
+
+ private Message(ByteBuffer _message,MessageChain _chain)
+ {
+ message = _message;
+ chain = _chain;
+ }
+
+ public ByteBuffer getMessage()
+ {
+ return message.asReadOnlyBuffer();
+ }
+
+ public MessageChain getMessageChain()
+ {
+ return chain;
+ }
+
+ public long getSize()
+ {
+ return message.limit();
+ }
+
+ public Message newMessage(ByteBuffer _message)
+ {
+ MessageChain newChain = chain.add(this);
+ return new Message(_message,newChain);
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/MessageChain.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/MessageChain.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,37 @@
+package suikwasha.distributedalgorithm.framework;
+
+import java.util.Iterator;
+
+import fj.data.List;
+
+public class MessageChain implements Iterable
+{
+ private static final List NIL_LIST = List.nil();
+ private final List list;
+ public static final MessageChain NIL_MESSAGECHAIN = new MessageChain();
+
+ private MessageChain()
+ {
+ list = NIL_LIST;
+ }
+
+ private MessageChain(List _list,Message _message)
+ {
+ list = _list.snoc(_message);
+ }
+
+ public MessageChain add(Message _message)
+ {
+ return new MessageChain(list,_message);
+ }
+
+ public long getMessageCount()
+ {
+ return list.length();
+ }
+
+ public Iterator iterator()
+ {
+ return list.iterator();
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/Port.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/Port.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,8 @@
+package suikwasha.distributedalgorithm.framework;
+
+public interface Port
+{
+ public void send(Message _mes);
+ public Message blockingReceive() throws InterruptedException;
+ public Message tryReceive();
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/Topology.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/Topology.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,7 @@
+package suikwasha.distributedalgorithm.framework;
+
+public interface Topology
+{
+ public Iterable getMachines();
+ public long getMachineCount();
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/framework/TopologyBuilder.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/framework/TopologyBuilder.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,6 @@
+package suikwasha.distributedalgorithm.framework;
+
+public interface TopologyBuilder
+{
+ public Topology build(Iterable _algos,MachineBuilder _machineBuilder,LinkBuilder _linkBuilder);
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/link/ReliableLinkBuilder.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/link/ReliableLinkBuilder.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,67 @@
+package suikwasha.distributedalgorithm.link;
+
+import java.util.concurrent.LinkedBlockingQueue;
+
+import suikwasha.distributedalgorithm.framework.Link;
+import suikwasha.distributedalgorithm.framework.LinkBuilder;
+import suikwasha.distributedalgorithm.framework.Message;
+import suikwasha.distributedalgorithm.framework.Port;
+
+public class ReliableLinkBuilder implements LinkBuilder
+{
+ public Link build()
+ {
+ return new LinkImpl();
+ }
+
+ private static class LinkImpl implements Link
+ {
+ private final Port port1,port2;
+
+ public LinkImpl()
+ {
+ LinkedBlockingQueue queue1 = new LinkedBlockingQueue();
+ LinkedBlockingQueue queue2 = new LinkedBlockingQueue();
+
+ port1 = new PortImpl(queue1,queue2);
+ port2 = new PortImpl(queue2,queue1);
+ }
+
+ public Port getPort1()
+ {
+ return port1;
+ }
+
+ public Port getPort2()
+ {
+ return port2;
+ }
+ }
+
+ private static class PortImpl implements Port
+ {
+ private final LinkedBlockingQueue in;
+ private final LinkedBlockingQueue out;
+
+ public PortImpl(LinkedBlockingQueue _in,LinkedBlockingQueue _out)
+ {
+ in = _in;
+ out = _out;
+ }
+
+ public void send(Message _mes)
+ {
+ out.add(_mes);
+ }
+
+ public Message blockingReceive() throws InterruptedException
+ {
+ return in.take();
+ }
+
+ public Message tryReceive()
+ {
+ return in.poll();
+ }
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/machines/SimpleMachineBuilder.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/machines/SimpleMachineBuilder.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,54 @@
+package suikwasha.distributedalgorithm.machines;
+
+
+import fj.data.List;
+import suikwasha.distributedalgorithm.framework.Context;
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.framework.Machine;
+import suikwasha.distributedalgorithm.framework.MachineBuilder;
+import suikwasha.distributedalgorithm.framework.Port;
+
+public class SimpleMachineBuilder implements MachineBuilder
+{
+ public Machine createMachine(Algorithm _algo)
+ {
+ return new MachineImpl(_algo);
+ }
+
+ private static class MachineImpl extends Machine
+ {
+ private List ports;
+ private final Algorithm algo;
+
+ public MachineImpl(Algorithm _algo)
+ {
+ ports = List.nil();
+ algo = _algo;
+ }
+
+ public void addPort(Port _p)
+ {
+ ports = ports.snoc(_p);
+ }
+
+ public void run()
+ {
+ algo.execute(new ContextImpl(ports));
+ }
+ }
+
+ private static class ContextImpl implements Context
+ {
+ public List ports;
+
+ public ContextImpl(List _ports)
+ {
+ ports = _ports;
+ }
+
+ public Iterable getPorts()
+ {
+ return ports;
+ }
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/simulator/LoggingMessageLinkBuilder.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/simulator/LoggingMessageLinkBuilder.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,77 @@
+package suikwasha.distributedalgorithm.simulator;
+
+import suikwasha.distributedalgorithm.framework.Link;
+import suikwasha.distributedalgorithm.framework.LinkBuilder;
+import suikwasha.distributedalgorithm.framework.Message;
+import suikwasha.distributedalgorithm.framework.Port;
+
+public class LoggingMessageLinkBuilder implements LinkBuilder
+{
+ private final LinkBuilder builder;
+ private final Summary summary;
+
+ public LoggingMessageLinkBuilder(Summary _summary,LinkBuilder _builder)
+ {
+ summary = _summary;
+ builder = _builder;
+ }
+
+ public Link build()
+ {
+ return new LoggingLink(summary,builder.build());
+ }
+
+ public static class LoggingLink implements Link
+ {
+ private Link link;
+ private Summary summary;
+
+ public LoggingLink(Summary _summary,Link _link)
+ {
+ summary = _summary;
+ link = _link;
+ }
+
+ public Port getPort1()
+ {
+ return new LoggingPort(summary,link.getPort1());
+ }
+
+ public Port getPort2()
+ {
+ return new LoggingPort(summary,link.getPort2());
+ }
+ }
+
+ public static class LoggingPort implements Port
+ {
+ private Summary summary;
+ private Port port;
+
+ public LoggingPort(Summary _summary,Port _port)
+ {
+ summary = _summary;
+ port = _port;
+ }
+
+ public void send(Message _mes)
+ {
+ long bits = _mes.getMessage().limit();
+ summary.addMessageBitCount(bits);
+ summary.incrementMessageCount();
+ summary.trySetMessageChain(_mes.getMessageChain());
+
+ port.send(_mes);
+ }
+
+ public Message blockingReceive() throws InterruptedException
+ {
+ return port.blockingReceive();
+ }
+
+ public Message tryReceive()
+ {
+ return port.tryReceive();
+ }
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/simulator/Simulator.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/simulator/Simulator.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,43 @@
+package suikwasha.distributedalgorithm.simulator;
+
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.framework.LinkBuilder;
+import suikwasha.distributedalgorithm.framework.Machine;
+import suikwasha.distributedalgorithm.framework.MachineBuilder;
+import suikwasha.distributedalgorithm.framework.Topology;
+import suikwasha.distributedalgorithm.framework.TopologyBuilder;
+
+public class Simulator
+{
+ private final Iterable algos;
+ private final LinkBuilder linkBuilder;
+ private final MachineBuilder machineBuilder;
+ private final TopologyBuilder topologyBuilder;
+
+ public Simulator(Iterable _algos,LinkBuilder _linkBuilder
+ ,MachineBuilder _machineBuilder,TopologyBuilder _topologyBuilder)
+ {
+ algos = _algos;
+ linkBuilder = _linkBuilder;
+ machineBuilder = _machineBuilder;
+ topologyBuilder = _topologyBuilder;
+ }
+
+ public Summary startSimulation() throws InterruptedException
+ {
+ Summary summary = new Summary();
+ LoggingMessageLinkBuilder logLinkBuilder = new LoggingMessageLinkBuilder(summary,linkBuilder);
+ SyncMachineBuilder syncMachineBuilder = new SyncMachineBuilder(machineBuilder);
+
+ Topology topologies = topologyBuilder.build(algos,syncMachineBuilder,logLinkBuilder);
+
+ for(Machine machine : topologies.getMachines()){
+ machine.start();
+ }
+
+ Synchronizer sync = syncMachineBuilder.getSynchronizer();
+ sync.await();
+
+ return summary;
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/simulator/Summary.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/simulator/Summary.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,66 @@
+package suikwasha.distributedalgorithm.simulator;
+
+import java.util.concurrent.atomic.AtomicLong;
+import java.util.concurrent.atomic.AtomicReference;
+
+import suikwasha.distributedalgorithm.framework.MessageChain;
+
+public class Summary
+{
+ private final AtomicLong messageComplexity;
+ private final AtomicLong bitComplexity;
+ private final AtomicReference longestMessageChain;
+
+ public Summary()
+ {
+ messageComplexity = new AtomicLong(0);
+ bitComplexity = new AtomicLong(0);
+ longestMessageChain = new AtomicReference(MessageChain.NIL_MESSAGECHAIN);
+ }
+
+ public void incrementMessageCount()
+ {
+ messageComplexity.incrementAndGet();
+ }
+
+ public void addMessageBitCount(long _size)
+ {
+ bitComplexity.addAndGet(_size);
+ }
+
+ public long getCurrentMessageComplexity()
+ {
+ return messageComplexity.get();
+ }
+
+ public long getCurrentBitComplexity()
+ {
+ return bitComplexity.get();
+ }
+
+ public MessageChain getLongestMessageChain()
+ {
+ return longestMessageChain.get();
+ }
+
+ public boolean trySetMessageChain(MessageChain _chain)
+ {
+ MessageChain currentLongestChain;
+ do{
+ currentLongestChain = longestMessageChain.get();
+ if(currentLongestChain.getMessageCount() > _chain.getMessageCount()){
+ return false;
+ }
+ }while(!longestMessageChain.compareAndSet(currentLongestChain,_chain));
+
+ return true;
+ }
+
+ public void print()
+ {
+ System.out.println("Summary:");
+ System.out.println(String.format("MessageComplexity :\t\t%d",messageComplexity.get()));
+ System.out.println(String.format("MessageBitComplexity :\t\t%d",messageComplexity.get()));
+ System.out.println(String.format("TimeComplexity :\t\t%d",longestMessageChain.get().getMessageCount()));
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/simulator/SyncMachineBuilder.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/simulator/SyncMachineBuilder.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,53 @@
+package suikwasha.distributedalgorithm.simulator;
+
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.framework.Machine;
+import suikwasha.distributedalgorithm.framework.MachineBuilder;
+import suikwasha.distributedalgorithm.framework.Port;
+
+public class SyncMachineBuilder implements MachineBuilder
+{
+ private final MachineBuilder builder;
+ private final Synchronizer synchronizer;
+
+ public SyncMachineBuilder(MachineBuilder _builder)
+ {
+ builder = _builder;
+ synchronizer = new Synchronizer();
+ }
+
+ public Machine createMachine(Algorithm _algo)
+ {
+ Machine newMachine = builder.createMachine(_algo);
+ synchronizer.countup();
+ return new SyncMachine(synchronizer,newMachine);
+ }
+
+ public Synchronizer getSynchronizer()
+ {
+ return synchronizer;
+ }
+
+ private static class SyncMachine extends Machine
+ {
+ private final Synchronizer synchronizer;
+ private final Machine machine;
+
+ public SyncMachine(Synchronizer _synchronizer,Machine _machine)
+ {
+ synchronizer = _synchronizer;
+ machine = _machine;
+ }
+
+ public void addPort(Port _p)
+ {
+ machine.addPort(_p);
+ }
+
+ public void run()
+ {
+ machine.run();
+ synchronizer.countdown();
+ }
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/simulator/Synchronizer.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/simulator/Synchronizer.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,48 @@
+package suikwasha.distributedalgorithm.simulator;
+
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.atomic.AtomicLong;
+
+public class Synchronizer
+{
+ private AtomicLong counter;
+ private CountDownLatch latch;
+
+ public Synchronizer()
+ {
+ counter = new AtomicLong();
+ latch = new CountDownLatch(1);
+ }
+
+ public long countup() throws IllegalStateException
+ {
+ // double checking , is it effective?
+ if(latch.getCount() != 0){
+ long value = counter.incrementAndGet();
+ if(latch.getCount() != 0){
+ return value;
+ }
+ }
+
+ throw new IllegalStateException("latch.getCount() == 0");
+ }
+
+ public long countdown() throws IllegalStateException
+ {
+ long value = counter.decrementAndGet();
+ if(value < 0){
+ throw new IllegalStateException("counter < 0");
+ }
+
+ if(value == 0){
+ latch.countDown();
+ }
+
+ return value;
+ }
+
+ public void await() throws InterruptedException
+ {
+ latch.await();
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/main/java/suikwasha/distributedalgorithm/topologies/RingTopologyBuilder.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/suikwasha/distributedalgorithm/topologies/RingTopologyBuilder.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,72 @@
+package suikwasha.distributedalgorithm.topologies;
+
+import fj.data.List;
+import suikwasha.distributedalgorithm.framework.Algorithm;
+import suikwasha.distributedalgorithm.framework.Link;
+import suikwasha.distributedalgorithm.framework.LinkBuilder;
+import suikwasha.distributedalgorithm.framework.Machine;
+import suikwasha.distributedalgorithm.framework.MachineBuilder;
+import suikwasha.distributedalgorithm.framework.Topology;
+import suikwasha.distributedalgorithm.framework.TopologyBuilder;
+
+public class RingTopologyBuilder implements TopologyBuilder
+{
+ public Topology build(Iterable _algos,MachineBuilder _machineBuilder,LinkBuilder _linkBuilder)
+ {
+ List list = List.nil();
+
+ // first , create machines
+
+ for(Algorithm algo : _algos){
+ Machine machine = _machineBuilder.createMachine(algo);
+ list = list.snoc(machine);
+ }
+
+ if(list.length() < 1){
+ throw new IllegalArgumentException("list.length() < 1");
+ }
+
+ // create links
+
+ Link firstLink = _linkBuilder.build();
+ Machine head = list.head();
+ head.addPort(firstLink.getPort2());
+
+ List tail = list.tail();
+ Machine prevMachine = head;
+ if(tail.length() != 0){
+ for(Machine machine : tail){
+ Link link = _linkBuilder.build();
+ prevMachine.addPort(link.getPort1());
+ machine.addPort(link.getPort2());
+ prevMachine = machine;
+ }
+ Machine last = tail.last();
+ last.addPort(firstLink.getPort1());
+ }else{
+ head.addPort(firstLink.getPort1());
+ }
+
+ return new RingTopology(list);
+ }
+
+ private class RingTopology implements Topology
+ {
+ private final List machines;
+
+ public RingTopology(List _machines)
+ {
+ machines = _machines;
+ }
+
+ public Iterable getMachines()
+ {
+ return machines;
+ }
+
+ public long getMachineCount()
+ {
+ return machines.length();
+ }
+ }
+}
diff -r 000000000000 -r 38a110b13db1 src/test/java/suikwasha/distributedalgorithm/AppTest.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/java/suikwasha/distributedalgorithm/AppTest.java Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,38 @@
+package suikwasha.distributedalgorithm;
+
+import junit.framework.Test;
+import junit.framework.TestCase;
+import junit.framework.TestSuite;
+
+/**
+ * Unit test for simple App.
+ */
+public class AppTest
+ extends TestCase
+{
+ /**
+ * Create the test case
+ *
+ * @param testName name of the test case
+ */
+ public AppTest( String testName )
+ {
+ super( testName );
+ }
+
+ /**
+ * @return the suite of tests being tested
+ */
+ public static Test suite()
+ {
+ return new TestSuite( AppTest.class );
+ }
+
+ /**
+ * Rigourous Test :-)
+ */
+ public void testApp()
+ {
+ assertTrue( true );
+ }
+}
diff -r 000000000000 -r 38a110b13db1 target/classes/META-INF/MANIFEST.MF
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/target/classes/META-INF/MANIFEST.MF Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,5 @@
+Manifest-Version: 1.0
+Built-By: shoshi
+Build-Jdk: 1.6.0_35
+Created-By: Maven Integration for Eclipse
+
diff -r 000000000000 -r 38a110b13db1 target/classes/META-INF/maven/suikwasha/distributedalgorithm/pom.properties
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/target/classes/META-INF/maven/suikwasha/distributedalgorithm/pom.properties Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,7 @@
+#Generated by Maven Integration for Eclipse
+#Fri Oct 19 00:04:33 JST 2012
+version=0.0.1-SNAPSHOT
+groupId=suikwasha
+m2e.projectName=distributedalgorithm
+m2e.projectLocation=/Users/shoshi/Documents/old/distributedalgorithm
+artifactId=distributedalgorithm
diff -r 000000000000 -r 38a110b13db1 target/classes/META-INF/maven/suikwasha/distributedalgorithm/pom.xml
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/target/classes/META-INF/maven/suikwasha/distributedalgorithm/pom.xml Fri Oct 19 00:05:41 2012 +0900
@@ -0,0 +1,30 @@
+
+ 4.0.0
+
+ suikwasha
+ distributedalgorithm
+ 0.0.1-SNAPSHOT
+ jar
+
+ distributedalgorithm
+ http://maven.apache.org
+
+
+ UTF-8
+
+
+
+
+ junit
+ junit
+ 3.8.1
+ test
+
+
+ org.functionaljava
+ functionaljava
+ 3.0
+
+
+