两军问题

两军问题研究长春师范大学传媒学院11教育技术学专业高雄飞两军问题——教学重点•什么是两军问题•两军问题的由来与发展•研究两军问题的意义什么是两军问题一支红色部队在山谷里扎营,在周围的两边山坡上驻扎着蓝色部队.红色部队比两支蓝色部队中的任意一支都要强大,但两支蓝色部队加在一起就要比红色部队强大.如果一支蓝色部队单独作战,那么它就会被红色部队击败;如果两支蓝色部队同时进攻,他们将能够把红色部队击败.两支蓝色部队需要同步他们的进攻,但他们惟一的通信媒介是步行进入山谷,在那里他们可能被俘虏,从而将信息丢失(换言之,他们必须使用非可靠的通信信道).问题是,是否存在一个协议,能够使得蓝色部队取胜?这就是有名的两军问题.两军问题的由来及发展由来：拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序。在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成。两军问题的由来及发展1.两军问题是现实生活中的一个关于信息传送的典型案例2.随着信息技术的发展两军问题的不断演化（1）古代我们用的就只有烽火狼烟、飞鸽传书和上述方式（2）二次工业革命之后产生的电话和无线电（3）在信息时代的网络媒介3.抽象后的两军问题抽象之后的两军问题实际上就是研究如何使用非可靠的通信信道来传递可靠保密的信息4.如何解决两军问题两军问题的由来及发展1.拜占庭问题的解决•拜占庭问题的最初描述是：n个将军被分隔在不同的地方，忠诚的将军希望通过某种协议达成某个命令的一致（比如一起进攻或者一起后退）。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。Lamport证明了在将军总数大于3m，背叛者为m或者更少时，忠诚的将军可以达成命令上的一致。•为了保证上面的需求，必须满足下面两个条件：•1.每两个忠诚的将军必须收到相同的值v(i)（v(i)是第i个将军的命令）两军问题的由来及发展•1.拜占庭问题的解决•2.如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的v(i)相同•为了简化以上模型，我们使用一个将军发送命令给多个副官的形式来证明，发送命令的将军称为发令者，接收命令的将军为副官，那么上面的两个条件可以表述为：•IC1.所有忠诚的副官遵守相同的命令•IC2.如果发出命令的将军是忠诚的，那么所有忠诚的副官遵守司令（发出命令的将军）的命令•特别提示：发送命令的每次只有一个将军，将其命令发送给n-1个副官。m代表叛国者的个数，因为将军总数为n，所以副官总数为n-1个。IC2中副官遵守实际上是指忠诚的将军能够正确收到忠诚将军的命令消息。两军问题的由来及发展2.电话电报与无线电时代问题的解决由于计算机网络是基于电话系统无线电传输系统之上的，因此我们可以直接对计算机网络系统的信息传输进行研究其实也就是对电器时代的信息传输的研究。两军问题的由来及发展3.信息时代两军问题的解决信息时代信息的相互传输也是通过协议来完成的只是这个协议叫网络协议。网络协议，也可简称协议，由三要素组成：(1)语法：即数据与控制信息的结构或格式；(2)语义：即需要发出何种控制信息，完成何种动作以及做出何种响应；(3)时序（同步），即事件实现顺序的详细说明。计算机通信网是由许多具有信息交换和处理能力的节点互连而成的。要使整个网络有条不紊地工作,就要求每个节点必须遵守一些事先约定好的有关数据格式及时序等的规则。这些为实现网络数据交换而建立的规则、约定或标准就称为网络协议。协议是通信双方为了实现通信而设计的约定或通话规则。协议总是指某一层的协议。准确地说，它是在同等层之间的实体通信时，有关通信规则和约定的集合就是该层协议，例如物理层协议、传输层协议、应用层协议。两军问题的由来及发展3.信息时代两军问题的解决步骤是一系列的步骤：它包括两方或多方，设计它的目的是要完成一项任务！是对数据格式和计算机之间交换数据时必须遵守的规则的正式描述。简单的说，网络中的计算机要能够互相顺利的通信，就必须讲同样的语言，语言就相当于协议，它分为Ethernet、NetBEUI、IPX/SPX以及TCP/IP协议。特点协议还有其他的特点：1）协议中的每个人都必须了解协议，并且预先知道所要完成的所有的步骤。2）协议中的每个人都必须同意并遵循它。3）协议必须是清楚的，每一步必须明确定义，并且不会引起误解。在计算机网络中用于规定信息的格式以及如何发送和接收信息的一套规则称为网络协议或通信协议协议也可以这样说,就是连入网络的计算机都要遵循的一定的技术规范,关于硬件、软件和端口等的技术规范。两军问题的由来及发展3.信息时代两军问题的解决5432154321H3物理传输媒体数据部分数据部分数据部分数据部分10100110100101比特流11010111010T2计算机1H5H4H2首部尾部……AP2AP1应用程序数据计算机2比特帧IP数据报IP分组TCP报文段UDP报文段发送方邮件缓存邮件服务器因特网使用SMTP协议用户邮箱接收方发送邮件使用的协议——简单邮件传送协议SMTP(SimpleMailTransferProtocol)邮件服务器接收邮件使用的协议——邮局协议版本3POP3(PostOfficeProtocolversion3)发送端ISP接收端ISP使用SMTP协议使用POP3协议sina.commail.cctv.com发信人地址：[e-mail]收信人地址：[e-mail]邮件服务器的域名读作“at”用户名（用户邮箱）邮件的传送仍然要使用IP和TCP协议超文本传送协议HTTP(HyperTextTransferProtocol)•万维网客户程序与服务器程序之间的交互遵守超文本传送协议HTTPIP电话的原理话音编码装成分组分组缓存话音解码因特网无线局域网有固定基础设施的无线局域网AP1AP2802.11局域网的物理层802.11无线局域网可再细分为不同的类型。•现在最流行的无线局域网是802.11b，而另外两种（802.11a和802.11g）的产品也广泛存在。•802.11的物理层有以下几种实现方法：–直接序列扩频DSSS–正交频分复用OFDM–跳频扩频FHSS（已很少用）–红外线IR（已很少用）几种常用的802.11无线局域网标准频段数据速率物理层优缺点802.11b2.4GHz最高为11Mb/sHR-DSSS最高数据率较低，价格最低，信号传播距离最远，且不易受阻碍802.11a5GHz最高为54Mb/sOFDM最高数据率较高，支持更多用户同时上网，价格最高，信号传播距离较短，且易受阻碍802.11g2.4GHz最高为54Mb/sOFDM最高数据率较高，支持更多用户同时上网，信号传播距离最远，且不易受阻碍，价格比802.11b贵覆盖范围几种无线网络的比较1Gb/s100Mb/s10Mb/s1Mb/s100kb/s10kb/s用户数据率PANLANMANWAN802.15.4ZigBee802.15.1蓝牙802.15.3超宽带802.11g,a802.11b802.162G移动通信3G移动通信4G移动通信Wi-FiWiMAX下一代的网际协议IPv6(IPng)解决IP地址耗尽的措施•从计算机本身发展以及从因特网规模和网络传输速率来看，现在IPv4已很不适用。•最主要的问题就是32位的IP地址不够用。•要解决IP地址耗尽的问题的措施：–采用无类别编址CIDR，使IP地址的分配更加合理。–采用网络地址转换NAT方法以节省全球IP地址。–采用具有更大地址空间的新版本的IP协议IPv6。两军问题与信息技术的未来在未来人们更加注重信息传递的安全性人们更加注重网络安全和对信息质量和信息传递速度的更高要求从而开发更为复杂和合理安全的信息传输协议。研究两军问题的意义1.保障信息高效准确的传输2.信息安全3.对于非法信息的制裁谢谢观赏