weak_global_coin.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!pip install qiskit\n",
    "#!pip install qiskit[visualization]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import QuantumCircuit\n",
    "from qiskit_aer import AerSimulator\n",
    "import numpy as np\n",
    "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n",
    "from qiskit_ibm_runtime import SamplerV2\n",
    "\n",
    "from threading import Lock, Condition\n",
    "from globals import *\n",
    "\n",
    "import ipynb.fs.full.adversary as ADV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Initial parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_cube = pow(n,3)\n",
    "\n",
    "qb_per_process = int(np.ceil(np.log2(n_cube)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quantum Factory"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class QuantumFactory:\n",
    "    def __init__(self) -> None:\n",
    "        self.coin = None\n",
    "        self.leader = None\n",
    "        self.generate_coin_circuit()\n",
    "        self.generate_leader_circuit()\n",
    "\n",
    "    def generate_coin_circuit(self):\n",
    "        qc = QuantumCircuit(n)\n",
    "        qc.h(0)\n",
    "        qc.cx(0,range(1,n))\n",
    "        qc.measure_all()    \n",
    "        self.coin = qc\n",
    "    \n",
    "    def generate_leader_circuit(self):\n",
    "        total_qubits = n * qb_per_process\n",
    "        qc = QuantumCircuit(total_qubits)\n",
    "        qc.h(range(0, qb_per_process))\n",
    "\n",
    "        for j in range(1,n):\n",
    "            for i in range(0, qb_per_process):\n",
    "                qc.cx(i, i + j * qb_per_process)\n",
    "        qc.measure_all()\n",
    "        self.leader = qc\n",
    "\n",
    "    def get_coin_circuit(self) -> QuantumCircuit:\n",
    "         return self.coin.copy()\n",
    "    \n",
    "    def get_leader_circuit(self) -> QuantumCircuit:\n",
    "         return self.leader.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Circuit():\n",
    "    def __init__(self, system) -> None:\n",
    "        self.system = system\n",
    "        self.result = None\n",
    "        self.memory = None\n",
    "        self.measured = False\n",
    "    def measure_circuit(self):\n",
    "        aer_sim = AerSimulator(method=\"stabilizer\")\n",
    "        pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)\n",
    "        isa_qc = pm.run(self.system)\n",
    "        sampler = SamplerV2(backend=aer_sim)\n",
    "        \n",
    "        result = sampler.run([isa_qc], shots=1).result()\n",
    "        data_pub = result[0].data\n",
    "        counts = data_pub.meas.get_counts()\n",
    "        self.memory = list(counts.keys())[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CircuitMessage(Message):\n",
    "    def __init__(self, process_id, receivers, system) -> None:\n",
    "        super().__init__(process_id, receivers)\n",
    "        self.circuit = Circuit(system)  \n",
    "    def __str__(self) -> str:\n",
    "        return f\"sender: {self.sender} | receivers: {self.receivers} | measured: {self.circuit.measured} | result: {self.circuit.result}\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Global variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "quantum_factory = QuantumFactory()\n",
    "coin_msgs = []\n",
    "leader_msgs = []\n",
    "\n",
    "waiting_num_of_msgs = []\n",
    "msg_quantity_lock = Lock() \n",
    "\n",
    "coin_condition = Condition()\n",
    "leader_condition = Condition()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_msgs_for_process(process_id, curr_leader_msgs=None, curr_coin_msgs=None):\n",
    "    msg_count = 0\n",
    "    if curr_leader_msgs:\n",
    "        leader_lock.acquire()\n",
    "        for msg in curr_leader_msgs:\n",
    "            if process_id in msg.receivers:\n",
    "                msg_count += 1\n",
    "        leader_lock.release()\n",
    "    elif curr_coin_msgs:\n",
    "        coin_lock.acquire()\n",
    "        for msg in curr_coin_msgs:\n",
    "            if process_id in msg.receivers:\n",
    "                msg_count += 1\n",
    "        coin_lock.release()\n",
    "    return msg_count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Waiting number of messages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_waiting_num_of_msgs(epoch, processes):\n",
    "    msg_quantity_lock.acquire()\n",
    "    if len(waiting_num_of_msgs) < epoch:\n",
    "        if epoch-1 == 0:\n",
    "            waiting_num_of_msgs.append([n]*n)    \n",
    "        else:\n",
    "            min_val_prev_epoch = min(waiting_num_of_msgs[epoch-2])\n",
    "            actual_alive_processes = [1 for pr in processes if pr.non_faulty].count(1)\n",
    "            min_val = min([min_val_prev_epoch, actual_alive_processes])\n",
    "            waiting_num_of_msgs.append([min_val]*n)\n",
    "    msg_quantity_lock.release()\n",
    "    \n",
    "def update_waiting_num_of_msgs(processes, epoch, new_receivers):\n",
    "    msg_quantity_lock.acquire()\n",
    "    for pr in processes:\n",
    "        if pr.id not in new_receivers:\n",
    "            waiting_num_of_msgs[epoch-1][pr.id] -= 1\n",
    "    msg_quantity_lock.release()\n",
    "\n",
    "def get_waiting_msgs(process_id, epoch):\n",
    "    msg_quantity_lock.acquire()\n",
    "    waiting_msgs = waiting_num_of_msgs[epoch-1][process_id]\n",
    "    msg_quantity_lock.release()\n",
    "    return waiting_msgs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def notify_condition(processes, epoch, curr_leader_msgs=None, curr_coin_msgs=None):\n",
    "    all_msgs_received = []\n",
    "    for pr in processes:\n",
    "        if pr.non_faulty:\n",
    "            pr_condition = None\n",
    "            if curr_leader_msgs:\n",
    "                pr_condition = get_msgs_for_process(pr.id, curr_leader_msgs=curr_leader_msgs) == get_waiting_msgs(pr.id, epoch)\n",
    "            elif curr_coin_msgs:\n",
    "                pr_condition = get_msgs_for_process(pr.id, curr_coin_msgs=curr_coin_msgs) == get_waiting_msgs(pr.id, epoch)\n",
    "            assert(pr_condition is not None)\n",
    "\n",
    "            all_msgs_received.append(pr_condition)\n",
    "    assert(all_msgs_received)\n",
    "    return all(all_msgs_received)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Acquire coin state (for each process)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def send_coin(processes, process_id, coin_condition, epoch):\n",
    "    coin_qc = quantum_factory.get_coin_circuit()\n",
    "    coin_lock.acquire()\n",
    "    new_msg = CircuitMessage(process_id, list(range(0,n)), coin_qc)\n",
    "    \n",
    "    if (len(coin_msgs) < epoch):\n",
    "        coin_msgs.append([])\n",
    "    coin_msgs[epoch-1].append(new_msg)\n",
    "    coin_lock.release()\n",
    "    \n",
    "    with coin_condition:\n",
    "        coin_condition.acquire()\n",
    "        if notify_condition(processes, epoch, curr_coin_msgs=coin_msgs[epoch-1]):\n",
    "            coin_condition.notify_all()\n",
    "        coin_condition.release()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Acquire Leader state (for each process)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def send_leader(processes, process_id, leader_condition, epoch):\n",
    "    leader_qc = quantum_factory.get_leader_circuit()\n",
    "    leader_lock.acquire()\n",
    "    new_msg = CircuitMessage(process_id, list(range(0,n)), leader_qc)\n",
    "    if len(leader_msgs) < epoch:\n",
    "        leader_msgs.append([])\n",
    "    leader_msgs[epoch-1].append(new_msg)\n",
    "    leader_lock.release()\n",
    "    \n",
    "    with leader_condition:\n",
    "        leader_condition.acquire()\n",
    "        if notify_condition(processes, epoch, curr_leader_msgs=leader_msgs[epoch-1]):\n",
    "            leader_condition.notify_all()\n",
    "        leader_condition.release()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### QuantumCoinFlip"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_highest_leader_id(process, epoch):\n",
    "    leader_lock.acquire()\n",
    "    leader_measurements = {}\n",
    "    curr_leader_msgs = leader_msgs[epoch-1]\n",
    "    assert(len(curr_leader_msgs) >= MAX_ALIVE_PROCESSES)\n",
    "    for msg in curr_leader_msgs:\n",
    "        if process.id in msg.receivers:\n",
    "            owner_id = msg.sender\n",
    "\n",
    "            if not msg.circuit.measured:\n",
    "                msg.circuit.measure_circuit()\n",
    "                msg.circuit.measured = True\n",
    "            leader_outcome = int(msg.circuit.memory[:qb_per_process], 2)\n",
    "\n",
    "            existing_ids = leader_measurements.get(leader_outcome)\n",
    "            if existing_ids is not None:\n",
    "                existing_ids.append(owner_id)\n",
    "            else:\n",
    "                existing_ids = [owner_id]\n",
    "\n",
    "            leader_measurements.update({leader_outcome:existing_ids})\n",
    "    highest_leader_outcome = max(leader_measurements)\n",
    "\n",
    "    leader_processes_ids = leader_measurements.get(highest_leader_outcome)\n",
    "    leader_processes_ids.sort()\n",
    "    leader_lock.release()\n",
    "    return leader_processes_ids[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_coin_result(sender_id, curr_coin_msgs):\n",
    "    coin_lock.acquire()\n",
    "    memory_val = None\n",
    "    for msg in curr_coin_msgs:\n",
    "        if msg.sender == sender_id:\n",
    "            if not msg.circuit.measured:\n",
    "                msg.circuit.measure_circuit()\n",
    "                msg.circuit.measured = True\n",
    "            memory_val = msg.circuit.memory\n",
    "            break\n",
    "    coin_lock.release()\n",
    "    assert(memory_val is not None)\n",
    "    return memory_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_leader_condition(process, epoch):\n",
    "    with leader_condition:\n",
    "        while get_msgs_for_process(process.id, curr_leader_msgs=leader_msgs[epoch-1]) < get_waiting_msgs(process.id, epoch):\n",
    "            leader_condition.acquire()\n",
    "            leader_condition.wait()\n",
    "            leader_condition.release()\n",
    "\n",
    "def check_coin_condition(process, epoch):\n",
    "    with coin_condition:\n",
    "        while get_msgs_for_process(process.id, curr_coin_msgs=coin_msgs[epoch-1]) < get_waiting_msgs(process.id, epoch):\n",
    "            coin_condition.acquire()\n",
    "            coin_condition.wait()\n",
    "            coin_condition.release()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quantum_coin_flip(processes, process, epoch):\n",
    "    init_waiting_num_of_msgs(epoch, processes)\n",
    "    send_coin(processes, process.id, coin_condition, epoch)\n",
    "    send_leader(processes, process.id, leader_condition, epoch)\n",
    "\n",
    "    new_receivers = ADV.adversary_take_over(process, coin_msgs[epoch-1], leader_msgs[epoch-1])\n",
    "    if not process.non_faulty:\n",
    "        update_waiting_num_of_msgs(processes, epoch, new_receivers)\n",
    "        \n",
    "        own_coin_val = get_coin_result(process.id, coin_msgs[epoch-1])\n",
    "        return own_coin_val[process.id]\n",
    "\n",
    "    check_leader_condition(process, epoch)\n",
    "\n",
    "    leader_process_id  = get_highest_leader_id(process, epoch)\n",
    "\n",
    "    leader_coin = None\n",
    "\n",
    "    check_coin_condition(process, epoch)\n",
    "\n",
    "    leader_coin = get_coin_result(leader_process_id, coin_msgs[epoch-1])\n",
    "    return leader_coin[process.id]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}