# marriage.py

This example solves the stable marriages problem.

    marriage.py men
    marriage.py women

This example solves the stable marriages problem. A classic distributed computing problem involves a group of men and a group of women. Each person has an ordered list ranking each member of the opposite sex in the order they want to marry them. A stable marriage is one where there are no pairs of the form {wi, mj} {wk, mt} where wi prefers mt to mj and mt prefers wi to wk.

This example is based on the example in A Principled Semantics for inp by Jacob & Wood 2000. The main code is in the Men and Women functions. The rest of the code is just to fork a seperate process for each person in the simulation.

The code itself is very simple, and relies mostly on the fact that when deadlock is reached the algorithm has finished. The inp calls detect the deadlock and cause the processes to exit.

    #!/usr/bin/python

    #    Copyright 2004 Andrew Wilkinson <aw@cs.york.ac.uk>.
    #
    #    This file is part of PyLinda (http://www-users.cs.york.ac.uk/~aw/pylinda)
    #
    #    PyLinda is free software; you can redistribute it and/or modify
    #    it under the terms of the GNU Lesser General Public License as published by
    #    the Free Software Foundation; either version 2.1 of the License, or
    #    (at your option) any later version.
    #
    #    PyLinda is distributed in the hope that it will be useful,
    #    but WITHOUT ANY WARRANTY; without even the implied warranty of
    #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    #    GNU Lesser General Public License for more details.
    #
    #    You should have received a copy of the GNU Lesser General Public License
    #    along with PyLinda; if not, write to the Free Software
    #    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    import linda
    import sys
    import random
    import os

    #
    # Process command line options
    #
    from optparse import OptionParser

    parser = OptionParser(version="%prog 1.0")
    parser.add_option("-p", "--connect-port", type="int", dest="connectport", default=2102,
                      help="The port to connect to.")

    (options, args) = parser.parse_args()

    linda.connect(options.connectport)
    #
    #
    #

    # Lists of men's and women's names
    men = ["AIDAN", "JADEN", "CADEN", "ETHAN", "CALEB", "DYLAN", "JACOB", "JORDAN", "LOGAN", "HAYDEN", "CONNOR", "RYAN", "MORGAN", "CAMERON", "ANDREW", "JOSHUA", "NOAH", "MATTHEW", "ADDISON", "ASHTON"]
    women = ["MADISON", "EMMA", "ABIGAIL", "RILEY", "CHLOE", "HANNAH", "ALEXIS", "ISABELLA", "MACKENZIE", "TAYLOR", "OLIVIA", "HAILEY", "PAIGE", "EMILY", "GRACE", "AVA", "AALIYAH", "ALYSSA", "FAITH", "BRIANNA"]

    ts = None

    # Function that represents a Man
    def Man(name):
        # Get the tuplespace we're working in
        ts = linda.universe._in(("ts", linda.TupleSpace))[1]

        # Randomize the order we want to propose to people in
        order = women[:]
        random.shuffle(order)

        # propose to each woman in order
        for w in order:
            print name + " proposing to " + w
            ts._out(("propose", name, w))

            # wait to see if we get rejected. If a deadlock is reached we've finished and should exit
            r = ts._inp(("reject", name, w))
            if r is None:
                break

        print "%s ended with %s (%i)" % (name, w, order.index(w) + 1)

    # Function that represents a Woman
    def Woman(name):
        # Returns the person we'd rather marry
        def BestOf(fiance, suitor):
            if fiance is None:
                return suitor
            elif order.index(fiance) < order.index(suitor):
                return fiance
            else:
                return suitor
        # Returns the person we'd rather not marry
        def WorstOf(fiance, suitor):
            if BestOf(fiance, suitor) == fiance:
                return suitor
            else:
                return fiance

        # Get the tuplespace we're working in
        ts = linda.universe._in(("ts", linda.TupleSpace))[1]

        # Randomize the order we want to marry people in
        order = men[:]
        random.shuffle(order)

        fiance = None
        while 1:
            # wait to be proposed to. If this returns None then a deadlock was reached
            p = ts._inp(("propose", str, name))
            if p is None:
                break
            else:
                suitor = p[1]

            # Choose who to reject and who to keep
            reject = WorstOf(fiance, suitor)
            fiance = BestOf(fiance, suitor)

            if reject is not None:
                print "%s rejecting %s for %s" % (name, reject, fiance)
                ts._out(("reject", reject, name))
            else:
                print "%s accepting %s" % (name, fiance)

        print "%s ended with %s (%i)" % (name, fiance, order.index(fiance) + 1)

    import sys

    # Create a tuplespace for us to work in
    if args[0] == "man" and args[1] == "0":
        ts = linda.TupleSpace()
        for i in range(len(men) + len(women)):
            linda.universe._out(("ts", ts))
        del ts

    if args[0] == "man":
        Man(men[int(sys.argv[2])])

    elif args[0] == "men":
        for i in range(0,len(men)):
            print "spawn", i
            os.spawnl(os.P_NOWAIT, "marriage.py", "marriage.py", "man", str(i))
            #if os.fork() == 0:
            #    os.execlp("./marriage.py", "marriage.py", "man", str(i))

    elif args[0] == "woman":
        Woman(women[int(sys.argv[2])])

    elif args[0] == "women":
        for i in range(0,len(women)):
            print "spawn", i
            os.spawnl(os.P_NOWAIT, "marriage.py", "marriage.py", "woman", str(i))
            #if os.fork() == 0:
            #    os.execlp("./marriage.py", "marriage.py","woman", str(i))

    00001 #!/usr/bin/python
    00002
    00003 #    Copyright 2004 Andrew Wilkinson <aw@cs.york.ac.uk>.
    00004 #
    00005 #    This file is part of PyLinda (http://www-users.cs.york.ac.uk/~aw/pylinda)
    00006 #
    00007 #    PyLinda is free software; you can redistribute it and/or modify
    00008 #    it under the terms of the GNU Lesser General Public License as published by
    00009 #    the Free Software Foundation; either version 2.1 of the License, or
    00010 #    (at your option) any later version.
    00011 #
    00012 #    PyLinda is distributed in the hope that it will be useful,
    00013 #    but WITHOUT ANY WARRANTY; without even the implied warranty of
    00014 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00015 #    GNU Lesser General Public License for more details.
    00016 #
    00017 #    You should have received a copy of the GNU Lesser General Public License
    00018 #    along with PyLinda; if not, write to the Free Software
    00019 #    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    00020
    00021 import linda
    00022 import sys
    00023 import random
    00024 import os
    00025
    00026 #
    00027 # Process command line options
    00028 #
    00029 from optparse import OptionParser
    00030
    00031 parser = OptionParser(version="%prog 1.0")
    00032 parser.add_option("-p", "--connect-port", type="int", dest="connectport", default=2102,
    00033                   help="The port to connect to.")
    00034
    00035 (options, args) = parser.parse_args()
    00036
    00037 linda.connect(options.connectport)
    00038 #
    00039 #
    00040 #
    00041
    00042 # Lists of men's and women's names
    00043 men = ["AIDAN", "JADEN", "CADEN", "ETHAN", "CALEB", "DYLAN", "JACOB", "JORDAN", "LOGAN", "HAYDEN", "CONNOR", "RYAN", "MORGAN", "CAMERON", "ANDREW", "JOSHUA", "NOAH", "MATTHEW", "ADDISON", "ASHTON"]
    00044 women = ["MADISON", "EMMA", "ABIGAIL", "RILEY", "CHLOE", "HANNAH", "ALEXIS", "ISABELLA", "MACKENZIE", "TAYLOR", "OLIVIA", "HAILEY", "PAIGE", "EMILY", "GRACE", "AVA", "AALIYAH", "ALYSSA", "FAITH", "BRIANNA"]
    00045
    00046 ts = None
    00047
    00048 # Function that represents a Man
    00049 def Man(name):
    00050     # Get the tuplespace we're working in
    00051     ts = linda.universe._in(("ts", linda.TupleSpace))[1]
    00052
    00053     # Randomize the order we want to propose to people in
    00054     order = women[:]
    00055     random.shuffle(order)
    00056
    00057     # propose to each woman in order
    00058     for w in order:
    00059         print name + " proposing to " + w
    00060         ts._out(("propose", name, w))
    00061
    00062         # wait to see if we get rejected. If a deadlock is reached we've finished and should exit
    00063         r = ts._inp(("reject", name, w))
    00064         if r is None:
    00065             break
    00066
    00067     print "%s ended with %s (%i)" % (name, w, order.index(w) + 1)
    00068
    00069 # Function that represents a Woman
    00070 def Woman(name):
    00071     # Returns the person we'd rather marry
    00072     def BestOf(fiance, suitor):
    00073         if fiance is None:
    00074             return suitor
    00075         elif order.index(fiance) < order.index(suitor):
    00076             return fiance
    00077         else:
    00078             return suitor
    00079     # Returns the person we'd rather not marry
    00080     def WorstOf(fiance, suitor):
    00081         if BestOf(fiance, suitor) == fiance:
    00082             return suitor
    00083         else:
    00084             return fiance
    00085
    00086     # Get the tuplespace we're working in
    00087     ts = linda.universe._in(("ts", linda.TupleSpace))[1]
    00088
    00089     # Randomize the order we want to marry people in
    00090     order = men[:]
    00091     random.shuffle(order)
    00092
    00093     fiance = None
    00094     while 1:
    00095         # wait to be proposed to. If this returns None then a deadlock was reached
    00096         p = ts._inp(("propose", str, name))
    00097         if p is None:
    00098             break
    00099         else:
    00100             suitor = p[1]
    00101
    00102         # Choose who to reject and who to keep
    00103         reject = WorstOf(fiance, suitor)
    00104         fiance = BestOf(fiance, suitor)
    00105
    00106         if reject is not None:
    00107             print "%s rejecting %s for %s" % (name, reject, fiance)
    00108             ts._out(("reject", reject, name))
    00109         else:
    00110             print "%s accepting %s" % (name, fiance)
    00111
    00112     print "%s ended with %s (%i)" % (name, fiance, order.index(fiance) + 1)
    00113
    00114 import sys
    00115
    00116 # Create a tuplespace for us to work in
    00117 if args[0] == "man" and args[1] == "0":
    00118     ts = linda.TupleSpace()
    00119     for i in range(len(men) + len(women)):
    00120         linda.universe._out(("ts", ts))
    00121     del ts
    00122
    00123 if args[0] == "man":
    00124     Man(men[int(sys.argv[2])])
    00125
    00126 elif args[0] == "men":
    00127     for i in range(0,len(men)):
    00128         print "spawn", i
    00129         os.spawnl(os.P_NOWAIT, "marriage.py", "marriage.py", "man", str(i))
    00130         #if os.fork() == 0:
    00131         #    os.execlp("./marriage.py", "marriage.py", "man", str(i))
    00132
    00133 elif args[0] == "woman":
    00134     Woman(women[int(sys.argv[2])])
    00135
    00136 elif args[0] == "women":
    00137     for i in range(0,len(women)):
    00138         print "spawn", i
    00139         os.spawnl(os.P_NOWAIT, "marriage.py", "marriage.py", "woman", str(i))
    00140         #if os.fork() == 0:
    00141         #    os.execlp("./marriage.py", "marriage.py","woman", str(i))
    00142
    00143