My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Thanks Tree1Thanks
  • 1 Post By Maschke
Reply
 
LinkBack Thread Tools Display Modes
July 17th, 2013, 11:29 PM   #1
Senior Member
 
Joined: Jan 2013

Posts: 209
Thanks: 3

How can set of computers agree if set size is even or odd?

How can a set of computers agree with eachother if the set size is even or odd?

I'm not sure how to prove it, but I think that to solve this reliably is an NP-Complete problem and practically is useful for new kinds of routing protocols and a foundation for decentralized global democracy more similar to how Wikipedia allows billions of people to agree on many things instead of top down ways of organizing things.

How can a set of computers agree with eachother if the set size is even or odd? How do you scale this up?
BenFRayfield is offline  
 
July 18th, 2013, 04:13 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: How can set of computers agree if set size is even or od

How is the set defined?
CRGreathouse is offline  
July 18th, 2013, 08:05 AM   #3
Senior Member
 
Joined: Jan 2013

Posts: 209
Thanks: 3

Re: How can set of computers agree if set size is even or od

Since the definition of every set includes its size which is even or odd, the question is how such a set of computers would agree on any such set in the first place. Its similar Max Clique. I can't just define the clique as a set then you tell me if its even or odd. Its a subset of all computers, some of which are directly connected and others have to communicate on longer paths to eachother.

I'll make it even easier... Tell me any such set that has ever, in the real world, been counted (as even or odd, to make it easier than counting), and how was it proven the count is accurate? Whats the biggest set of computers that has ever been done for? I think this is more than a mathematical abstraction. I think they really don't know how to count large groups of computers.
BenFRayfield is offline  
July 18th, 2013, 08:09 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: How can set of computers agree if set size is even or od

Quote:
Originally Posted by BenFRayfield
the question is how such a set of computers would agree on any such set in the first place.
So you're looking for a Byzantine agreement scheme, then.
CRGreathouse is offline  
July 18th, 2013, 08:23 AM   #5
Senior Member
 
Joined: Jan 2013

Posts: 209
Thanks: 3

Re: How can set of computers agree if set size is even or od

Hardware failures can be abstracted out of the question by representing a set of computers as a network within one Turing Complete cellular automata, like Conway's Game Of Life or Rule 110.
BenFRayfield is offline  
July 18th, 2013, 09:56 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: How can set of computers agree if set size is even or od

You need a bunch of computers to agree on something. You can use the Byzantine generals scheme to get them to do that, even if there are no hardware failures.
CRGreathouse is offline  
July 18th, 2013, 04:34 PM   #7
Senior Member
 
Joined: Aug 2012

Posts: 2,385
Thanks: 745

Re: How can set of computers agree if set size is even or od

Quote:
Originally Posted by BenFRayfield
I'll make it even easier... Tell me any such set that has ever, in the real world, been counted (as even or odd, to make it easier than counting), and how was it proven the count is accurate? Whats the biggest set of computers that has ever been done for? I think this is more than a mathematical abstraction. I think they really don't know how to count large groups of computers.
Not following at all. If the set has a size, and if that size can be represented in binary, the computer need only look at the low-order bit to determine if the set is even or odd. And your bank counts the set of dollars in your checking account, right down to the penny, every month. And they're never wrong. Just try convincing them they've made a mistake.

As CRG noted, there are a lot of algorithms related to fault-tolerant computing in which a network of computers can determine which of them are malfunctioning. There's computer science literature on multiprocessor voting schemes going back to the 1970's.
Thanks from CRGreathouse
Maschke is online now  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
agree, computers, odd, set, size



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Set size is relative - Same topology of negative size sets BenFRayfield Applied Math 4 December 21st, 2013 10:58 PM
Can someone agree? yogazen2013 Algebra 2 October 5th, 2013 03:26 AM
Integrals in computers dervast Real Analysis 8 January 17th, 2011 09:40 AM
the study of computers johnny Computer Science 5 August 7th, 2007 05:55 AM
speed of quantum computers johnny Computer Science 3 July 31st, 2007 06:35 AM





Copyright © 2019 My Math Forum. All rights reserved.